基于负载均衡的网格工作流调度算法研究

论文摘要

网格计算是并行计算、分布式计算以及高性能计算必然的发展趋势和重点研究方向,随着网格的发展而产生的网格工作流技术是网格计算的重要研究领域之一。网格工作流技术能够更加有效地利用各种网格资源来完成具有时间、空间和资源等多种约束条件的复杂任务。网格工作流模型是工作流管理系统的基础,同时也是网格工作流流程的一种表示方法。因为工作流之间存在时间或数据等约束关系,网格计算可用有向无环图(Directed Acyclic Graph,DAG)来表示工作流调度模型。通过对网格用户和系统资源在网格工作流任务调度中的不同目标进行分析,本文对用DAG表示的工作流调度模型提出一种时间复杂度较低可以在一定程度上缩短工作流时间跨度的基于逆向分层负载均衡的调度算法,并提出一种在最优时间跨度下负载均衡的网格工作流调度算法。模拟实验表明,两种调度算法都能缩短工作流时间跨度和均衡系统资源负载,最优时间跨度下负载均衡的调度算法由于时间复杂度高所以比基于逆向分层负载均衡的调度算法更能缩短工作流时间跨度,同时系统资源的负载也更均衡。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 什么是网格
• 1.2 网格的基本特征
• 1.3 网格的发展
• 1.4 网格的相关技术
• 1.4.1 网格体系结构
• 1.4.2 网格安全技术
• 1.4.3 网格中间件技术
• 1.5 网格的研究现状
• 1.6 课题来源及意义
• 1.7 本文的主要工作
• 第二章 网格工作流模型和调度算法研究
• 2.1 工作流和网格工作流概述
• 2.2 网格工作流研究现状
• 2.2.1 网格工作流介绍
• 2.2.2 相关网格工作流管理系统
• 2.2.3 网格工作流规范
• 2.3 网格工作流调度算法分析
• 2.3.1 遗传算法
• 2.3.2 粒子群优化算法
• 2.3.4 最小关键路径法
• 2.3.5 分层法
• 2.3.6 异构最小时间优先算法
• 2.4 负载均衡
• 2.4.1 负载均衡的定义
• 2.4.2 负载均衡的重要性
• 2.4.3 相关负载均衡的调度算法
• 2.5 负载均衡的网格工作流调度模型
• 2.5.1 问题的定义及相关的约定
• 2.5.2 模型的调度目标
• 第三章 基于逆向分层负载均衡的网格工作流调度算法
• 3.1 算法相关背景分析
• 3.2 基于逆向分层负载均衡的调度算法
• 3.3 基于逆向分层负载均衡的调度算法实例
• 第四章 最优时间跨度下负载均衡的网格工作流调度算法
• 4.1 最优时间跨度下负载均衡的调度算法
• 4.1.1 求解关键路径算法分析
• 4.1.2 获取每个节点的前驱矩阵以及后继矩阵
• 4.1.3 并行调度函数
• 4.1.4 最终算法程序实现的伪代码
• 4.1.5 算法时间复杂度分析
• 4.1.6 轮询算法
• 4.2 最优时间跨度下负载均衡的调度算法实例
• 第五章 模拟实验与结果分析
• 5.1 基于逆向分层负载均衡的调度算法实验
• 5.1.1 实验设置
• 5.1.2 基于逆向分层负载均衡的算法与轮询算法比较
• 5.1.3 逆向分层中时间跨度的实验
• 5.2 最优时间跨度下负载均衡的调度算法实验
• 5.2.1 最优时间跨度下负载均衡的调度算法实验设置
• 5.2.2 最优时间跨度下负载均衡的调度算法分析
• 第六章 总结
• 6.1 全文总结
• 6.2 进一步的工作
• 参考文献
• 攻读硕士期间发表论文
• 致谢