Pipelining Broadcasts on Heterogeneous Platforms under the One-Port Model.

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. Rather than aiming at minimizing the execution time of a single broadcast, we focus on the steady-state operation. We assume that there is a large number of messages to be broadcast in pipeline fashion, and we aim at maximizing the throughput, i.e. the (rational) number of messages which can be broadcast every time-step. We target heterogeneous platforms, modeled by a graph where resources have different communication speeds under the unidirectional one-port model (i.e. at a given time step, a processor can be involved in at most one (incoming or outgoing) communication with one of its neighbors). Achieving the best throughput may well require that the target platform is used in totality: we show that neither spanning trees nor DAGs are as powerful as general graphs. We propose a rather sophisticated polynomial algorithm for determining the optimal throughput that can be achieved using a platform, together with a (periodic) schedule achieving this throughput. The algorithm is based on the use of polynomial oracles and of the ellipsoid method for solving in linear programs in rational numbers. The polynomial compactness of the description comes from the decomposition of the schedule into several broadcast trees that are used concurrently to reach the best throughput. It is important to point out that a concrete scheduling algorithm based upon the steady-state operation is asymptotically optimal, in the class of all possible schedules (not only periodic solutions).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 la diffusion de données à travers le réseau d’interconnexion. Nous cherchons à optimiser le débit d’une telle diffusion en régime permanent, en supposant qu’un grand nombre de messages doivent être diffusés successivement, comme c’est le cas pour le parallélisme de données. Nous visons des plateformes hétérogènes, modélisées par un graphe où les ressources de communications ont des vitesses différentes et utilisent le modèle un-port ; i.e. à un instant donné, un nœud est impliqué dans au plus un transfert de données ( émission ou réception). Nous étudions la diffusion utilisant des sous-réseaux avec des topologies restreintes (arbres ou graphes acycliques dirigés) et montrons que celles-ci sont moins puissantes que des graphes généraux. Nous proposons un algorithme sophistiqué pour calculer le débit optimal dans le cas général et construire un ordonnancement périodique qui le réalise. Notre algorithme est basé sur l’utilisation d’oracles polynomiaux et de la méthode de ellipsoïde [9,13] afin de résoudre des systèmes linéaires en nombres rationnels. Nous montrons que l’ordonnancement réalisé est asymptotique-ment optimal, parmi tous les ordonnancements possibles (pas seulement les solutions périodique