Complexity results and heuristics for pipelined multicast operations on heterogeneous platforms

Olivier Beaumont 1 Arnaud Legrand 1 Loris Marchal 1 Yves Robert 1
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we consider the communications involved by the execution of a complex application deployed on a heterogeneous platform. Such applications extensively use macro-communication schemes, for example to broadcast data items to several targets, known as the multicast operation. Rather than seeking to minimize the execution time of a single multicast, we focus on steady-state performance. We target heterogeneous platforms, modeled by a graph where resources 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; most of them are based on linear programming. We prove that some of these heuristics 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 the linear programming approach.
Type de document :
Rapport
[Research Report] RR-5123, INRIA. 2004
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00071460
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 17:36:47
Dernière modification le : mardi 16 janvier 2018 - 15:42:36
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:16:20

Fichiers

Identifiants

  • HAL Id : inria-00071460, version 1

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Loris Marchal, Yves Robert. Complexity results and heuristics for pipelined multicast operations on heterogeneous platforms. [Research Report] RR-5123, INRIA. 2004. 〈inria-00071460〉

Partager

Métriques

Consultations de la notice

198

Téléchargements de fichiers

96