A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems

TLDR

Heterogeneous computing environments can handle large, diverse meta‑tasks, but mapping them is NP‑complete and selecting the best heuristic is difficult because prior studies use differing assumptions. This study offers a common basis for comparison and insights into when one technique outperforms another. The authors implemented and evaluated eleven mapping heuristics—opportunistic load balancing, user‑directed assignment, fast greedy, min‑min, max‑min, greedy, genetic algorithm, simulated annealing, genetic simulated annealing, tabu, and A*—under a unified set of assumptions and compared their results.

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.