Ph.D., Purdue University, Aug. 2004
Co-Major Professors: H. J. Siegel and Anthony A. Maciejewski
In a distributed heterogeneous computing (HC) system, the resources have different capabilities and tasks have different requirements. To maximize the performance of the system, it is essential to assign resources to tasks (match) and order the execution of tasks on each resource (schedule) in a manner that exploits the heterogeneity of the resources and tasks. The mapping (matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques to find a near-optimal solution to this problem are required. Static mapping heuristics are used in an off-line planning phase. Dynamic mapping is performed when the arrival of a task is not known a priori or there may be changes in the system.
Three environments are investigated in this research. The first is an environment with continuously running applications and commercial off-the-shelf machines and communication links, where the goal is to find an initial static allocation of the applications onto a set of heterogeneous machines to maximize the allowable workload increase until a dynamic reallocation of resources is required. The contribution of this research is the modeling of the High Performance Distributed Computing Program (HiPer-D) environment, and the design of a variation of the simulated annealing approach.
The second environment studies a dynamic mapping problem with tasks that have priorities and multiple deadlines. The objective is to complete as many tasks as possible to achieve the most value accrued during an interval of time (value of a task depends on the priority of the task and when the task is completed). The contributions of this research are the design of eight dynamic mapping heuristics for this HC system, the comparison of the performance of the heuristics, and a method of calculating the tight upper bound for this environment.
The third environment is a dynamic ad hoc grid environment where: (a) the arrival times of tasks are not known a priori, the tasks have weighted priorities and deadlines, the tasks need inputs from other sources, and the tasks must return a result to the machine that generated the task request; (b) the clock rate of each machine can vary depending on the rate of power consumption for that machine at any point in time (dynamic voltage scaling); (c) the battery capacity of each machine is limited; and (d) the system is expected to operate for eight hours. The goal of this research was to maximize a performance measure based on the weighted priorities of the tasks that completed by their deadlines within the eight-hour session. Seven resource management techniques were designed and compared.