Heterogeneous distributed computing: Off-line mapping heuristics for independent tasks and for tasks with dependencies, priorities, deadlines, and multiple versions

Heterogeneous computing (HC) environments composed of interconnected machines with varied computational capabilities are well suited to meet the computational 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 environment has been shown, in general, to be NP-complete. Therefore, the development of heuristic techniques to find near-optimal solutions is required. This research focuses on the static HC mapping problem (i.e., mapping is done off-line in a predictive manner) and considers several different aspects of this problem. A taxonomy for HC mapping heuristics is presented to help researchers classify and distinguish among different issues impacting mapping heuristic execution. The taxonomy is divided into three sections based on application 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 heterogeneous 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 machines). 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