2011/11/23 by Guillaume Aupy, Aupy, Guillaume, Anne Benoit +4
Computer Science · #Cloud Computing and Resource Management #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Parallel Computing and Optimization Techniques #Real-Time Systems Scheduling #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1111.5528
22 pages. A 10 pages version should appear in HiPC'12
openalex publication_date 2011/11/23 · arxiv created 2012/08/02 · arxiv updated 2012/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a task graph mapped on a set of homogeneous processors. We aim at minimizing the energy consumption while enforcing two constraints: a prescribed bound on the execution time (or makespan), and a reliability threshold. Dynamic voltage and frequency scaling (DVFS) is an approach frequently used to reduce the energy consumption of a schedule, but slowing down the execution of a task to save energy is decreasing the reliability of the execution. In this work, to improve the reliability of a schedule while reducing the energy consumption, we allow for the re-execution of some tasks. We assess the complexity of the tri-criteria scheduling problem (makespan, reliability, energy) of deciding which task to re-execute, and at which speed each execution of a task should be done, with two different speed models: either processors can have arbitrary speeds (continuous model), or a processor can run at a finite number of different speeds and change its speed during a computation (VDD model). We propose several novel tri-criteria scheduling heuristics under the continuous speed model, and we evaluate them through a set of simulations. The two best heuristics turn out to be very efficient and complementary.