A taxonomy for describing matching and scheduling heuristics for mixed-machine heterogeneous computing systems
- 27 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The problem of mapping (defined as matching and scheduling) tasks and communications onto multiple machines and networks in a heterogeneous computing (HC) environment has been shown to be NP-complete, in general, requiring the development of heuristic techniques. Many different types of mapping heuristics have been developed in recent years. However, selecting the best heuristic to use in any given scenario remains a difficult problem. Factors making this selection difficult are discussed. Motivated by these difficulties, a new taxonomy for classifying mapping heuristics for HC environments is proposed (Purdue HC Taxonomy). The taxonomy is defined in three major parts: the models used for applications and communication requests; the models used for target hardware platforms; and the characteristics of mapping heuristics, Each part of the taxonomy is described, with examples given to help clarify the taxonomy. The benefits and uses of this taxonomy are also discussedKeywords
This publication has 11 references indexed in Scilit:
- A mathematical model, heuristic, and simulation study for a basic data staging problem in a heterogeneous networking environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scheduling resources in multi-user, heterogeneous, computing environments with SmartNetPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The relative performance of various mapping algorithms is independent of sizable variances in run-time predictionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Estimating the execution time distribution for a task graph in a heterogeneous computing systemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimal task assignment in heterogeneous computing systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Minimizing the application execution time through scheduling of subtasks and communication traffic in a heterogeneous computing systemIEEE Transactions on Parallel and Distributed Systems, 1997
- A survey of heterogeneous computing: concepts and systemsProceedings of the IEEE, 1996
- EM/sup 3/: a taxonomy of heterogeneous computing systemsComputer, 1995
- Allocating modules to processors in a distributed systemIEEE Transactions on Software Engineering, 1989
- A taxonomy of scheduling in general-purpose distributed computing systemsIEEE Transactions on Software Engineering, 1988