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

被引：8

作者：

刘振英

方滨兴

张毅

机构：

[1] 哈尔滨工业大学计算机科学与工程系!哈尔滨

[2] 哈尔滨理工大学电气与电子工程系!哈尔滨

来源：

计算机学报 | 2001年 / 04期

关键词：

任务调度; 关键路径; 调度长度; 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

← 1 →