Efficient scheduling techniques and performance evaluation methods for heterogeneous distributed computing systems

This dissertation focuses on developing new and efficient scheduling techniques for heterogeneous distributed computing systems in particular Multiple-Instruction-Multiple-Data (MIMD) based systems. Heterogeneous systems consist of machines of many different types and the networks that connect the machines are, in general, non-uniform. Heterogeneous systems have the potential to provide low cost and high performance computing whenever computational applications can be broken into tasks that can be distributed to the various machines for parallel execution. This potential cannot be realized without an efficient scheduling algorithm. The general problem of obtaining an optimal schedule in a heterogeneous system is well known to be infeasible except for trivial cases.; This dissertation proposes several scheduling algorithms (both static and dynamic) that provide approximately optimal solutions for various types of scheduling problems in heterogeneous systems. The proposed scheduling algorithms combine a random ordering technique with an efficient heuristic for transforming task order into a schedule. The formulation of these scheduling algorithms considers various forms of the heterogeneous scheduling problem including independent tasks, interdependent tasks that exchange data, unknown task execution time and scalability.; A detailed comparison of the proposed algorithms with existing known algorithms is presented through various experimental results that clearly demonstrate the features and advantages of these proposed methods. The algorithms have been implemented and tested in a simulated environment and in a real distributed system at the University of Idaho and the Idaho National Engineering and Environmental Laboratory, Idaho Falls. A dynamic feedback mechanism is being included in our algorithm that provides for improved system performance when the task execution time estimates are not precisely known a priori. This dissertation also proposes a generalized architecture for scalability to very large heterogeneous systems. It is hoped that in the future even greater performance may be achieved by applying these algorithms to many other parallel applications and by continued research in scheduling methods that exploit the potential of heterogeneous computing systems.