Optimizing the Steady-State Throughput of Scatter and Reduce Operations on Heterogeneous Platforms

Arnaud Legrand 1 Loris Marchal 2, 3 Yves Robert 4
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 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 large-scale distributed 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-communications 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.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2005, 65, pp.1497―1514. <10.1016/j.jpdc.2005.05.021>
Liste complète des métadonnées

https://hal.inria.fr/hal-00789425
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:49:55
Dernière modification le : mercredi 14 décembre 2016 - 01:09:22

Identifiants

Collections

Citation

Arnaud Legrand, Loris Marchal, Yves Robert. Optimizing the Steady-State Throughput of Scatter and Reduce Operations on Heterogeneous Platforms. Journal of Parallel and Distributed Computing, Elsevier, 2005, 65, pp.1497―1514. <10.1016/j.jpdc.2005.05.021>. <hal-00789425>

Partager

Métriques

Consultations de la notice

300