A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems

Mixed-machine heterogeneous computing (HC) environments utilize a distribut ed suite of different high-performance machines, interconnected with high-s peed links, to perform different computationally intensive applications tha t have diverse computational requirements. HC environments are well suited to meet the computational demands of large, diverse groups of tasks. The pr oblem of optimally mapping (defined as matching and scheduling) these tasks onto the machines of a distributed HC environment has been shown, in gener al, to be NP-complete. requiring the development of heuristic techniques. S electing the best heuristic to use in a given environment, however, remains a difficult problem, because comparisons are often clouded by different un derlying assumptions in the original study of each heuristic. Therefore, a collection of ii heuristics: From the literature has been selected, adapted , implemented, and analyzed under one set of common assumptions. It is assu med that the heuristics: derive a mapping statically (i.e., off-line). It i s also assumed that a metatask ( i.e., a set of independent. noncommunicati ng tasks) is bring mapped and that tile goal is to minimize the total execu tion time of the metatask. The 11 heuristics examined are Opportunistic Loa d Balancing, Minimum Execution Time, Minimum Completion Time, Min-min, Max- min. Duplex. Genetic Algorithm, Simulated Annealing, Genetic Simulated Anne aling, Tabu, and A*. This study provides one even basis for comparison and insights into circumstances where one technique will outperform another. Th e evaluation procedure is specified, the heuristics are defined, and then c omparison results are discussed. It is shown that for the cases studied her e, the relatively simple Min-min heuristic performs M;ell in comparison to the other techniques. (C) 2001 Academic Press.