inria-00565151, version 1
Workload balancing and throughput optimization for heterogeneous systems subject to failures
Anne Benoit a, 1, 2Alexandru Dobrila
1, 3Jean-Marc Nicod
b, 3Laurent Philippe
b, 3
N° RR-7532 (2011)
Résumé : In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications are composed of a sequence of consecutive tasks linked as a linear graph (pipeline), with a type associated to each task. The challenge is to specialize the machines of a target platform to process only one task type, given that every machine is able to process all the types before being specialized, to avoid costly context or setup changes. Each instance can thus be performed by any machine specialized in its type and the workload of the system can be shared among a set of specialized machines. For identical machines, we prove that an optimal solution can be computed in polynomial time. However, the problem becomes NP-hard when two machines can compute the same task type at different speeds. Several polynomial time heuristics are presented for the most realistic specialized settings. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping, and close to the optimal throughput in the particular cases on which the optimal throughput can be computed.
- a – École normale supérieure de Lyon - ENS Lyon
- b – Université de Franche-Comté
- 1 : GRAAL (INRIA Grenoble Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme)
- CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I – Laboratoire d'informatique du Parallélisme
- 2 : Laboratoire de l'Informatique du Parallélisme (LIP)
- Université de Lyon – CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I
- 3 : Laboratoire d'Informatique de Franche-Comté (LIFC)
- Université de Franche-Comté : EA4269
- Domaine : Informatique/Calcul parallèle, distribué et partagé
- Référence interne : RR-7532
- inria-00565151, version 1
- http://hal.inria.fr/inria-00565151
- oai:hal.inria.fr:inria-00565151
- Contributeur : Anne Benoit
- Soumis le : Vendredi 11 Février 2011, 10:30:22
- Dernière modification le : Lundi 14 Février 2011, 10:55:19