Scheduling on power-heterogeneous processors

Susanne Albers 1 Evripidis Bampis 2 Dimitrios Letsios 3 Giorgio Lucarelli 4 Richard Stotz 1
2 RO - Recherche Opérationnelle
LIP6 - Laboratoire d'Informatique de Paris 6
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We consider the problem of scheduling a set of jobs, each one specified by its release date, its deadline and its processing volume, on a set of heterogeneous speed-scalable processors, where the energy-consumption rate is processor-dependent. Our objective is to minimize the total energy consumption when both the preemption and the migration of jobs are allowed. We propose a new algorithm based on a compact linear programming formulation. Our method approaches the value of the optimal solution within any desired accuracy for a large set of continuous power functions. Furthermore, we develop a faster combinatorial algorithm based on flows for standard power functions and jobs whose density is lower bounded by a small constant. Finally, we extend and analyze the AVerage Rate (AVR) online algorithm in the heterogeneous setting.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2017, 257, pp.22-33. 〈10.1016/j.ic.2017.09.013〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01668736
Contributeur : Lucarelli Giorgio <>
Soumis le : mercredi 7 mars 2018 - 09:43:29
Dernière modification le : jeudi 11 octobre 2018 - 08:48:05
Document(s) archivé(s) le : vendredi 8 juin 2018 - 12:35:27

Fichier

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

Identifiants

Citation

Susanne Albers, Evripidis Bampis, Dimitrios Letsios, Giorgio Lucarelli, Richard Stotz. Scheduling on power-heterogeneous processors. Information and Computation, Elsevier, 2017, 257, pp.22-33. 〈10.1016/j.ic.2017.09.013〉. 〈hal-01668736〉

Partager

Métriques

Consultations de la notice

444

Téléchargements de fichiers

33