相关任务图的均衡动态关键路径调度算法

被引：23

作者：

石威

郑纬民

机构：

[1] 清华大学计算机科学与技术系高性能计算技术研究所!北京

来源：

计算机学报 | 2001年 / 09期

关键词：

表调度; 动态关键路径; 调度长度;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

表调度 (list scheduling)法是解决任务调度问题的较为有效的方法 .该文对两个典型的表调度算法——MCP算法和 ETF算法进行了分析 ,发现它们均存在着一定的不足 .文中提出了一个更好的表调度算法 BDCP,它采用动态关键路径技术并均衡考虑关键路径结点和非关键路径结点 ,使得对相关任务图调度长度影响最大的就绪结点能够被优先调度 ,从而极大地缩短了任务图的调度长度 .分析和实验结果表明 ,BDCP算法要优于 MCP和ETF算法

引用

页码：991 / 997

页数：7

共 11 条

[1]

Hypertool : A programming aid for message-passing systems. Wu M Y,Gajski D D. IEEE Transactions on Parallel and Distributed Systems . 1990

[2]

Scheduling precedence graphs in systems with interprocessor communication times. Hwang J J,Chow Y C,Anger F D,Lee C Y. SIAM Journal on Computing . 1989

[3]

Dynamic critical -path scheduling: An effective technique for allocating task graphs onto muti -processors. Kwok Y-K,Ahmad I. IEEE Transactions on Parallel and Distributed Systems . 1996

[4]

A shortest tree algorithm for optimal assignments across space and time in distributed processor systems. Bokhari S. IEEE Transactions on Software Engineering . 1981

[5]

Parallel Gaussian elimination on an MIMD computer. Cosnard M,Marrakchi M,Robert Y,Trystram D. Parallel Computing . 1988

[6]

Optimization and approximation in deterministic sequencing and scheduling: A survey. Graham R L,Lawler E L,Lenstra J K,Rinnoy A H G. Annals of Discrete Mathematics . 1979

[7]

A preliminary evaluation of the critical path method for scheduling tasks on multiprocessor systems. Kohler W H. IEEE Transactions on Communications . 1975

[8]

Benchmarking the task graph scheduling algorithm. Kwok Y K,Ahmad I. In: Proc 12th International Parallel Processing Symposium, Orlando, Florida, USA . 1998

[9]

Deterministic processor scheduling. Gonzalez M J. ACM Computing Surveys . 1977

[10]

Computerandjobshopschedulingtheory. CoffmanEG. . 1976

← 1 2 →