一个调度Fork-Join任务图的新算法

A New Algorithm for Scheduling Fork-Join Task Graph

任务调度是影响工作站网络效率的关键因素之一.Fork-Join任务图可以代表很多并行结构,但其他已有调度Fork-Join任务图算法忽略了在非全互连工作站网络环境中通信之间不能并行执行的问题,有些效率高的算法又没有考虑节省处理器个数的问题.因此,专门针对该任务图,综合考虑调度长度、非并行通信和节省处理器个数问题,提出了一个基于任务复制的静态调度算法TSA_FJ.通过随机产生任务的执行时间和通信时间,生成了多个Fork-Join任务图,并且采用TSA_FJ算法和其他调度算法对生成的任务图进行调度.结果表明,TSA_FJ算法的调度长度最短、使用的处理器个数最少,它更适合于非全互连的NOW环境.

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.