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

doi:10.1109/ICPP.2004.1327931

Metadatos

Licencia de uso del documento

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]

Idioma

Communication dans un congrès

Este ítem está publicado en

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

IEEE Computer Society Press

Resumen en inglés

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.< Leer menos

Metadatos

Compartir este ítem

Licencia de uso del documento

Complexity Results and Heuristics for Pipelined Multicast Operations on Heterogeneous Platforms

Idioma

Este ítem está publicado en

Resumen en inglés

URI

DOI

Orígen

Centros de investigación