An Efficient Greedy Scheduling Algorithm for Join Task Graphs in Heterogeneous Computing Systems

摘要

Many previous algorithms for scheduling task graphs are mainly for homogeneous processors and ignore the economization on processors in real applications, which leads to low efficiency in practice. In this paper we presents a new insertion based greedy algorithm, called the HGS_J algorithm for scheduling join task graphs in heterogeneous computing systems, which schedules tasks according to the critical task and tries to insert the tasks having the larger amounts of the total costs of computation and communication to used faster processors while guaranteeing shorter schedule length and so improves the scheduling performance. The simulation results show that the proposed algorithm has the characteristics of shorter schedule length and less number of used processors than other compared algorithms.