学位论文 > 优秀研究生学位论文题录展示

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

作　者: 黄俊一
导　师: 乔建忠
学　校: 东北大学
专　业: 计算机软件与理论
关键词: 网格计算异构静态任务调度动态关键路径预分配
分类号: TP393.02
类　型: 硕士论文
年　份: 2008年
下　载: 26次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

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

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

内容摘要

全文目录

相似论文