Ph.D., Purdue University, May 2001
Co-Major Professors: H. J. Siegel and Anthony A. Maciejewski
Heterogeneous computing (HC) environments composed of interconnected ma chines with varied computational capabilities are well suited to meet the computa tional demands of large, diverse groups of tasks. The problem of mapping (defined as matching and scheduling) these tasks onto the machines of a distributed HC environ ment has been shown, in general, to be NPcomplete, requiring the development of heuristic techniques. This research focuses on the static HC mapping problem (i.e., mapping is done offline in a predictive manner) and considers several different as pects of this problem. A taxonomy for HC mapping heuristics is presented that can help researchers classify and distinguish among different issues impacting mapping heuristic execution. The taxonomy is divided into three sections based on applica tion models, machine models, and mapping heuristic models. Then, two different HC environments from two different regions of the taxonomy are studied. In the first HC environment, a set of independent (noncommunicating) tasks are mapped to a het erogeneous suite of machines with the goal of minimizing the time at which the last task finishes (i.e., the makespan). Eleven different mapping heuristics were selected from the literature, applied to this environment, and compared by simulation studies under one common set of assumptions. The second HC environment investigated has several additional levels of complexity. In the second HC environment, independent tasks have deadlines, priorities, and multiple versions (of differing worths), and may also be composed of communicating subtasks (which can be mapped to different ma chines). The best techniques from the first HC environment are adapted and applied to this more difficult mapping problem. Specifically, two types of genetic algorithms (GAs) are implemented, a generational GA and a steadystate GA (GENITOR), along with a stochastic version of the greedy Minmin technique. Simulation studies compare the performance of these heuristics under several different scenarios. It is shown that for the cases studied here, the GENITOR technique performs better than the other techniques presented.