Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Grids

Cyril Banino 1 Olivier Beaumont 1, 2 Arnaud Legrand 3 Yves Robert 3
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
3 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 problem of allocating a large number of independent, equal-sized tasks to a heterogeneous "grid" computing platform. We use a non-oriented graph to model a grid, where resources can have different speeds of computation and communication, as well as different overlap capabilities. We show how to determine the optimal steady-state scheduling strategy for each processor. Because spanning trees are easier to deal with in practice, a natural question arises: how to extract the best spanning tree, i.e. the one with optimal steady-state throughput, out of a general interconnection graph? We show that this problem is NP-Complete. Still, we introduce and compare several low-complexity heuristics to determine a sub-optimal spanning tree.
Type de document :
Communication dans un congrès
PARA\'02: International Conference on Applied Parallel Computing, Jun 2002, Espoo, Finland. Springer Verlag, pp.423―432, 2002, LNCS 2367. 〈10.1007/3-540-48051-X_42〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00789455
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:51:47
Dernière modification le : vendredi 11 septembre 2015 - 01:06:02

Identifiants

Collections

Citation

Cyril Banino, Olivier Beaumont, Arnaud Legrand, Yves Robert. Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Grids. PARA\'02: International Conference on Applied Parallel Computing, Jun 2002, Espoo, Finland. Springer Verlag, pp.423―432, 2002, LNCS 2367. 〈10.1007/3-540-48051-X_42〉. 〈hal-00789455〉

Partager

Métriques

Consultations de la notice

160