EZDCP: a new static task scheduling algorithm with edge-zeroing based on dynamic critical paths

Abstract

A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.

Keywords

EZDCP / directed acyclic graph / dynamic critical path / task scheduling algorithm

References

[1] ZhongQiu-xi, XieTao. Task allocation and scheduling by computational model of coevolution[J]. Journal of Computer, 2001, 24(3): 308-313(in Chinese)

[2] CoffmanE GComputer and job-shop scheduling theory[M], 1976, New York, John Willey & Sons Publication

[3] KwokYu-kwong, AhmadI. Static scheduling algorithms for allocating directed task graphs to multiprocessors[J]. ACM Computing Surveys, 1999, 31(4): 406-471

[4] SarkarVPartitioning and scheduling parallel programs for multiprocessors[M], 1989, Cambridge, MIT Press

[5] YangTao, GerasoulisA. Dsc: Scheduling parallel tasks on an unbounded number of processors[J]. IEEE Transactions on Parallel and Distributed Systems, 1994, 5(9): 951-967

[6] KwokYu-kwong, AhmadI. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(5): 506-521

[7] GerasoulisA, YangTao. On the granularity and clustering of directed acyclic task graphs[J]. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(6): 686-701

[8] YangTao. Gerasoulis Apostolos. Pyrros: Static task scheduling and code generation for message passing multiprocessors[A]. Proceedings of 6th ACM International Conference on Supercomputing (in Chinese) [C], 1992, Washington D. C., ACM Press

[9] ShiWei, ZhengWei-min. The balanced dynamic critical path scheduling algorithm of dependent task graphs[J]. Journal of Computer, 2001, 24(9): 991-997

[10] LiuZhen-yin, FangBin-xing. Tsaot: An algorithm scheduling an outtree DAG[J]. Journal of Computer, 2001, 24(4): 390-394(in Chinese)