Dynamic and Static Energy Efficient Scheduling of Task Graphs on Multiprocessors: A Heuristic

Abstract

For energy efficient scheduling of task graphs on multiprocessors, dynamic voltage and frequency scaling (DVFS) and duplication are two widely used techniques. DVFS is generally used to utilize the execution slack by lowering the voltage and frequency of a task to decrease the dynamic energy consumption. Whereas duplication decreases the schedule length and communication energy consumption by replicating certain dependent tasks to avoid communication delays. However, while making decisions on DVFS and duplication for a task, the static energy consumption is mostly overlooked. With chip technologies reducing to a few nano meters, static energy consumption due to leakage current has become important. This article proposes a novel polynomial time heuristic that uses both DVFS and duplication to optimize static energy consumption along with dynamic and communication energy when scheduling task graphs on heterogeneous multiprocessors. The proposed list scheduling algorithm also balances schedule length with energy consumption using proposed normalized difference parameters while making scheduling decisions for a particular task. The results demonstrate the ability of the proposed algorithm to decrease the overall energy consumption with an improved or comparable schedule length as compared with other algorithms in various scenarios.

Keywords

• Scheduling
• duplication
• DVFS
• multiprocessors
• heterogeneity