BEAUMONT, Olivier; LEGRAND, Arnaud; MARCHAL, Loris; ROBERT, Yves

doi:10.1109/ICPP.2004.1327931

Métadonnées

Licence d’utilisation du document

BEAUMONT, Olivier
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]

LEGRAND, Arnaud
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]

MARCHAL, Loris
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]

Langue

Communication dans un congrès

Ce document a été publié dans

2004 International Conference on Parallel Processing (ICPP\'2004), 2004, Unknown. 2004p. 267―274

IEEE Computer Society Press

Résumé en anglais

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.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Complexity Results and Heuristics for Pipelined Multicast Operations on Heterogeneous Platforms

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche