Reclaiming the energy of a schedule: models and algorithms

Abstract : We consider a task graph to be executed on a set of processors. We assume that the mapping is given, say by an ordered list of tasks to execute on each processor, and we aim at optimizing the energy consumption while enforcing a prescribed bound on the execution time. Although it is not possible to change the allocation of a task, it is possible to change its speed. Rather than using a local approach such as backfilling, we consider the problem as a whole and study the impact of several speed variation models on its complexity. For continuous speeds, we give a closed-form formula for trees and series-parallel graphs, and we cast the problem into a geometric programming problem for general directed acyclic graphs. We show that the classical dynamic voltage and frequency scaling (DVFS) model with discrete modes leads to an NP-complete problem, even if the modes are regularly distributed (an important particular case in practice, which we analyze as the incremental model). On the contrary, the Vdd-hopping model that allows to switch between different supply voltages (VDD) while executing a task leads to a polynomial solution. Finally, we provide an approximation algorithm for the incremental model, which we extend for the general DVFS model.
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2013, 25, pp.1505-1523. 〈10.1002/cpe.2889〉
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00763388
Contributeur : Equipe Roma <>
Soumis le : mardi 3 septembre 2013 - 11:29:07
Dernière modification le : jeudi 8 novembre 2018 - 14:26:08
Document(s) archivé(s) le : vendredi 31 mars 2017 - 18:16:57

Fichier

ccpe.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Guillaume Aupy, Anne Benoit, Fanny Dufossé, Yves Robert. Reclaiming the energy of a schedule: models and algorithms. Concurrency and Computation: Practice and Experience, Wiley, 2013, 25, pp.1505-1523. 〈10.1002/cpe.2889〉. 〈hal-00763388〉

Partager

Métriques

Consultations de la notice

220

Téléchargements de fichiers

113