%0 Journal Article
%T An Optimal Scheduling Algorithm for Fork-Join Task Graphs<br>一个调度Fork-Join任务图的最优算法
%A LI Qing-Hu
%A RUAN You-Lin
%A LIU Gan
%A JIANG Sheng-Yi
%A YANG Shi-Da
%A <br>李庆华
%A 阮幼林
%A 刘干
%A 蒋盛益
%A 杨世达
%J 软件学报
%D 2005
%I 
%X 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.
%K task scheduling
%K task duplication
%K fork-join task graph
%K speedup<br>任务调度
%K 任务复制
%K Fork-Join任务图
%K 加速比
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=F532F834F6435EEF96FDF6102DA06C7A&yid=2DD7160C83D0ACED&vid=7801E6FC5AE9020C&iid=94C357A881DFC066&sid=47122BA7BE181C5A&eid=DC2727B6AC017B3F&journal_id=1000-9825&journal_name=软件学报&referenced_num=5&reference_num=11