Energy Aware Task Scheduling on Heterogeneous Systems

Abstract

We consider the problem of scheduling directed a-cyclic task graphs (DAG) on heterogeneous distributed processor systems with the twin objectives of minimizing finish time and energy consumption. Previous scheduling heuristics have assigned DAGs to processors to minimize overall run-time of applications. But due to many new applications on embedded systems such as high performance DSP in image processing, multimedia, and wireless security, there is a strong need for scheduling algorithms which lower energy consumption and yet attain good finish times. In this research, we employ dynamic voltage scaling (DVS) within the scheduling heuristics to achieve the twin objectives. The processors used can run on different discrete operating voltages. Processors can scale down their voltages to slow down in order to reduce energy consumption whenever they idle due to task dependencies. Specifically, we combine Decisive Path Scheduling (DPS) and Heterogeneous N-predecessor Duplication (HNPD) with DVS. Using simulations, we show average energy consumption reductions of 40% over DPS and 28% over HNPD. The simulations used large number of randomly generated DAGs with various characteristics as well as DAGs of real world problems. Energy savings increased with increasing number of nodes or increasing Communication to Computation Ratios (CCR) whereas it decreased with increasing parallelism (out-degree) or increasing number of available processors. Increasing nodes, increase tasks dependencies and thus idle times. When CCR increases, processors are idle longer due to communication between tasks. Our algorithms used such idle times to achieve energy savings. An increase in out-degree resulted in smaller average energy savings. A larger out-degree allows more processors to run in parallel, reducing idle times.