A Comparison Study of Static Mapping Heuristics for a Class of Meta-tasks on Heterogeneous Computing Systems

Heterogeneous computing (HC) environments are well suited to meet the computational demands of large diverse groups of tasks (i. e., a meta- task). The prob lem of mapping (defi ned as matching and scheduling ) these tasks onto the machines of an HC environment has been shown in general to be NP- complete, requir ing the development of heuristic techniques. Selecting the best heuristic to use in a given environment , how ever, remains a di cult problem because comparisons are often clouded by di erent 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 exam ined are Opportunistic Load Balancing, User- Directed Assignment, Fast Greedy, Min min Max- min, Greedy, Genetic Algorithm, Simulated Annealing , Genetic Sim ulated Annealing, Tabu , and A*. This study provides one even basis for comparison and insights into circum stances where one technique will outperform another . The evaluation procedure is speci ed the heuristics are defined and then selected results are compared .