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

基于MPI的几种确定性算法的并行设计

作　者: 陈龙鑫
导　师: 张少强
学　校: 天津师范大学
专　业: 计算机技术
关键词: 并行计算 MPI 贪心算法 k-means算法禁忌搜索
分类号: TP311.11
类　型: 硕士论文
年　份: 2013年
下　载: 1次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来,软硬件技术的快速发展,使得计算机技术得到了越来越广泛的应用,新一代计算机在性能上较之以往有了长足进步。随着计算机使用范围的不断扩大,需要使用计算机来解决的问题规模也逐渐增大。面对现代诸多科研应用领域中具有挑战性的大规模计算课题对计算资源的需求,人们对高性能计算有了更加迫切的需求。并行计算是高性能计算研究领域中的热点问题之一,是计算数学与新一代计算机科学相结合的成果,它为大规模科学计算提供了理论基础与支持工具。作为如今流行的基于消息传递的并行编程环境,MPI(Message Passing Interface)即消息传递接口,以其功能强大、移植性好、高效等优点成为了目前最重要的并行编程工具被广泛应用于并行计算中。本文首先介绍了高性能计算与并行计算的发展情况,阐述了并行算法的基本理论。而后对MPI进行了简要说明,并介绍了C语言环境下MPI库的基本调用方法。在此基础上,研究讨论了运用MPI对三种确定性算法进行并行化设计。对于贪心算法中求单源最短路径的Dijkstra算法,通过实验测试给出算法执行时间以及加速比以分析算法性能：对于k-means算法,通过对实验数据的具体计算分析完成算法相应功能；对于禁忌搜索算法,在进行并行化设计的同时对其进行适当改进,通过实验对比串行算法与并行算法数据并予以分析得出结论。

全文目录

摘要  4-5
ABSTRACT  5-6
目录  6-9
第一章绪论  9-15
  1.1 高性能计算简介  9-10
  1.2 高性能计算的发展情况  10-11
  1.3 高性能的研究方向  11-13
    1.3.1 网格计算  12
    1.3.2 集群计算  12
    1.3.3 志愿计算  12-13
    1.3.4 海量存储  13
  1.4 国内外高性能计算研究现状  13-15
第二章并行计算基础  15-22
  2.1 并行计算的基本概念  15
  2.2 并行计算机的分类  15-19
    2.2.1 单指令流单数据流计算机系统——SISD  16
    2.2.2 单指令流多数据流计算机系统——SIMD  16-17
    2.2.3 多指令流单数据流计算机系统——MISD  17
    2.2.4 多指令流多数据流计算机系统——MIMD  17-19
  2.3 并行计算性能评价方法  19-20
    2.3.1 加速系数  19
    2.3.2 效率  19-20
    2.3.3 并行执行时间  20
  2.4 并行计算的发展——机群系统  20-22
    2.4.1 机群系统概念  20
    2.4.2 机群系统的特点  20-22
第三章并行算法理论  22-28
  3.1 并行基础——消息传递  22
  3.2 并行算法的分类  22-23
  3.3 并行化策略  23-24
  3.4 并行算法的性能评估与度量  24-28
    3.4.1 阶  24
    3.4.2 通讯步与计算步  24-25
    3.4.3 计算复杂度与通讯复杂度  25
    3.4.4 并行度与平均并行性  25-26
    3.4.5 加速比  26-27
    3.4.6 效率  27
    3.4.7 成本  27-28
第四章基于MPI的程序设计  28-34
  4.1 MPI(Message Passing Interface)简介  28-29
  4.2 MPI编程方法(基于C语言)  29
  4.3 MPI基本调用  29-34
    4.3.1 MPI初始化  30
    4.3.2 MPI结束  30
    4.3.3 MPI当前进程标识  30-31
    4.3.4 MPI通信中包含的进程数  31
    4.3.5 MPI消息发送  31-32
    4.3.6 MPI消息接收  32-34
第五章贪心算法的并行设计  34-43
  5.1 贪心算法(Greedy Algorithm)介绍  34
  5.2 贪心算法特性  34-35
  5.3 单源最短路径Djkstra算法  35-43
    5.3.1 算法基本思想  36
    5.3.2 串行Djkstra算法主要代码实例  36-38
    5.3.3 并行Djkstra算法设计  38-43
第六章 k-means算法的并行设计  43-51
  6.1 k-means算法介绍  43
  6.2 算法基本思想  43-44
  6.3 算法流程  44-45
  6.4 算法伪代码  45-46
  6.5 并行k-means算法设计  46-51
    6.5.1 并行性分析  46
    6.5.2 算法设计  46-47
    6.5.3 实验结果  47-51
第七章禁忌搜索算法的并行设计  51-56
  7.1 禁忌搜索算法介绍  51
  7.2 禁忌搜索算法思想  51-52
  7.3 禁忌搜索算法伪代码  52-53
  7.4 并行禁忌搜索算法设计  53-56
    7.4.1 并行性分析  53
    7.4.2 算法设计  53-54
    7.4.3 实验结果  54-56
总结与展望  56-57
参考文献  57-60
致谢  60

基于MPI的几种确定性算法的并行设计

内容摘要

全文目录

相似论文