A New Algorithm for Scheduling Fork-Join Task Graph
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

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

    Task scheduling is one of the crucial factors influencing the efficiency of a network of workstations. Fork-Join task graphs can represent many parallel structures. All of the existing algorithms which schedule Fork-Join task graphs have ignored the problem that communications cannot be executed in parallel in non-fully-connected NOW, and some of algorithms with high efficiency even did not take the problem of how to save the processors into account. In this paper, a new static task scheduling algorithm called TSA_FJ is proposed,which is based on task duplication and trying to synthetically take the problems of schedule length shortening,unparallel communications and processor saving into account.By randomly generating the task execution time and communication time,several fork-Join task graphs are got and the scheduling results of TSA_FJ are compared with that of other algorithms for the generated task graphs.It shows that TSA_FJ algorithm has the shortest scheduling length and uses much less processors.It is much suitable to non-fully-connected NOW.

    Reference
    Related
    Cited by
Get Citation

刘振英,方滨兴,姜誉,张毅,赵宏.一个调度Fork-Join任务图的新算法.软件学报,2002,13(4):693-697

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:April 04,2000
  • Revised:August 21,2001
  • 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