A Fast Heuristic for Scheduling Parallel Software with Respect to Energy and Timing Constraints

摘要

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.