基于粒子群优化算法的集群调度策略研究

论文摘要

随着集群规模的逐渐扩大和性能的日益提高,集群调度技术作为集群的关键技术也成为研究的难点和热点。粒子群优化算法（Particle Swarm Optimization, PSO）具有并行性、有效的全局/局部搜索平衡能力、计算简单、鲁棒性好等优点,将粒子群优化算法的引入集群调度中,具有很高的学术价值和实际意义。本文搭建了一个基于Linux + MPI的松耦合PC集群,在集群网络存储节点间建立RAID5数据冗余关系,来提高数据传输速率和系统吞吐量,实现了逻辑盘卷管理（LVM）,提高集群系统磁盘分区管理的灵活性,降低节点/磁盘的平均失效时间的同时提高了系统的重构速率,增强了整个集群系统的安全性和可靠性。设计并实现了基于PSO算法的调度策略,包括编码方式的设计、选择速度-位置模型、确定集群调度问题的适应度函数和约束条件、确定算法的终止准则、设计粒子解码方式并生成调度方案。并根据调度策略中负载均衡的要求以及粒子群算法中惯性权重的研究,提出均衡因子Ti为每个节点的负载完成率的倒数,通过把各资源的负载完成率的差值控制在一个较小的阈值之内,以动态调整惯性权重来保证负载均衡。通过实验得出了最佳的ω、vmax、ε、m取值,由于PSO算法比较出色的性能,使得集群调度策略在生成速度和精度上都有明显的提高,添加均衡因子的调度策略由于充分考虑到集群系统在执行过程中的动态负载情况,使得集群的总体执行时间（最优值）更小。对最终调度结果、集群各节点的平均响应时间和CPU平均利用率进行测试和评价,通过与FCFS、Backfill的对比,基于PSO算法调度结果的效果是非常明显的,大大缩短了集群系统的处理周期,为实际的生产过程节约了大量的时间和成本。加入均衡因子后,更加平衡了系统高利用率和短作业等待时间之间的矛盾。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题的背景和意义
• 1.2 国内外研究现状
• 1.2.1 现有的调度策略分析
• 1.2.2 负载均衡调度策略分析
• 1.3 课题的主要研究内容
• 1.4 章节安排
• 第二章 集群及资源管理系统
• 2.1 集群体系结构和特点
• 2.2 集群的分类
• 2.3 集群的关键技术
• 2.4 集群资源管理系统介绍
• 2.4.1 Condor
• 2.4.2 Load Leveler
• 2.4.3 LSF
• 2.4.4 PBS
• 2.4.5 曙光3000 的JOSS 集群作业管理系统
• 2.5 PBS 作业调度机制
• 2.6 本章小结
• 第三章 集群调度策略
• 3.1 集群作业调度的模型及原理
• 3.2 现有调度策略分析
• 3.3 调度策略中的负载均衡
• 3.4 负载均衡调度策略分析
• 3.5 存在的问题
• 3.6 本章小结
• 第四章 基于粒子群优化算法的集群调度策略的设计与实现
• 4.1 粒子群优化算法原理
• 4.1.1 基本的粒子群优化算法
• 4.1.2 粒子群优化算法模型的改进
• 4.2 粒子群优化算法的优点和应用
• 4.3 粒子群优化算法的设计步骤和算法流程
• 4.4 基于PSO 算法的调度策略的设计与实现
• 4.4.1 粒子的编码方式
• 4.4.2 适应度函数的确定
• 4.4.3 选择粒子群速度-位置模型
• 4.4.4 确定算法的终止准则
• 4.4.5 生成粒子解码和调度方案
• 4.4.6 算法描述
• 4.4.7 生成调度方案
• 4.5 均衡因子的添加
• 4.6 本章小结
• 第五章 实验验证与结果分析
• 5.1 PC 集群的构建与测试
• 5.1.1 集群硬件环境
• 5.1.2 安装MPICH
• 5.1.3 配置MPICH
• 5.2 集群存储系统RAID
• 5.2.1 集群存储系统
• 5.2.2 RAID 技术的工作原理及特点
• 5.3 RAID5 原理及配置
• 5.3.1 RAID5 技术原理
• 5.3.2 设置RAID 5
• 5.3.3 配置热备（Hot spare）
• 5.4 逻辑盘卷管理（LVM）
• 5.4.1 LVM 基本术语
• 5.4.2 LVM 工具的安装
• 5.5 集群RAID5 存储系统可靠性分析
• 5.6 实验环境的搭建
• 5.6.1 PBS 的配置
• 5.6.2 PBS 的测试
• 5.7 实验结果分析
• 5.7.1 最优惯性权值和飞行速度的测试
• 5.7.2 优化结果与均衡因子阈值的关系
• 5.7.3 调度策略生成测试与评价
• 5.7.4 调度结果的测试与分析
• 5.8 本章小结
• 总结和展望
• 参考文献
• 攻读硕士学位期间取得的学术成果
• 致谢