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

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

论文摘要

随着网格技术的深入研究与发展,地理上分布的异构资源可以通过网格工具整合成一个完整的计算平台。高效的网格任务调度成为研究的热点和亟待解决的问题,其难点在于综合考虑任务间数据依赖,网格环境的拓扑结构和异构性特征对于调度的影响。有向无环图(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章 结论
  • 参考文献
  • 致谢
  • 相关论文文献

    • [1].超图在网格任务调度中的应用[J]. 电子世界 2014(11)
    • [2].遗传算法在网格任务调度的应用研究[J]. 计算机仿真 2011(11)
    • [3].基于遗传算法的网格任务调度方法研究[J]. 舰船科学技术 2009(11)
    • [4].基于改进遗传算法的网格任务调度模型构建[J]. 软件导刊 2017(01)
    • [5].网格任务调度问题求解的萤火虫算法[J]. 重庆邮电大学学报(自然科学版) 2015(05)
    • [6].混沌粒子优化算法在网格任务调度的应用[J]. 计算机仿真 2012(10)
    • [7].基于改进遗传算法的网格任务调度研究[J]. 计算机科学 2010(07)
    • [8].基于实数编码遗传算法的网格任务调度[J]. 吉林省教育学院学报(上旬) 2013(01)
    • [9].基于改进免疫遗传算法的网格任务调度[J]. 河北工程大学学报(自然科学版) 2013(02)
    • [10].数据网格任务调度模拟器的设计[J]. 计算机应用研究 2011(11)
    • [11].基于混合蚁群算法的网格任务调度[J]. 计算机工程 2010(03)
    • [12].网格任务调度模型的研究[J]. 科技广场 2010(03)
    • [13].一种基于蚁群算法动态均衡的网格任务调度[J]. 东北大学学报(自然科学版) 2010(05)
    • [14].基于遗传算法的网格任务调度研究[J]. 山西电子技术 2009(01)
    • [15].网格任务调度机制的研究[J]. 现代计算机(专业版) 2008(04)
    • [16].改进蛙跳算法的网格任务调度优化模型[J]. 吉林大学学报(信息科学版) 2018(02)
    • [17].混合算法在网格任务调度中的应用研究[J]. 计算机仿真 2011(09)
    • [18].基于资源预测的网格任务调度模型[J]. 计算机应用 2010(09)
    • [19].改进遗传算法在网格任务调度中的应用[J]. 微型机与应用 2010(18)
    • [20].基于遗传算法与蚁群算法动态融合的网格任务调度[J]. 计算机应用与软件 2009(07)
    • [21].一种基于预测和激励机制的网格任务调度框架[J]. 计算机应用与软件 2008(10)
    • [22].基于改进遗传算法的网格任务调度[J]. 信息通信 2016(03)
    • [23].基于小生境和自适应遗传算法的网格任务调度优化研究[J]. 计算机测量与控制 2013(02)
    • [24].基于动态资源预测的遗传算法网格任务调度方案研究[J]. 硅谷 2009(21)
    • [25].基于自适应遗传算法的网格任务调度优化[J]. 吉林大学学报(理学版) 2015(02)
    • [26].一种基于蚁群算法的网格任务调度方法[J]. 微处理机 2008(02)
    • [27].基于动态负载均衡策略的网格任务调度优化模型和算法[J]. 计算机应用 2008(11)
    • [28].基于云模型的网格任务调度遗传算法研究[J]. 电子科技大学学报 2012(06)
    • [29].基于小生境遗传算法的网格任务调度[J]. 计算机工程 2010(21)
    • [30].基于改进遗传算法的网格任务调度[J]. 解放军理工大学学报(自然科学版) 2012(04)

    标签:;  ;  ;  ;  ;  

    树形网格任务调度方法研究
    下载Doc文档

    猜你喜欢