Task Scheduling Algorithm for Interconnection Constrained Network of Heterogeneous Processors

摘要

Efficient scheduling of parallel programs represented by a-cyclic directed graph (DAG), with or without duplication, is one of the most challenging NP-complete problems in parallel and distributed systems. Because of its key importance, this problem has been extensively studied and various heuristics algorithms have been proposed. However, most of the available algorithms are designed under the assumption of unbounded availability of fully connected processors and lie in high complexity range. In this paper, we propose a new task scheduling algorithm, namely, Highly Communicating and Dependant Based Task Scheduling (HCDBTS) algorithm for scheduling DAG structured applications onto interconnection constrained network of heterogeneous processors. Our objective is to develop an efficient scheduling algorithm that will deliver a good schedule i.e., minimize the completion time of the application and still work with limited number of interconnection constrained processors. We compared the performance of HCDBTS algorithm against the Heterogeneous Earliest Finish Time (HEFT) and the Heterogeneous Critical Node First (HCNF) algorithms by simulation. Our extensive simulation studies based on both randomly generated task graphs and the task graphs of some real applications such as Fast Fourier Transformations, Gaussian Elimination, LU Decom-position and Laplace Transformation, reveal that our scheduling algorithm significantly surpass HEFT and HCNF in schedule length and speedup ratio.