网格任务调度与优化机制研究

论文摘要

网格的目的是将地理上分布的、系统上异构的多种计算资源通过高速网络连接起来,协同解决大型应用问题,进行广域信息资源的分布共享,最终把整个因特网整合成一台超级虚拟计算机,实现计算资源、存储资源、数据资源、信息资源、知识资源、专家资源的全面共享。在网格计算中如何最有效的管理和利用巨大的网格资源来最有效的完成各种计算任务是一个重点,即网格任务调度要解决的问题。网格计算资源的异构性,非常适合具有多种内在并行性的应用执行,将应用程序调度到异构的计算节点上运行,获得最优或近优的性能指标是网格任务调度技术的目标和方向。通过建立网格任务调度模型,并在模型基础上实现任务调度,能够达到充分有效利用资源来提高任务调度性能的目的。任务调度是网格计算中的一个重要组成部分,一直是国际和国内学术界的热点研究领域。本论文的主要工作和创新性成果如下:(1)提出了一种网格任务调度模型,并在此基础上提出了一种网格优化有向超图任务调度算法GODHTS。针对传统分布式系统任务调度算法的不足,使任务调度适应网格特征,充分发挥网格优势,本文将超图理论融合网格环境特征,建立了网格任务调度基本框架模型。本文通过结合任务和资源特征,构建超图分层模型,根据无尺度与小世界理论构建调度分布结构,在此基础上建立有效的网格任务调度机制,通过网格优化有向超图的水平构形、标号及带宽计算实现任务对网格资源的映射与调度,提出了网格优化有向超图任务调度算法GODHTS。分析及模拟实验结果验证了该机制的合理性和有效性。(2)提出了一种网格服务资源多维性能聚类任务调度机制MPCGSR。该机制根据网格环境下服务资源数量庞大、异构、多样的特点,预先以构建的网格服务资源超图模型为基础,结合无尺度和小世界原理对服务资源进行多维性能聚类,将任务与聚类资源相匹配并实施调度。理论分析和模拟实验结果表明该机制是一种有效的网格任务调度机制,其算法优于同类算法。(3)提出了一种基于资源超图划分聚类的网格任务调度机制RHPC。该机制在构建的网格超图模型基础上,预先对资源超图进行划分聚类,将任务与聚类资源相匹配并实施调度。模拟实验结果表明该机制缩短了任务资源相匹配的时间,提高了任务调度的性能,是一种有效的网格任务调度机制。(4)提出了一种基于有向超图划分的网格任务调度算法HPGTS。根据网格环境下任务调度及传统DAG图的特点,吸取有向超图的优点,将有向超图理论融合任务调度特征,建立了基于划分的网格有向超图模型,在此基础上通过对网格任务有向超图的划分并结合可信度实现任务对网格资源的映射与调度,提出了一种基于有向超图划分的网格任务调度算法HPGTS。分析和模拟仿真实验结果验证了该模型及其算法的有效性和优越性。(5)提出了一种基于融合进化计算的网格任务调度算法CEGTS。针对网格环境异构、分布等特点,本文结合了遗传算法与蚂蚁算法的优点,在双层进化结构基础上,提出了一种基于融合进化计算的网格任务调度算法CEGTS。模拟实验结果表明该调度算法与同类算法相比具有优越性。

论文目录

• 摘要
• ABSTRACT
• 目录
• 插图索引
• 附表索引
• 第一章 绪论
• 1.1 本课题的研究意义
• 1.2 研究现状
• 1.2.1 网格概述
• 1.2.2 网格任务调度
• 1.2.3 主要研究项目
• 1.3 本课题的主要研究内容
• 1.4 论文的组织结构
• 第二章 相关研究
• 2.1 网格资源
• 2.2 虚拟组织
• 2.3 网格环境
• 2.3.1 环境特性
• 2.3.2 结构与分类
• 2.3.3 环境构建
• 2.4 网格任务调度
• 2.5 超图理论
• 2.6 本章小结
• 第三章 网格任务调度模型
• 3.1 概述
• 3.2 模型构成
• 3.2.1 任务管理层
• 3.2.2 资源管理层
• 3.2.3 映射层
• 3.2.4 模型分布结构
• 3.3 任务调度策略
• 3.3.1 生成有向超图
• 3.3.2 水平构形
• 3.3.3 调度
• 3.4 分析与实验
• 3.4.1 分析
• 3.4.2 实验
• 3.5 本章小结
• 第四章 一种资源性能聚类优化的网格任务调度机制
• 4.1 概述
• 4.2 调度模型
• 4.2.1 任务模型
• 4.2.2 资源模型
• 4.3 调度机制
• 4.3.1 算法描述
• 4.3.2 性能分析
• 4.4 实验
• 4.4.1 实验内容与设置
• 4.4.2 实验结果
• 4.5 本章小结
• 第五章 基于资源超图划分优化的网格任务调度
• 5.1 概述
• 5.2 网格资源超图划分
• 5.3 算法描述
• 5.3.1 初始化
• 5.3.2 资源超图划分聚类
• 5.3.3 任务调度
• 5.4 实验
• 5.5 本章小结
• 第六章 可信网格任务划分调度
• 6.1 概述
• 6.2 任务划分模型
• 6.3 可信度计算
• 6.4 算法描述
• 6.4.1 初始化
• 6.4.2 任务划分
• 6.4.3 算法总体描述
• 6.5 实验及分析
• 6.6 本章小结
• 第七章 基于融合进化计算的网格任务调度
• 7.1 概述
• 7.2 任务模型
• 7.3 调度算法
• 7.3.1 染色体编码
• 7.3.2 初始种群（initial population）
• 7.3.3 适应度函数
• 7.3.4 遗传操作
• 7.3.5 遗传迭代终止及信息素转换
• 7.3.6 AA计算部分
• 7.3.7 CEGTS算法总体描述
• 7.4 实验
• 7.5 本章小结
• 第八章 结论
• 8.1 工作总结
• 8.2 进一步的深入研究工作
• 参考文献
• 致谢
• 攻读博士学位期间的主要研究成果