Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems

Authors: Maheswaran M.¹; Ali S.²; Siegel H.J.²; Hensgen D.³; Freund R.F.⁴

Source: Journal of Parallel and Distributed Computing, Volume 59, Number 2, November 1999 , pp. 107-131(25)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

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, immediate mode and batch mode heuristics. Three new heuristics, one for batch mode and two for immediate mode, are introduced as part of this research. Simulation studies are performed to compare these heuristics with some existing ones. In total five immediate mode heuristics and three batch mode heuristics are examined. The immediate mode dynamic heuristics consider, to varying degrees and in different ways, task affinity for different machines and machine ready times. The batch mode dynamic heuristics consider these factors, as well as aging of tasks waiting to execute. The simulation results reveal that the choice of which dynamic mapping heuristic to use in a given heterogeneous environment depends on parameters such as (a) the structure of the heterogeneity among tasks and machines and (b) the arrival rate of the tasks. Copyright 1999 Academic Press.

Language: English

Document Type: Research article

Affiliations: 1: Department of Computer Science, University of Manitoba, Winnipeg, MB, R3T 2N2, Canada 2: School of Electrical and Computer Engineering, Purdue University, West Lafayette, Indiana, 47907-1285 3: Department of Computer Science, Naval Postgraduate School, Monterey, California, 93940 4: NOEMIX Inc., 1425 Russ Boulevard, Suite T-110, San Diego, California, 92101

Publication date: 1999-11-01