Optimizing the steady-state throughput of Broadcasts on heterogeneous platforms

Arnaud Legrand 1 Olivier Beaumont Loris Marchal Yves Robert
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we consider the communications involved by the execution of a complex application, deployed on a heterogeneous «grid» 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 and computation speeds. 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 show how to compute the best throughput using linear programming, and how to exhibit a periodic schedule, first when restricting to a DAG, and then when using a general graph. 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

https://hal.inria.fr/inria-00071712
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:35:24 PM
Last modification on : Tuesday, December 11, 2018 - 10:58:13 AM
Long-term archiving on : Sunday, April 4, 2010 - 10:34:39 PM

Identifiers

  • HAL Id : inria-00071712, version 1

Collections

Citation

Arnaud Legrand, Olivier Beaumont, Loris Marchal, Yves Robert. Optimizing the steady-state throughput of Broadcasts on heterogeneous platforms. RR-4871, INRIA. 2003. ⟨inria-00071712⟩

Share

Metrics

Record views

428

Files downloads

244