Optimizing the steady-state throughput of scatter and reduce operations on heterogeneous platforms.

In this paper, we consider the communications involved by the execution of a complex application, deployed on a heterogeneous ``grid'' platform. Such applications intensively use collective macro-communication schemes, such as scatters, personalized all-to-alls or gather/reduce operations. Rather than aiming at minimizing the execution time of a single macro-communication, we focus on the steady-state operation. We assume that there is a large number of macro-communication to perform in pipeline fashion, and we aim at maximizing the throughput, i.e. the (rational) number of macro-communications which can be initiated every time-step. We target heterogeneous platforms, modeled by a graph where resources have different communication and computation speeds. The situation is simpler for series of scatters or personalized all-to-alls than for series of reduces operations, because of the possibility of combining various partial reductions of the local values, and of interleaving computations with communications. In all cases, we show how to determine the optimal throughput, and how to exhibit a concrete periodic schedule that achieves this throughput.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 de communications collectives, telle que des diffusions ou des échanges totaux personnalisés, ou encore des opérations de réduction. Nous nous intéressons ici à optimiser le débit de telles opérations en régime permanent, en supposant qu'un grand nombre de communications collectives semblables doivent être effectuées successivement, comme c'est le cas pour le parallélisme de données. La plateforme hétérogène que nous visons est modélisée par un graphe où les différentes ressources ( calcul ou communication) ont des vitesses différentes. Pour les opérations de communications précédentes, nous montrons comment calculer le débit optimal et comment construire un ordonnancement périodique qui réalise ce débit