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

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.

Nous nous intéressons ici aux communications qui ont lieu lors de l’exécution d’une application complexe distribuée sur un environnement hétérogène de type “grille de calcul”. De telles applications font un usage intensif des primitives de communications collectives, comme par exemple le multicast (diffusion de données vers plusieurs cibles). Nous supposons qu’il y a un grand nombre de messages `a diffuser et cherchons à optimiser le débit de telles opérations en régime permanent. La plate-forme hétérogène sous-jacente est modélisée par un graphe où les différentes ressources (processeurs, liens de communication) ont des vitesses diff ́e-rentes. Nous montrons que calculer le meilleur débit pour une opération de multicast est un problème NP-dur, alors le meilleur débit pour un broadcast (diffusion vers tous les nœuds de la plate-forme) peut être calculé en temps polynomial. Nous introduisons donc plusieurs heuristiques pour le problème du multicast, dont la plupart sont basées sur la programmation linéaire, et dont certaines sont garanties à un facteur près de l’optimal. Nous réalisons des simulations pour tester les performances de ces heuristiques et montrons que leur résultat est proche d’une borne supérieure théorique sur le débit que nous avons obtenue avec notre approche utilisant la programmation linéaire.

Mots clés: HETEROGENEOUS PLATFORMS; COMPLEXITY; SCHEDULING; STEADY-STATE

Mots clés: ORDONNANCEMENT; REGIME PERMANENT; PLATEFORMES HETEROGENES; COMPLEXITE

Domaines: Autre [cs.OH]

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