A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems
Authors:
- H.J. SiegalHSH.J. Siegal
- N. BeckNBN. Beck
- L.L. BoloniLBL.L. Boloni
- M. MaheswaranMMM. Maheswaran
- A.I. ReutherARA.I. Reuther
- J.P. RobertsonJRJ.P. Robertson
- TheysTHTheys
- Bin YaoBYBin Yao
- D. HensgenDHD. Hensgen
- R.F. FreundRFR.F. Freund
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10975209,p. 15-29
Abstract
Heterogeneous computing (HC) environments are well suited to meet the computational demands of large, diverse groups of tasks (i.e., a meta-task). The problem of mapping (defined as matching and scheduling) these tasks onto the machines of an HC environment has been shown, in general, to be NP-complete, requiring the development of heuristic techniques. Selecting the best heuristic to use in a given environment, however, remains a difficult problem, because comparisons are often clouded by different underlying assumptions in the original studies of each heuristic. Therefore, a collection of eleven heuristics from the literature has been selected, implemented, and analyzed under one set of common assumptions. The eleven heuristics examined are opportunistic load balancing, user-directed assignment, fast greedy, min-min, max-min, greedy, genetic algorithm, simulated annealing, genetic simulated annealing, tabu, and A*. This study provides one even basis for comparison and insights into circumstances where one technique will outperform another. The evaluation procedure is specified, the heuristics are defined, and then selected results are compared.Keywords
This publication has 18 references indexed in Scilit:
- An overview of MSHN: the Management System for Heterogeneous Networks2003
- A taxonomy for describing matching and scheduling heuristics for mixed-machine heterogeneous computing systems2002
- Optimal task assignment in heterogeneous distributed computing systemsIEEE Concurrency, 1998
- Parallel genetic simulated annealing: a massively parallel SIMD algorithmIEEE Transactions on Parallel and Distributed Systems, 1998
- Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based ApproachJournal of Parallel and Distributed Computing, 1997
- Tabu Search1997
- A distributed heterogeneous supercomputing management systemComputer, 1993
- Heterogeneous computing: challenges and opportunitiesComputer, 1993
- Optimization by Simulated AnnealingScience, 1983
- Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical ProcessorsJournal of the ACM, 1977