Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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

Abstract : 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).
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:06:10 AM
Last modification on : Wednesday, October 26, 2022 - 8:15:30 AM


Files produced by the author(s)


  • HAL Id : hal-02101785, version 1



Olivier Beaumont, Loris Marchal. Pipelining Broadcasts on Heterogeneous Platforms under the One-Port Model.. [Research Report] LIP RR-2004-32, Laboratoire de l'informatique du parallélisme. 2004, 2+22p. ⟨hal-02101785⟩



Record views


Files downloads