网格系统中基于可用性的混合粒子群调度算法研究

摘要

网格计算的特点是把网络中大量空闲的计算和存储资源高效整合,组成一台超级计算机,以解决挑战性问题。这对解决大型复杂问题的计算来说能大幅度降低成本。通常可以把一个大型复杂问题分解成若干小任务,然后通过调度程序,把小任务分配到理想的处理节点中去执行,最后把所有的执行结果综合到一起,得到最后的结果。对于网格这种分布式异构系统而言,任务调度属于NP完全问题。因此,为使网格系统能发挥最佳性能,高效的任务调度算法是资源管理必不可少的部分。
　　目前的调度策略多基于启发式方法,每一种启发式算法的产生都来自于不同的应用背景,在面对新应用问题时,具有适应性限制。本文研究基于可用性的混合粒子群调度策略与算法,应用环境是基于异构分布式系统,其中的每一种资源由于种种原因都有可用性约束,同时,不同类型的任务也对机器的执行性能具有可用性需求。
　　将基于可用性的调度问题建模为一个最优化问题,研究和分析基本粒子群算法,根据基本粒子群算法在求解大型优化问题时所具有的收敛性强、适应度高、算法简洁、参数少和易于实现等优点,以及其有时会收敛过早的缺点。在基本粒子群算法中引入入遗传算法的轮盘赌选择后组成混合粒子群算法,设计出一种求解基于可用性约束的混合粒子群调度算法,对该算法在调度长度和可用性方面的性能进行了理论分析。并通过构建一个基于SimGrid工具包的模拟实验平台对所提出的算法同SSAC、遗传算法等3种算法的性能进行了模拟实验比较。实验结果表明,本文所提出的新算法不但在调度长度略优于传统算法,同时也提高了任务和系统的可用性。

目录

封面

声明

中文摘要

英文摘要

目录

引言

第一章 网格计算概述

1.1网格计算简介

1.2网格计算发展现状

1.3网格计算面临的问题

1.4网格中的任务调度

1.5小结

第二章 粒子群算法概况

2.1粒子群算法的基本概况

2.2粒子群算法的特点

2.3粒子群算法的研究现状

2.4基本粒子群算法的流程

2.5粒子群算法在任务调度问题中的应用

2.6小结

第三章 基于可用性的混合粒子群算法

3.1算法的基本思想

3.2基本模型

3.3 问题分析

3.4 基于可用性的混合粒子群调度算法

3.5 小结

第四章 实验对比分析结果

4.1 SimGrid工具包

4.2实验结果的对比及分析

4.3 小结

第五章 结论

5.1 总结

5.2 展望

参考文献

致谢

作者在攻读硕士期间的主要研究成果