The Fork-Join structure is one of the basic modeling structures for parallel processing. Although some algorithms are able to find an optimal schedule under certain conditions, they ignore to economize processors and minimize the total completion time. This paper presents a Task Duplication based Balance Scheduling(TDBS)algorithm which can generate an optimal schedule for fork-join task graph with a complexity of O(vq+vlogv), where v and q are the number of tasks and processors respectively. By considering workload and idle time slots of the used processors, TDBS algorithm tries to assign tasks to scheduled processors and maximize their utilization. Simulation results show that TDBS algorithm has better speedup and efficiency than other compared algorithms. Therefore,TDBS algorithm is a viable option for practical high performance applications.
[1]Yang T, Gerasoulis A. DSC: Scheduling parallel tasks on an unbounded number of processors. IEEE Trans. on Parallel and Distributed Systems, 1994,5(9):951-967.
[2]Kwok YK, Ahmad I. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors, IEEE Trans. on Parallel and Distributed Systems, 1996,7(5):506-521.
[3]Palis MA, Jing-Chiou Liou, Wei DSL. Task clustering and scheduling for distributed memory parallel architecture. IEEE Trans. on Parallel and Distributed Systems, 1996,7(1):46-55.
[4]Ahmad I, Kwok YK. On exploiting task duplication in parallel program scheduling. IEEE Trans. on Parallel and Distributed Systems, 1998,9(9):872-891.
[5]Darbha S, Agrawal DP. Optimal scheduling algorithm for distributed-memory machines. IEEE Trans. on Parallel and Distributed Systems, 1998,9(1):87-94.
[6]Chan-Ik Park, Tae-Young Choe. An optimal scheduling algorithm based on task duplication. IEEE Trans. on Computers, 2002,51 (4):444-448.
[7]Liu ZY, Fang BX, Jiang Y, Zhang Y, Zhao H. A new algorithm for scheduling fork-join task graph. Journal of Software,2002,13(4):693-696 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/13/693.pdf
[8]Liu ZY, Fang BX, Zhang Y. TSA-OT: An algorithm scheduling an out-tree DAG. Chinese Journal of Computers, 2001,24(4):390-394 (in Chinese with English abstract).
[9]Andrei Radulescu, Arjan JC, van Gemund. Low-Cost task scheduling for distributed-memory machines. IEEE Trans. on Parallel and Distributed Systems, 2002,13(6):648-658.