Scheduling strategies for master-slave tasking on heterogeneous processor platforms
- 8 March 2004
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 15 (4), 319-330
- https://doi.org/10.1109/tpds.2004.1271181
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.Keywords
This publication has 10 references indexed in Scilit:
- Autonomous protocols for bandwidth-centric scheduling of independent-task applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Task scheduling algorithms for heterogeneous processorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- An enabling framework for master-worker applications on the Computational GridPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scheduling multi-component applications in heterogeneous wide-area networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Master/slave computing on the GridPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor GridsLecture Notes in Computer Science, 2002
- Bandwidth-centric allocation of independent tasks on heterogeneous platformsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Parallel processor configuration design with processing/transmission costsIEEE Transactions on Computers, 2000
- Task allocation on a network of processorsIEEE Transactions on Computers, 2000
- Optimizing computing costs using divisible load analysisIEEE Transactions on Parallel and Distributed Systems, 1998