If you are experiencing problems downloading PDF or HTML fulltext, our helpdesk recommend clearing your browser cache and trying again. If you need help in clearing your cache, please click here . Still need help? Email help@ingentaconnect.com

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

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.


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. Copyright 2001 Academic Press.

Keywords: A*; Genetic Algorithm; Tabu search; heterogeneous computing; mapping heuristics; metatasks; simulated annealing; static matching

Document Type: Research Article

Affiliations: 1: School of Electrical and Computer Engineering, Purdue University, West Lafayette, Indiana, 47907-1285 2: CPlane Inc., 897 Kifer Road, Sunnyvale, California, 94086 3: Department of Computer Science, University of Manitoba, Winnipeg, MB, R3T 2N2, Canada 4: Motorola, 6300 Bridgepoint Parkway, Bldg. #3, MD:OE71, Austin, Texas, 78730 5: Department of Electrical Engineering and Computer Science, University of Illinois at Chicago, Chicago, Illinois, 60607-7053 6: OpenTV, 401 East Middlefield Road, Mountain View, California, 94043 7: NOEMIX, 1425 Russ Boulevard, Suite T-110, San Diego, California, 92101

Publication date: June 1, 2001

Related content



Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more