Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Scheduling strategies for master-slave tasking on heterogeneous processor grids

Cyril Banino Olivier Beaumont 1, 2 Arnaud Legrand 3, 4 Yves Robert 3, 4 
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, É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 (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 interconnection graph, and allowing for several masters. Because spanning trees are easier to deal with in practice (there is a single path from the master to each node), 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-hard. Even worse, we show that there exist heterogeneous networks for which the optimal spanning tree has a throughput which is arbitrarily bad in front of the throughput that can be achieved by the optimal (multiple-path) solution. Still, we introduce and compare several low-complexity heuristics to determine a sub-optimal spanning tree. Fortunately, we observe that the best heuristics do achieve an excellent performance in most experiments.
Complete list of metadata
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Wednesday, April 3, 2013 - 2:53:47 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:19 AM


  • HAL Id : hal-00807406, version 1



Cyril Banino, Olivier Beaumont, Arnaud Legrand, Yves Robert. Scheduling strategies for master-slave tasking on heterogeneous processor grids. [Research Report] 2002-12, 2002. ⟨hal-00807406⟩



Record views