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

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