Broadcast Trees for Heterogeneous Platforms.

Olivier Beaumont (1) , Loris Marchal (1) , Yves Robert (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

In this paper, we deal with broadcasting on heterogeneous platforms. Typically, the message to be broadcast is split into several slices, which are sent by the source processor in a pipeline fashion. A spanning tree is used to implement this operation, and the objective is to find the tree which maximizes the throughput, i.e. the average number of slices sent by the source processor every time-unit. We introduce several heuristics to solve this problem. The good news is that the best heuristics perform quite efficiently, reaching more than 70% of the absolute optimal throughput, thereby providing a simple yet efficient approach to achieve very good performance for broadcasting on heterogeneous platforms.

Dans ce rapport, nous considérons le problème de la diffusion de messages sur plateformes hétérogènes. En particulier, nous considérons le cas où le message à envoyer, de grande taille, est fractionné en plusieurs morceaux qui sont envoyés par le processeur à la source de la diffusion de façon successive et pipelinée. On utilise un arbre de diffusion pour implémenter cette opération, et le but est de trouver l’arbre de diffusion qui permet d’obtenir le meilleur débit. Nous introduisons plusieurs heuristiques pour résoudre ce problème. La meilleure de ces heuristiques atteint un débit de plus de 70% de l’optimal, et fournit ainsi une approche simple mais efficace pour obtenir de bonnes performances pour la diffusion sur plates-formes hétérogènes.

Mots clés: Collective communications; Heterogeneous platforms; Modeling; Steady-state

Mots clés: Communications collectives; Régime permanent; Plateformes hétérogènes; Modélisation

Domaines: Informatique [cs]

Olivier Beaumont, Loris Marchal, Yves Robert. Broadcast Trees for Heterogeneous Platforms.. [Research Report] Laboratoire de l'informatique du parallélisme; LIP RR-2004-46. 2004, 2+18p. ⟨hal-02101806⟩