Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Platforms

Cyril Banino 1 Olivier Beaumont 1, 2 Larry Carter 3 Jeanne Ferrante 3 Arnaud Legrand 4 Yves Robert 5
2 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
4 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
5 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous computing platform. We use a nonoriented graph to model the platform, where resources can have different speeds of computation and communication. Because the number of tasks is large, we focus on the question of determining 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). In contrast to minimizing the total execution time, which is NP-hard in most formulations, we show that finding the optimal steady state can be solved using a linear programming approach and, thus, in polynomial time. Our result holds for a quite general framework, allowing for cycles and multiple paths in the interconnection graph, and allowing for several masters. We also consider the simpler case where the platform is a tree. While this case can also be solved via linear programming, we show how to derive a closed-form formula to compute the optimal steady state, which gives rise to a bandwidth-centric scheduling strategy. The advantage of this approach is that it can directly support autonomous task scheduling based only on information local to each node; no global information is needed. Finally, we provide a theoretical comparison of the computing power of tree-based versus arbitrary platforms.
Type de document :
Article dans une revue
IEEE Trans. Parallel Distributed Systems, IEEE Computer Society, 2004, 15, pp.319―330. <10.1109/TPDS.2004.1271181>
Liste complète des métadonnées

https://hal.inria.fr/hal-00789427
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:49:56
Dernière modification le : vendredi 11 septembre 2015 - 01:06:00

Identifiants

Collections

Citation

Cyril Banino, Olivier Beaumont, Larry Carter, Jeanne Ferrante, Arnaud Legrand, et al.. Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Platforms. IEEE Trans. Parallel Distributed Systems, IEEE Computer Society, 2004, 15, pp.319―330. <10.1109/TPDS.2004.1271181>. <hal-00789427>

Partager

Métriques

Consultations de la notice

235