Keynote
Posted: Fri Jun 01, 2018
Title: A multi-criteria scheduling heuristic to optimize the execution time, the reliability, the power consumption and the 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: execution time, reliability, maximum power consumption, and peak temperature. We propose a ready list scheduling heuristic: it builds a static schedule of the given DAG of tasks onto the given multicore such that its reliability, power consumption, and temperature remain below three given thresholds, and such that its total execution time is as low as possible. We replicate actively the tasks to increase the reliability, we use Dynamic Voltage and Frequency Scaling to decrease the power consumption, and we insert cooling times to control the peak temperature. 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 reliability requires to add some redundancy in the schedule (in our case spatial redundancy), which penalizes the execution time. For this reason, we build a Pareto front in the 4D space (exec. time, reliability, power, temp.), by varying the three thresholds on the reliability, power, and temperature.
Comparisons show that the schedules produced by our heuristic are on average only 10% worse than the optimal schedules (computed by an ILP program), and 35% better than the ones generated by the PowerPerf-PET heuristic from the literature.
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: execution time, reliability, maximum power consumption, and peak temperature. We propose a ready list scheduling heuristic: it builds a static schedule of the given DAG of tasks onto the given multicore such that its reliability, power consumption, and temperature remain below three given thresholds, and such that its total execution time is as low as possible. We replicate actively the tasks to increase the reliability, we use Dynamic Voltage and Frequency Scaling to decrease the power consumption, and we insert cooling times to control the peak temperature. 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 reliability requires to add some redundancy in the schedule (in our case spatial redundancy), which penalizes the execution time. For this reason, we build a Pareto front in the 4D space (exec. time, reliability, power, temp.), by varying the three thresholds on the reliability, power, and temperature.
Comparisons show that the schedules produced by our heuristic are on average only 10% worse than the optimal schedules (computed by an ILP program), and 35% better than the ones generated by the PowerPerf-PET heuristic from the literature.