Levelized scheduling of directed a-cyclic precedence constrained task graphs onto heterogeneous computing system

Efficient scheduling of processes onto processors of a heterogeneous computing system has always been an important and challenging area of research. The scheduling problem has been shown to be NP-complete in general cases as well as in several restricted cases. Because of its key importance, this problem has been extensively studied in the recent years and many algorithms for homogenous system and a few algorithms for heterogeneous system have been proposed in the literature. In this paper, we propose a new duplication based task scheduling algorithm, namely, levelized heavily communicating node first (LHCNF) that statically schedules directed a-cyclic precedence constrained task graphs (DAGs) onto heterogeneous computing system to minimize the schedule length or overall completion time of the application. The performance of the algorithm has been observed by its application to some practical DAGs, and by comparing it with other existing scheduling algorithms such as HEFT, LDBS1 and LDBS2 in terms of the schedule length and speedup. The comparison studies shows that LHCNF significantly outperforms HEFT, LDBS1 and LDBS2 in schedule length, speedup.