| Identifiant de l'article : |
 |
inria-00515209, version 2 |
|
|
| Domaine : |
|
Informatique/Calcul parallèle, distribué et partagé
|
|
|
| Titre : |
|
On the performance of greedy algorithms for energy minimization |
|
|
| Auteur(s) : |
|
Anne Benoit1, Paul Renaud-Goud1, Yves Robert1 |
|
|
| Projet(s) / laboratoire(s) : |
|
| 1 : |
INRIA Grenoble Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme - GRAAL |
|
|
|
| Résumé : |
|
We revisit the well-known greedy algorithm for scheduling independent jobs on parallel processors, with the objective of energy minimization. We assess the performance of the online version, as well as the performance of the offine version, which sorts the jobs by non-increasing size before execution. We derive new approximation factors, as well as examples that show that these factors cannot be improved, thereby completely characterizing the performance of the algorithms. |
|
|
| Langue du document : |
|
Anglais |
|
|
|
| Mots-clés : |
|
Greedy algorithm – Independent jobs – Parallel processors – Energy minimization |
|
|
BibTeX,EndNote,...
