TSA-OT:一个调度Out-Tree任务图的算法

TSA-OT: An Algorithm Scheduling An Out-Tree DAG

对于把一个任务群调度到多个处理器的问题 ,人们往往只注重找到一个调度路径最短的算法 ,却忽略了要节省处理器 .由于 Out- Tree任务图代表分治算法的一大类问题 ,因此 ,文中专门针对该任务图 ,给出了一个基于任务复制的算法 TSA- OT.它首先分配关键路径上的任务结点 ,然后在不改变调度长度的情况下 ,把非关键路径上的结点尽可能分配到已用的处理器上 .并且 ,该算法将 Out- Tree任务图中的所有通信都化为零 .TSA- OT算法与近几年所提出的 TDS,CPFD,DCP算法之间的比较表明 ,TSA- OT算法不仅调度长度最短 ,而且采用了更少或相当个数的处理器 .

As to schedule tasks to processors, an algorithm with the shortest scheduling length is always emphasized, and using as less processors as possible is always ignored in this algorithm. This paper purposes an algorithm, called TSA -OT, based on task duplication to schedule an Out Tree task graph which represents a number of divide and conquer algorithms. TSA -OT algorithm assigns the task nodes of the critical paths to processors at first, and allocates the rest nodes to the used processors as possible without changing the scheduling length. And all the communication of an Out Tree graph is zeroized in this algorithm. By the comparison among TDS, CPFD, DCP and TSA -OT algorithms, it shows that TSA -OT algorithm has the shortest scheduling length, and takes less or equal number of processors.