Workload balancing and throughput optimization for heterogeneous systems subject to failures

Résumé : Dans ce rapport, nous étudions le problème de l'optimisation du débit d'applications de type pipeline dans un environnement hétérogène sujet à des pannes. Les applications sont constituées d'un ensemble de tâches consécu\-tives typées et organisées selon une chaîne linéaire ou pipeline. Le but est ici de spécialiser les machines de la plate-forme d'exécution afin qu'elles ne traitent qu'un seul type de tâches, sachant qu'au départ elles peuvent exécuter tous les types. Cela permet d'éviter des reconfigurations coûteuses entre tâches de types différents sur une même machine. Ainsi, les instances d'une même tâche peuvent être distribuées sur plusieurs machines spécialisées pour le type de cette tâche, ce qui permet une répartition de la charge du système sur un ensemble de machines spécialisées. Lorsque la plate-forme est composée de machines identiques, nous prouvons qu'une solution optimale peut être trouvée en temps polynomial. Par contre, le problème devient NP-complet dès lors que deux machines peuvent traiter une même tâche à des vitesses différentes. Ce faisant, plusieurs heuristiques sont présentées dans le cas le plus réaliste d'un système spécialisé. Les résultats expérimentaux montrent que les meilleures heuristiques obtiennent de bons résultats en terme de débit, meilleurs qu'avec une allocation aléatoire, et que les débits atteints sont très proches des débits optimaux dans les cas particuliers pour lesquels une solution optimale peut être calculée.
Type de document :
Rapport
[Research Report] RR-7532, INRIA. 2011, pp.22
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00565151
Contributeur : Anne Benoit <>
Soumis le : vendredi 11 février 2011 - 10:30:22
Dernière modification le : samedi 17 septembre 2016 - 01:33:13
Document(s) archivé(s) le : mardi 6 novembre 2012 - 13:50:31

Fichier

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

Identifiants

  • HAL Id : inria-00565151, version 1

Citation

Anne Benoit, Alexandru Dobrila, Jean-Marc Nicod, Laurent Philippe. Workload balancing and throughput optimization for heterogeneous systems subject to failures. [Research Report] RR-7532, INRIA. 2011, pp.22. 〈inria-00565151〉

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

113