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
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101785
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:06:10 AM
Last modification on : Wednesday, November 20, 2019 - 3:13:35 AM

File

RR2004-32.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101785, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

21

Files downloads

12