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

被引:8
作者
刘振英
方滨兴
张毅
机构
[1] 哈尔滨工业大学计算机科学与工程系!哈尔滨
[2] 哈尔滨理工大学电气与电子工程系!哈尔滨
关键词
任务调度; 关键路径; 调度长度; DAG;
D O I
暂无
中图分类号
TP301.6 [算法理论];
学科分类号
摘要
对于把一个任务群调度到多个处理器的问题 ,人们往往只注重找到一个调度路径最短的算法 ,却忽略了要节省处理器 .由于 Out- Tree任务图代表分治算法的一大类问题 ,因此 ,文中专门针对该任务图 ,给出了一个基于任务复制的算法 TSA- OT.它首先分配关键路径上的任务结点 ,然后在不改变调度长度的情况下 ,把非关键路径上的结点尽可能分配到已用的处理器上 .并且 ,该算法将 Out- Tree任务图中的所有通信都化为零 .TSA- OT算法与近几年所提出的 TDS,CPFD,DCP算法之间的比较表明 ,TSA- OT算法不仅调度长度最短 ,而且采用了更少或相当个数的处理器 .
引用
收藏
页码:390 / 394
页数:5
相关论文
共 4 条
[1]  
Scheduling algorithms for parallel Gaussian elimination with communication costs. Amoura a K,Bampis E,K nig J C. IEEE Transactions on Parallel and Distributed Systems . 1998
[2]  
Dynamic critical -path scheduling: An effective technique for allocating task graphs to multiprocessors. Kwok Y K,Ahmad I. IEEE Transactions on Parallel and Distributed Systems . 1996
[3]  
On exploit task duplication in parallel program scheduling. Ahmad I,Kwok Y K. IEEE Transactions on Parallel and Distributed Systems . 1998
[4]  
Optimal scheduling algorithm for distributed-memory machines. Darbha S,Agrawal D P. IEEE Transactions on Parallel and Distributed Systems . 1998