Scheduling Strategies for Mixed Data and Task Parallelism on Heterogeneous Clusters

Olivier Beaumont 1, 2 Arnaud Legrand 3 Loris Marchal 3, 4 Yves Robert 3
1 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
INRIA Futurs, Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
3 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We consider the execution of a complex application on a heterogeneous "grid" computing platform. The complex application consists of a suite of identical, independent problems to be solved. In turn, each problem consists of a set of tasks. There are dependences (precedence constraints) between these tasks and these dependences are organized as a tree. A typical example is the repeated execution of the same algorithm on several distinct data samples. We use a non-oriented graph to model the grid platform, where resources have different speeds of computation and communication. We show how to determine the optimal steady-state scheduling strategy for each processor (the fraction of time spent computing and the fraction of time spent communicating with each neighbor). This result holds for a quite general framework, allowing for cycles and multiple paths in the platform graph.
Complete list of metadatas
Contributor : Arnaud Legrand <>
Submitted on : Monday, February 18, 2013 - 11:50:58 AM
Last modification on : Tuesday, December 11, 2018 - 10:58:09 AM



Olivier Beaumont, Arnaud Legrand, Loris Marchal, Yves Robert. Scheduling Strategies for Mixed Data and Task Parallelism on Heterogeneous Clusters. Parallel Processing Letters, World Scientific Publishing, 2003, 13, pp.225―244. ⟨10.1142/S0129626403001252⟩. ⟨hal-00789432⟩



Record views