An Optimal Scheduling Algorithm for Fork-Join Task Graphs
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    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.

    Reference
    Related
    Cited by
Get Citation

李庆华,阮幼林,刘干,蒋盛益,杨世达.一个调度Fork-Join任务图的最优算法.软件学报,2005,16(5):684-690

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 07,2003
  • Revised:July 21,2004
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063