Tracy D. Braun's PhD Thesis Abstract

Heterogeneous Distributed Computing: Off-line Mapping Heuristics for Independent Tasks and for Tasks with Dependencies, Priorities, Deadlines, and Multiple Versions

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 NP­complete, requiring the development of heuristic techniques. This research focuses on the static HC mapping problem (i.e., mapping is done off­line 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 (non­communicating) 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 steady­state GA (GENITOR), along with a stochastic version of the greedy Min­min 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.