  In recent years, the issue of energy consumption in parallel and distributed
computing systems has attracted a great deal of attention. In response to this,
many energy-aware scheduling algorithms have been developed primarily using the
dynamic voltage-frequency scaling (DVFS) capability which has been incorporated
into recent commodity processors. Majority of these algorithms involve two
passes: schedule generation and slack reclamation. The former pass involves the
redistribution of tasks among DVFS-enabled processors based on a given cost
function that includes makespan and energy consumption; and, while the latter
pass is typically achieved by executing individual tasks with slacks at a lower
processor frequency. In this paper, a new slack reclamation algorithm is
proposed by approaching the energy reduction problem from a different angle.
Firstly, the problem of task slack reclamation by using combinations of
processors' frequencies is formulated. Secondly, several proofs are provided to
show that (1) if the working frequency set of processor is assumed to be
continues, the optimal energy will be always achieved by using only one
frequency, (2) for real processors with a discrete set of working frequencies,
the optimal energy is always achieved by using at most two frequencies, and (3)
these two frequencies are adjacent/neighbouring when processor energy
consumption is a convex function of frequency. Thirdly, a novel algorithm to
find the best combination of frequencies to result the optimal energy is
presented. The presented algorithm has been evaluated based on results obtained
from experiments with three different sets of task graphs: 3000 randomly
generated task graphs, and 600 task graphs for two popular applications
(Gauss-Jordan and LU decomposition). The results show the superiority of the
proposed algorithm in comparison with other techniques.
