Complexity Results and Heuristics for Pipelined Multicast Operations on Heterogeneous Platforms

Olivier Beaumont 1, 2 Arnaud Legrand 3 Loris Marchal 3, 4 Yves Robert 5
2 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
INRIA Futurs, Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
3 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
5 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We consider the communications involved by the execution of a complex application deployed on a heterogeneous platform. Such applications extensively use macro-communication schemes, such as multicast operations, where messages are broadcast to a set of predefined targets. We assume that there are a large number of messages to be multicast in pipeline fashion, and we seek to maximize the throughput of the steady-state operation. We target heterogeneous platforms, modeled by a graph where links have different communication speeds. We show that the problem of computing the best throughput for a multicast operation is NP-hard, whereas the best throughput to broadcast a message to every node in a graph can be computed in polynomial time. Thus, we introduce several heuristics to deal with this problem and prove that some of them are approximation algorithms. We perform, simulations to test these heuristics and show that their results are close to a theoretical upper bound on the throughput that we obtain with a linear programming approach.
Type de document :
Communication dans un congrès
2004 International Conference on Parallel Processing (ICPP\'2004), 2004, Unknown, IEEE Computer Society Press, pp.267―274, 2004, <10.1109/ICPP.2004.1327931>
Liste complète des métadonnées

https://hal.inria.fr/hal-00789448
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:51:40
Dernière modification le : vendredi 11 septembre 2015 - 01:06:01

Identifiants

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Loris Marchal, Yves Robert. Complexity Results and Heuristics for Pipelined Multicast Operations on Heterogeneous Platforms. 2004 International Conference on Parallel Processing (ICPP\'2004), 2004, Unknown, IEEE Computer Society Press, pp.267―274, 2004, <10.1109/ICPP.2004.1327931>. <hal-00789448>

Partager

Métriques

Consultations de la notice

136