Abstract
ABSTRACT Il'lixed-machine heterogeneous computing (HC) environments utilize a distributed suite of different high-performance machines, interconnected with high-speed links to perform different computationally intensive applications that have diverse comput ational requirements. HC environments are well suited to meet thl: computational dell-tands of large, diverse groups of tasks. The problem of mapping (defined as matching and scheduling) these tasks onto the machines of a distributed 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 enviroi~menth, owever, remains a difficult problem, because comparisons are often clouded by different underlying assumptions in the original studies of each heuristic. There~fore; a collection of eleven heuristics from the literature has been selected: a,dapted, in~plementeda, nd anaiyzed under one set of common assumptions. It is assumed that the heuristics derive a, mapping statically (i.e., off-line). It is also assumed that a meta-task (i.e., a set of independent, non-communicating tasks) is being mapped, and that the goal is to minimize the total execution time of the metla-task. The eleven heuristics examined are Opportunistic Load Balancing, Minimum Execution Time, MininLlum Clompletion Time, Min-min, hllax-min, Duplex? Genetic i-Ilgorithm, Simulated Annealing, Genetic Simulat.ed .Annealing, Tabu, and Ax. This study provides one even basis for comparisor] and insights into circumstances where one technique will out perform another. The evaluation procedure is specified, the heuristics are defined, and then comparison results are discussed. It is shown that for the ca.ses studied here, the relat,ively simple Min-min heuristic performs well in comparison to the other techniques.
Date of this Version
March 2000