Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Grids
| |
|
Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Grids
C. Banino5, O. Beaumont5, A. Legrand6 and Y. Robert6
| (5) |
LaBRI, UMR CNRS, 5800, Domaine Universitaire, 33405 Talence Cedex, France |
| (6) |
LIP, UMR CNRS-INRIA, 5668 ENS de Lyon, 69364 Lyon Cedex 07, France |
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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|