–
October 11, 2018
Title:
A multi-criteria scheduling heuristic to optimize the execution
time, reliability, power consumption, and temperature in multicores
Abstract :
We address the problem of computing a static schedule of a DAG of tasks
onto an multicore architecture, with the goal of optimizing four
criteria: the execution time, the failure rate, the maximum power
consumption, and the peak temperature. We propose two methods. The
first is a ready list scheduling heuristic called ERPOT (Execution
time, failure Rate, POwer consumption and Temperature): it builds a
static schedule of the given DAG of tasks onto the given multicore such
that its failure rate, power consumption, and temperature remain below
three given thresholds, and such that its total execution time is as
low as possible. ERPOT replicates actively the tasks to decrease the
failure rate, uses Dynamic Voltage and Frequency Scaling to decrease
the power consumption, and inserts cooling times to control the peak
temperature. The second method uses an Integer Linear Programming (ILP)
program to compute an optimal schedule.
We advocate that, when one wants to optimize multiple criteria, it
makes more sense to build a set of solutions, each one corresponding to
a different tradeoff between those criteria, rather than to build a
single solution. This is all the more true when the criteria are
antagonistic, which is the case here: for instance, improving the
failure rate requires to add some redundancy in the schedule (in our
case spatial redundancy), which penalizes the execution time. For this
reason, we use ERPOT to build a Pareto front in the 4D space (exec.
time, fail. rate, power, temp.), by varying the three thresholds on the
failure rate, power, and temperature. Our experimental comparisons show
that the schedules produced by ERPOT are on average only 10% worse than
the optimal schedules computed by our ILP program, and that ERPOT
outperforms the PowerPerf-PET heuristic from the literature by at least
35%.
