A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems

• Published in: Journal of parallel and distributed computing 2001-06, Vol.61 (6), p.810-837
• Main Authors: Braun, Tracy D, Siegel, Howard Jay, Beck, Noah, Bölöni, Ladislau L, Maheswaran, Muthucumaru, Reuther, Albert I, Robertson, James P, Theys, Mitchell D, Yao, Bin, Hensgen, Debra, Freund, Richard F
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Exact sciences and technology; Genetic Algorithm; heterogeneous computing; mapping heuristics; metatasks; simulated annealing; Software; static matching; Tabu search
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1006/jpdc.2000.1714

Mixed-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 computational requirements. HC environments are well suited to meet the computational demands of large, diverse groups of tasks. The problem of optimally 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 environment, however, remains a difficult problem, because comparisons are often clouded by different underlying assumptions in the original study of each heuristic. Therefore, a collection of 11 heuristics from the literature has been selected, adapted, implemented, and analyzed 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 metatask (i.e., a set of independent, noncommunicating tasks) is being mapped and that the goal is to minimize the total execution time of the metatask. The 11 heuristics examined are Opportunistic Load Balancing, Minimum Execution Time, Minimum Completion Time, Min–min, Max–min, Duplex, 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 out-perform another. The evaluation procedure is specified, the heuristics are defined, and then comparison results are discussed. It is shown that for the cases studied here, the relatively simple Min–min heuristic performs well in comparison to the other techniques.