Amal Khalifa, Reda Ammar, Tahany Fegrany, and Mohammed Fahmy Tolba
Heterogonous computing, dynamic mapping, batch-mode algo-rithms, preemptive allocation, task migration, residual time
Heterogeneous computing (HC) systems use different types of machines, networks and interfaces to coordinate the execution of various task components that have different computational require- ments. This variation in tasks needs as well as machine capabilities has created a very strong need for developing mapping/scheduling techniques especially for the HC community. The mapping prob- lem can be stated shortly as deciding on which task should be moved to where and when, to optimize some system performance criteria. Mapping problems are known to be NP-complete except under a few special situations. The existing heuristics for mapping tasks in HC systems works either statically or dynamically. This distinction is based on the time at which the mapping decisions are made. Although the principal advantage of the static mapping is its simplicity, it fails to adjust to changes in the system state. Therefore, dynamic algorithms are considered more suitable for HC environments, where the machine allocation process is done at run time. In general, dynamic mapping techniques can be grouped into two categories: online (immediate) mode and batch-mode heuristics. In this paper, we provide a detailed discussion for six batch mode algorithms. Four new algorithms and the other two exist in the literature. Simulation studies are performed to compare their per- formance with a variety of system heterogeneity modes and different task arrival rates. The experimental results helped to reveal which algorithm to use in a given heterogeneous environment.
Important Links:
Go Back
