Abstract
Diverse sets of resources interconnected with a high-speed network provide a new computing platform, called the heterogeneous computing system, which can support the execution of computationally intensive parallel and distributed application programs. Efficient task scheduling algorithm is critical for application programs to achieve high performance in heterogeneous computing systems. Although a large number of scheduling heuristics have been presented in the literature, most of them are mainly for the systems with homogeneous processors. In this thesis, we present a novel task scheduling algorithm, heterogeneous task duplication scheduling (HTDS), for a bounded number of heterogeneous processors with an objective to meet high performance. The HTDS algorithm uses task duplication method to decrease the communication overhead and to minimize the schedule length of application programs. To evaluate the performance of the proposed task scheduling algorithm, we have developed a simulator that contains a parametric graph generator for generating weighted directed acyclic graphs with various characteristics. We have implemented the HTDS along with three task scheduling algorithms, HEFT, LDBS1, and LDBS2, on the simulator. The simulation results show that our task scheduling algorithm outperforms other algorithms in terms of speedup.