A General Methodology for Energy-efficient Scheduling in Multicore Environments Based on Evolutionary Algorithms
Zorana Banković, Umer Liqat and Pedro López-García
In this work we present a general methodology for energy-efficient scheduling in multicore environments, which can be adapted to different features that the underlying environment exhibits, e.g., time and power consumption of different tasks, as well as to different requirements of the task scheduling, e.g., time or energy budgets, priorities, etc. We demonstrate how each of the different features can be used to obtain better scheduling results in terms of reducing the total execution time and power consumption. Given that task scheduling is in general a NP-hard problem, we rely on an Evolutionary Algorithm (EA) to provide an optimal solution in an acceptable amount of time. If the EA is not capable to provide a viable solution, in the sense that not all task deadlines are met, we resort to a modified version of the well known YDS algorithm. In this way, the methodology we propose always provides a viable solution to the scheduling problem. In the tested scenarios, our EA can save up to 55 − 90% more energy on average than our modified YDS algorithm. We also model task dependence using copula theory in the EA and prove that better results can be obtained when the dependence is modeled. The resulting stochastic scheduler can save up to 18% more energy on average compared to the deterministic scheduler.
Keywords: Task scheduling, multicore, energy efficiency, evolutionary algorithm, YDS, probabilistic inference, copulas