A Comparison Study of Static Mapping Heuristics for a Class of Meta-tasks on Heterogeneous Computing Systems
Braun, Tracy D.
Siegel, Howard Jay
Boloni, Ladislau L.
Reuther, Albert I.
Robertson, James P.
Theys, Mitchell D.
Freund, Richard F.
MetadataShow full item record
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 .
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Maheswaran, Muthucumaru; Shoukat Ali; Howard Jay Siegel; Hensgen, Debra; Freund, Richard F. (1999-06);Dynamic mapping (matching and scheduling) heuristics for a class of independent tasks using heterogeneous distributed computing systems are studied. Two types of mapping heuristics are considered: im- mediate mode and batch ...
Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems Maheswaran, Muthucumaru; Shoukat Ali; Howard Jay Siegel; Hensgen, Debra; Freund, Richard F. (1999);Dynamic mapping (matching and scheduling) heuristics for a class of independent tasks using heterogeneous dis- tributed computing systems are studied. Two types of map- ping heuristics are considered: on-line and batch ...
Adding intelligence to the Composite Warfare Commander - Distributed Dynamic Decision making paradigm. Wright, Brian Kenneth (Monterey, California. Naval Postgraduate School, 1991-03);The Composite Warfare Commander - Distributed Dynamic Decisionmaking (CWC-DDD) paradigm is a tool for experimentation and research into the area of command, control and communications (C3) team decisionmaking process in ...