| 摘要: |
| 机群系统静态任务调度是NP-完全问题,通常的算法是通过一些启发式算法得到多项式次优 解.该文提出的图解-子图重构算法实现了对分布在有向无环图(directed acyclic graph, 简称DAG)上的并行任务的快速有效调度.该算法的复杂性为O(log|V|×(|V|+| E|)),采用递归方法实现了对任务图的有效分解和子图重构,生成任务群,完成任务调度,并 且初步实现了对处理机的优化.通过实例分析以及与其他启发式调度算法的性能比较,证明该 算法是一种快速、有效、可 |
| 关键词: 任务调度,有向无环图,任务群,前驱任务,最优前驱任务,机群系统. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家自然科学基金(No.69873023)、国家863高科技项目基金(No.863- 306-ZD-02)资助. |
|
| A Static Scheduling Algorithm on DAG Partition-Reconfiguration in the Network of Workstations |
|
ZHOU Jia-xiang,ZHENG Wei-min
|
| 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. |
| Key words: Task scheduling, DAG (directed acyclic graph), task cluster, predecessor task, o ptimal predecessor task, NOW (network of workstations). |
