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

• 作者: 周佳祥 郑纬民
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 任务调度 有向无环图 任务群 前驱任务 最优前驱任务 机群系统
• 年，卷（期）: 2000,（8）
• 页码范围: 1097-1104
• 页数: 8页
• 分类号: TP316
• 字数: 5154字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郑纬民	清华大学计算机科学与技术系	181	2698	27.0	46.0
2	周佳祥	清华大学计算机科学与技术系	2	79	2.0	2.0