基于DAG图解-重构的机群系统静态调度算法

被引：31

作者：

周佳祥

郑纬民

机构：

[1] 清华大学计算机科学与技术系!北京

来源：

软件学报 | 2000年 / 08期

关键词：

任务调度; 有向无环图; 任务群; 前驱任务; 最优前驱任务; 机群系统;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

080201 [机械制造及其自动化];

摘要：

机群系统静态任务调度是 NP-完全问题 ,通常的算法是通过一些启发式算法得到多项式次优解 .该文提出的图解 -子图重构算法实现了对分布在有向无环图 (directed acyclic graph,简称 DAG)上的并行任务的快速有效调度 .该算法的复杂性为 O(log| V| × (|V|+|E|) ) ,采用递归方法实现了对任务图的有效分解和子图重构 ,生成任务群 ,完成任务调度 ,并且初步实现了对处理机的优化 .通过实例分析以及与其他启发式调度算法的性能比较 ,证明该算法是一种快速、有效、可行的任务调度算法 .

引用

页码：1097 / 1104

页数：8