首页 | 本学科首页   官方微博 | 高级检索  
     

基于DAG图解-重构的机群系统静态调度算法
引用本文:周佳祥,郑纬民. 基于DAG图解-重构的机群系统静态调度算法[J]. 软件学报, 2000, 11(8): 1097-1104
作者姓名:周佳祥  郑纬民
作者单位:清华大学计算机科学与技术系,北京,100084
基金项目:本文研究得到国家自然科学基金(No.69873023)、国家863高科技项目基金(No.863- 306-ZD-02)资助.
摘    要:机群系统静态任务调度是NP-完全问题,通常的算法是通过一些启发式算法得到多项式次优 解.该文提出的图解-子图重构算法实现了对分布在有向无环图(directed acyclic graph, 简称DAG)上的并行任务的快速有效调度.该算法的复杂性为O(log|V|×(|V|+| E|)),采用递归方法实现了对任务图的有效分解和子图重构,生成任务群,完成任务调度,并 且初步实现了对处理机的优化.通过实例分析以及与其他启发式调度算法的性能比较,证明该 算法是一种快速、有效、可

关 键 词:任务调度  有向无环图  任务群  前驱任务  最优前驱任务  机群系统.
收稿时间:1999-06-16
修稿时间:1999-08-30

A Static Scheduling Algorithm on DAG Partition-Reconfiguration in the Network of Workstations
ZHOU Jia-xiang and ZHENG Wei-min. A Static Scheduling Algorithm on DAG Partition-Reconfiguration in the Network of Workstations[J]. Journal of Software, 2000, 11(8): 1097-1104
Authors:ZHOU Jia-xiang and ZHENG Wei-min
Affiliation:Department of Computer Science and Technology Tsinghua University Beijing 100084
Abstract:Static task scheduling on network of workstations is well-known to be an NP-co mplete problem in a strong sense. Some heuristic algorithms have been proven to be sub-optimal under some restrictive conditions. In this paper, the authors pr esent a heuristic algorithm named DAG (directed acyclic graph) partition and sub -graph reconfiguration algorithm, which is a fast and effective one used in par allel task scheduling. The complexity of this algorithm is O(log|V|I1518 ×(|V|+|E|)). It adopts recursion to implement DAG partition and sub-graph re configuration, then builds task clusters to carry out the task scheduling. At th e same time, it even optimizes the number of processors to some degree for it ha s not been solved before. The performance has been observed in a representative example compared with other existing scheduling schemes in terms of several valu able factors. The experimental results show that this algorithm is feasible.
Keywords:Task scheduling   DAG (directed acyclic graph)   task cluster   predecessor task   o ptimal predecessor task   NOW (network of workstations).
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号