Approximation algorithms for energy, reliability and makespan optimization problems

Guillaume Aupy 1, 2, * Anne Benoit 1, 2, *
* Auteur correspondant
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Dans ce papier, nous considérons le problème d'ordonnancement d'une application sur une plateforme parallèle de calcul. L'application est un graphe de tâches particulier: soit une chaîne de tâche, soit un ensemble de tâches indépendantes. La plateforme est constituée de processeurs identiques, dont la vitesse peut être modifiée dynamiquement. Cette plateforme est aussi sujette à des fautes: lorsque l'on réduit la vitesse d'exécution d'un processeur pour diminuer la consommation d'énergie, ce processeur a une plus grande chance de faillir. C'est pourquoi, pour augmenter la fiabilité du processus, l'ordonnanceur va devoir choisir de re-exécuter ou répliquer certaines tâches (les exécuter deux fois, soit sur le même processeur, soit sur deux processeurs distincts). Le problème est donc tri-critère: nous cherchons à minimiser la consommation d'énergie, tout en préservant une limite sur le temps d'exécution, ainsi qu'une borne sur la fiabilité de chaque tâche. Nos contributions résident en l'écriture d'algorithmes d'approximation efficaces pour les deux classes de graphes étudiées. Dans le cas des chaînes linéaires, nous proposons un schéma d'approximation entièrement polynomial (FPTAS). Puis nous prouvons qu'il n'existe pas d'algorithmes d'approximation à facteur constant dans le cas des tâches indépendantes, sauf si P=NP, mais nous sommes cependant capable d'exhiber un algorithme d'approximation lorsque l'on autorise une relaxation de la contrainte sur le temps d'exécution.
Type de document :
Rapport
[Research Report] RR-8107, INRIA. 2014, pp.32
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00742754
Contributeur : Guillaume Aupy <>
Soumis le : lundi 7 juillet 2014 - 11:58:01
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : mardi 11 avril 2017 - 10:02:03

Fichier

RR-8107.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00742754, version 2

Collections

Citation

Guillaume Aupy, Anne Benoit. Approximation algorithms for energy, reliability and makespan optimization problems. [Research Report] RR-8107, INRIA. 2014, pp.32. 〈hal-00742754v2〉

Partager

Métriques

Consultations de la notice

351

Téléchargements de fichiers

167