![]() | Only 14 pages are availabe for public view |
Abstract Distributed Computing System (DCS) is emerging as a viable alternative to parallel computing system for executing computationally intensive applications. It has the potential to provide low cost and high performance computing environment for a complex application that partitioned into tasks by task partitioning algorithm and formed as Directed Acyclic Graph (DAG). Several task scheduling algorithms have been proposed for homogeneous and heterogeneous distributed computing systems. They are broadly classified into two categories namely; static and dynamic task scheduling. Static task scheduling algorithms are categorized as List-scheduling, Clustering, and Task Duplication-based algorithms. List-scheduling algorithms provide sub-optimal schedule with minimum scheduling overhead. B-level algorithm is one of the most efficient list scheduling algorithms. In this thesis, two new list-scheduling algorithms called Leveled DAG Prioritized Task (LDPT) and Leveled DAG Critical Task First (LDCTF) have been developed to improve the performance of homogeneous DCS which consists of bounded number of completely connected processors. First, LDPT algorithm is developed to improve the performance of DCS compared to the B-level algorithm. Then, ELDPT is developed to enhance the performance of LDPT. Finally, LDCTF algorithm is proposed to optimize the performance of LDPT algorithm. The performance of the proposed algorithms (LDPT, LDCTF) is evaluated by simulation and compared with each other and with the B-level algorithm. The experimental results show that the LDPT algorithm outperforms the B-level algorithm while the LDCTF algorithm outperforms both the LDPT and B-level algorithms in terms of schedule length, speedup, and efficiency. |