Energy-efficient task scheduling on heterogeneous computingrnsystems by linear programming

摘要

The continually increasing energy consumption represents a critical issue in modern heterogeneousrncomputing systems. With the aid of dynamic voltage frequency scaling (DVFS), taskrnscheduling is considered an effective software-based technique for reducing the total energy consumptionrnand minimizing the overall schedule length (makespan). A natural solution is to reclaimrnthe slack time in a given time-efficient schedule, which is also referred to as a “two-pass” methodrnor a “rescheduling” method. A number of studies have focused on slack reclamation to achievernenergy reductions through heuristics; although, these methods offer suboptimal solutions. In thisrnarticle, the rescheduling optimization problem is formulated as a linear program for minimizingrnan energy objective function subject to precedence and deadline constraints implied in the givenrnschedule.Twotypesofdecision variables, ie, frequency duty factors and task intervals, are definedrnto set up the linearmodel. Consequently, an optimal solution to the problem can be provided in arnstraightforwardmanner by a linear programming solver, which suggests that such a reschedulingrnproblem belongs to the P (polynomial time) class. The experimental results show the effectivenessrnof the proposed approach and demonstrate that the performance is superior to that of otherrncompetitive algorithms in terms of both energy saving and runtime efficiency.