22-05-2012, 11:12 AM
A Comparison Study of Static Mapping Heuristics for a Class of
Meta-tasks on Heterogeneous Computing Systems
Heterogeneous Computing Systems.pdf (Size: 246.62 KB / Downloads: 30)
Introduction
Mixed-machine heterogeneous computing (HC) environments utilize a distributed suite of dierent highperformance machines, interconnected with high-speed links to execute dierent computationally intensive
applications that have diverse computational requirements [10, 18, 24]. The general problem of mapping (i.e., matching and scheduling) tasks to machines has been shown to be NP-complete [8, 15]. Heuristics developed to perform this mapping function are often dicult to compare because of dierent underlying assumptions in the original studies of each heuristic [3]. Therefore, a collection of eleven heuristics from the literature has been selected, implemented, and compared by simulation studies under one set of common assumptions.
Heuristic Descriptions
The denitions of the eleven static meta-task mapping heuristics are provided below. First, some preliminary terms must be dened. Machine availability time, mat(j), is the earliest time a machine j can complete
the execution of all the tasks that have previously been assigned to it. Completion time, ct(i; j), is the machine availability time plus the execution time of task i on machine j, i.e., ct(i; j) = mat(j)+ETC(i; j).
The performance criterion used to compare the results of the heuristics is the maximum value of ct(i; j), for 0 i < t and 0 j <m, for each mapping, also known as the makespan [19]. Each heuristic is attempting to minimize the makespan (i.e., nish execution of the
meta-task as soon as possible). The descriptions below implicitly assume that the machine availability times are updated after each task
is mapped. For cases when tasks can be considered in an arbitrary order, the order in which the tasks appeared in the ETC matrix was used. Some of the heuristics listed below had to be modied from their
original implementation to better handle the scenarios under consideration. For many of the heuristics, there are control parameter values and/or control function specications that can be selected for a given implementation. For the studies here, such values and specications were selected based on experimentation and/or information
in the literature. These parameters and functions are mentioned in Section 5.
OLB: Opportunistic Load Balancing (OLB) assigns each task, in arbitrary order, to the next available machine, regardless of the task's expected execution time on that machine [1, 9, 10].
UDA: In contrast to OLB, User-Directed Assignment (UDA) assigns each task, in arbitrary order, to the machine with the best expected execution time for that task, regardless of that machine's
availability [1]. UDA is sometimes referred to as Limited Best Assignment (LBA), as in [1, 9].
Fast Greedy: Fast Greedy assigns each task, in arbitrary order, to the machine with the minimum completion time for that task [1].
Min-min: The Min-min heuristic begins with the set U of all unmapped tasks. Then, the set of minimum completion times, M = fmi : mi =
min0j<m(ct(i; j)); for each i 2 Ug, is found. Next, the task with the overall minimum completion time from M is selected and assigned to the corresponding machine (hence the name Min-min). Lastly, the newly mapped task is removed from U, and the process repeats
until all tasks are mapped (i.e., U = [1, 9, 15]. Intuitively, Min-min attempts to map as many tasks as possible to their rst choice of machine (on the basis of completion time), under the assumption that this will result in a shorter makespan. Because tasks with shorter execution times are being mapped rst, it was expected that the percentage of tasks that receive their rst choice of machine would generally be higher for Min-min than for Max-min (dened next), and this
was veried by data recorded during the simulations.
Max-min: The Max-min heuristic is very similar to Min-min. The Max-min heuristic also begins with the set U of all unmapped tasks. Then, the set of minimum completion times, M = fmi : mi = min0j<m(ct(i; j)); for each i 2 Ug, is found. Next, the task with the overall maximum completion time from M is selected and assigned to the corresponding machine (hence the name Max-min). Lastly, the newly mapped task is removed from U, and the process repeats
until all tasks are mapped (i.e., U = [1, 9, 15]. The motivation behind Max-min is to attempt to minimize the penalties incurred by delaying the scheduling of long-running tasks. Assume that the meta-task being mapped has several tasks with short execution times, and a small quantity of tasks with very long execution times.
Conclusions
The goal of this study was to provide a basis for comparison and insights into circumstances where one technique will out perform another for eleven dierent heuristics. The characteristics of the ETC matrices used as input for the heuristics and the methods used to
generate them were specied. The implementation of a collection of eleven heuristics from the literature was described. The results of the mapping heuristics were discussed, revealing the best heuristics to use in certain scenarios. For the situations, implementations, and parameter
values used here, GA was the best heuristic for most cases, followed closely by Min-min, with A* also doing well for inconsistent matrices.