-
题名基于DAG图解-重构的机群系统静态调度算法
被引量：7
- 1
-
-
作者
周佳祥
郑纬民
-
机构
清华大学计算机科学与技术系
-
出处
《软件学报》
EI
CSCD
北大核心
2000年第8期1097-1104,共8页
-
基金
国家自然科学基金! (No.6 98730 2 3)
国家 86 3高科技项目基金! (No.86 3- 30 6 - ZD- 0 2 )资助
-
文摘
机群系统静态任务调度是 NP-完全问题 ,通常的算法是通过一些启发式算法得到多项式次优解 .该文提出的图解 -子图重构算法实现了对分布在有向无环图 (directed acyclic graph,简称 DAG)上的并行任务的快速有效调度 .该算法的复杂性为 O(log| V| × (|V|+|E|) ) ,采用递归方法实现了对任务图的有效分解和子图重构 ,生成任务群 ,完成任务调度 ,并且初步实现了对处理机的优化 .通过实例分析以及与其他启发式调度算法的性能比较 ,证明该算法是一种快速、有效、可行的任务调度算法 .
-
关键词
机群系统
图解-子图重构算法
静态调度算法
DAG
-
Keywords
Task scheduling, DAG (directed acyclic graph), task cluster, predecessor task, optimal predecessor task, NOW (network of workstations).
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
