Title | ||
---|---|---|
A Fast Heuristic for Scheduling Parallel Software with Respect to Energy and Timing Constraints |
Abstract | ||
---|---|---|
Embedded systems with several heterogeneous processors require scheduling techniques that are able to make use of the parallel processors while at the same time keeping resource consumption low. In this paper, we therefore introduce a scheduling algorithm that considers timing and energy requirements for computation and communication and allows deadlines on program parts. The software applications are represented by Synchronous Dataflow Graphs (SDF) as these allow one to represent software concurrency and enable effective scheduling on multi-processor platforms. We suggest a scheduling heuristic that generates a number of possible schedules for an SDF representation of a parallelizable program, ranging from fast schedules with high energy consumption to slow schedules with lower energy consumption. Besides being able to choose only schedules that satisfy a specific global deadline or do not exceed a certain energy consumption, we allow individual constraints on single nodes of the SDF graph. The problems arising from including such constraints into the scheduling and adapting the heuristic accordingly are explained. The performance of our scheduling heuristic is illustrated on randomly generated graphs. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1109/IPDPS.2011.284 | IPDPS Workshops |
Keywords | Field | DocType |
parallel software,energy requirement,scheduling heuristic,lower energy consumption,certain energy consumption,scheduling algorithm,sdf graph,high energy consumption,sdf representation,fast heuristic,timing constraints,resource consumption low,effective scheduling,dynamic scheduling,schedules,embedded system,embedded systems,parallel processor,parallel programming | Fixed-priority pre-emptive scheduling,Fair-share scheduling,Computer science,Parallel computing,Gang scheduling,Two-level scheduling,Least slack time scheduling,Rate-monotonic scheduling,Earliest deadline first scheduling,Dynamic priority scheduling,Distributed computing | Conference |
Citations | PageRank | References |
1 | 0.35 | 20 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Margarete Sackmann | 1 | 1 | 0.69 |
Peter Ebraert | 2 | 153 | 10.53 |
Dirk Janssens | 3 | 522 | 88.99 |