树形网格任务调度方法研究

论文摘要

随着网格技术的深入研究与发展,地理上分布的异构资源可以通过网格工具整合成一个完整的计算平台。高效的网格任务调度成为研究的热点和亟待解决的问题,其难点在于综合考虑任务间数据依赖,网格环境的拓扑结构和异构性特征对于调度的影响。有向无环图(directed acyclic graph)在并行计算任务调度领域中已有大量应用,它使用结点来代表计算任务,并且使用有向边来表示任务间的数据依赖和任务之间的通信量。关键路径是任务调度图中最长的执行路径,本文对传统的有向无环图模型进行了修改,并在表调度技术中使用动态关键路径方法来有效降低整体任务图的调度长度。本文首先提出了一种基于有向无环图模型的树形异构网格静态任务调度启发式算法,该算法考虑了任务图中的数据依赖和网格的异构性,在每一个调度过程中,该算法使用动态关键路径来选择任务结点,并且采取最早完成时间策略来完成处理机映射。在总结了大量实验结果的基础上,针对任务间通信占用率较大的情况,本文提出了一种基于任务预分配方式的新算法。在实验中,本文对两种算法进行了实例分析和计算模拟,结果证明,两种算法都可以得到预期的调度结果,在指定的条件下,新算法可以有效降低计算的复杂度。最后本文对做出了工作总结,并对进一步的改进方向进行了简单讨论。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景和意义
• 1.2 国内外的研究现状
• 1.3 本文的主要工作
• 1.4 本文的组织结构
• 第2章 网格与任务调度
• 2.1 网格计算
• 2.1.1 网格的本质特征
• 2.1.2 OGSA网格体系结构
• 2.1.3 网格的五层结构
• 2.1.4 网格发展现状
• 2.2 网格调度问题
• 2.3 两种任务调度技术
• 2.3.1 表调度技术
• 2.3.2 聚类技术
• 2.4 网格计算中常见的任务调度算法
• 第3章 树形网格任务调度模型研究
• 3.1 DAG模型的引入
• 3.2 DAG模型描述
• 3.3 处理机描述
• 3.3.1 处理机模型定义
• 3.3.2 处理机拓扑结构
• 3.4 改进的DAG模型
• 第4章 树形网格任务调度算法
• 4.1 关键问题分析
• 4.2 一种基于动态关键路径的调度方法
• 4.2.1 顺序选择DAG图中的任务结点
• 4.2.2 任务间消息在处理机之间路由与传递
• 4.2.3 对所选择的任务结点进行处理机映射
• 4.3 特定条件下对调度算法的改进
• 第5章 实验及结果分析
• 5.1 实验样例DAG任务图模型和样例树形处理机结构
• 5.2 算法4.5调度实例
• 5.3 算法4.6调度实例
• 5.4 两种调度算法实验总结
• 第6章 结论
• 参考文献
• 致谢