学位论文 > 优秀研究生学位论文题录展示

基于并行计算负载均衡算法的研究

作　者: 闫蓉
导　师: 管建和
学　校: 中国地质大学（北京）
专　业: 计算机应用技术
关键词: 并行计算 并行编程 MPI 负载均衡算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2008年
下　载: 457次
引　用: 4次
阅　读: 论文下载
 

内容摘要


最近几年来,并行计算得到了业界的高度关注,微软首席预言家克莱格.穆迪更是预言并行计算将成未来重点。利用并行计算技术,计算机可以将不同的任务分配给多个处理器同时处理,而不是由一个处理器每次处理一项任务,从而提升了计算机的运算速度。为了将计算能力最大化,软件厂商需要改变软件程序员的工作方式,他们不能再使用传统的线性编程方式,而是要在代码中将计算任务划分为多个部分,并交由多个处理器同时处理。将这种模式扩展到局域网范围内,即引出了本文的研究内容,研究如何利用局域网内PC资源,使用Windows操作系统作为平台,给出运用MPI标准实现负载均衡调度算法并行程序设计的方法,从而达到高性能计算的目的。影响负载均衡的因素主要有负载均衡的调度算法、网络拓扑和负载均衡的粒度,其中,调度算法是负载均衡技术的核心。本文在研究国内外相关文献的基础上,从负载均衡技术的发展现状入手,介绍了该技术的涵义、分类等基础知识;讲解了负载均衡算法的理论知识,并针对常见负载均衡算法的实现细节进行了分析;同时利用运行平台MPICH,将多台PC机通过局域网连接成异构集群的并行计算环境,结合目前集群系统中最重要的并行编程标准MPI,通过求解“暴力破解”、“旅行商”等问题,充分挖掘问题和算法本身的并行特性,详细介绍了随机算法、循环算法和遗传算法的理论依据、实现流程及优缺点等,并针对现有算法的不足给出了相应的优化方案,为以后进行类似领域的开发提供了理论和方向上的支持,为并行计算中负载均衡算法实践的普及做了大胆的尝试。虽然静态负载均衡算法相对于动态负载均衡算法来说是一种比较落后的算法,不能达到任务适时调度的需求,但是由于其调度机制相对比较简单,调度消耗更低,因此在特定的应用领域它甚至比动态均衡算法更有效。

全文目录


摘要  5-6
Abstract  6-10
第一章 绪论  10-13
  1.1 研究背景  10
  1.2 研究意义  10-11
  1.3 研究现状  11
  1.4 论文组织结构  11-13
第二章 负载均衡技术  13-18
  2.1 负载均衡技术的涵义  13
  2.2 负载均衡技术的分类  13-15
    2.2.1 从实现方式角度划分  14
    2.2.2 从网络规模角度划分  14
    2.2.3 从网络层次角度划分  14-15
    2.2.4 从负载特性角度划分  15
  2.3 负载均衡算法  15-18
    2.3.1 负载均衡算法分类  15-16
    2.3.2 负载均衡算法的性能  16-18
第三章 静态负载均衡算法  18-25
  3.1 设计调度算法的因素  18-21
    3.1.1 网络拓扑  18-19
    3.1.2 粒度决策  19-20
    3.1.3 任务分配  20-21
  3.2 静态调度模型的演变与分类  21-22
  3.3 常见调度算法简介  22-25
第四章 算法研究与实现  25-39
  4.1 并行程序设计简介  25-29
    4.1.1 并行编程模式  25-26
    4.1.2 并行编程过程  26-27
    4.1.3 并行编程语言环境  27-28
    4.1.4 一般的MPI 程序设计流程图  28-29
  4.2 随机算法的实现  29-36
    4.2.1 算法理论分析  29-31
    4.2.2 实现流程  31-35
    4.2.3 测试  35-36
    4.2.4 优点及不足  36
  4.3 循环算法的实现  36-39
    4.3.1 算法理论分析及实现流程  36-37
    4.3.2 测试  37-38
    4.3.3 优点及不足  38-39
第五章 遗传算法  39-56
  5.1 遗传算法概述  39-44
    5.1.1 基础用语  39-40
    5.1.2 标准遗传算法基本结构  40-42
    5.1.3 标准遗传算法的手工模拟  42-44
    5.1.4 遗传算法的应用  44
  5.2 并行遗传算法  44-48
    5.2.1 遗传算法的可并行性分析  45
    5.2.2 遗传算法在并行实现上的困难  45-46
    5.2.3 遗传算法的并行化模型  46-48
  5.3 用遗传算法解决TSP 问题  48-52
    5.3.1 TSP 问题描述  48-49
    5.3.2 算法设计基本步骤  49-51
    5.3.3 并行遗传算法的模型实现  51-52
  5.4 测试  52-54
  5.5 优点与不足  54-56
第六章 结论  56-57
致谢  57-58
参考文献  58-60
附录  60

相似论文

  1. 一种高性能可扩展公钥密码协处理器的研究与设计,TN918.1
  2. 基于多核计算平台的视频压缩算法研究,TN919.81
  3. 基于GPU的有限元方法研究,O241.82
  4. 射频波注入磁化等离子体的数值模拟,TL612
  5. 新型电网广域后备保护的算法研究,TM774
  6. 保护在线自适应整定的研究,TM77
  7. 过载虚机条件下MPI通信性能改善方法研究,TP302
  8. 云环境下MapReduce容错技术的研究,TP302.8
  9. 高动态SINS导航解算算法及其并行化研究,TN966
  10. 图像检索的并行计算方法与系统,TP391.3
  11. GPU加速的粒子滤波PET图像重建算法,TP391.41
  12. 基于GPU的时间序列并行检索算法研究,TP391.41
  13. 基于CPU的源强反算算法研究,TP18
  14. 面向密集数据并行计算的可重构线性阵列处理器架构的设计,TP332
  15. 基于段落指纹的大规模近似网页检测算法研究,TP393.092
  16. 并行与双系统协同差异进化算法及其应用,TP18
  17. 云计算环境下的容错并行Skyline查询技术研究,TP311.13
  18. 基于GPGPU平台的对角线模型问题研究,TP391.41
  19. CUDA加速CV图像分割和外部CT图像重建算法研究,TP391.41
  20. 无人机数码遥感测绘系统集成及影像处理研究,P237
  21. FDTD与MPSTD并行算法在电磁散射中的应用研究,O441.4

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com