MS, Colorado State University, May 2006
Co-Major Professors: H. J. Siegel and Anthony A. Maciejewski
Heterogeneous parallel and distributed computing systems may operate in an environment where certain system performance features degrade due to unpredictable circumstances. Robustness can be defined as the degree to which a system can maintain a specified level of performance in the presence of parameter values different from those assumed.
In this thesis, the dynamic mapping of tasks onto machines for two different problem environments is studied. A model for a heterogeneous environment is developed for each type of mapping problem to allow the evaluation of mapping heuristics through simulation.
This research develops a model for quantifying robustness in a dynamic environment. It also presents a mathematical expression of robustness for a dynamic environment where actual task execution times may deviate from the estimated execution times. Several heuristic solutions to the problem are presented that utilize this expression of robustness to influence mapping decisions. These solutions are then compared to a bound on the highest attainable value of the system performance parameter for the described system.
In the first environment, mapping of independent tasks to machines is considered such that the makespan (completion time for the entire set of tasks) is minimized, while still guarantying a certain level of robustness. Ten different dynamic heuristics are examined and their performance is compared to a mathematical lower bound on makespan.
The second environment considers mapping of independent tasks to machines so as to maximize the robustness while maintaining a constraint on the allowable makespan for the resource allocation. Five different dynamic heuristics are examined for their ability to maximize robustness while still completing all the tasks within an overall makespan constraint. The performance of the proposed heuristics is also compared to a theoretical upperbound on robustness.