基于MPI和Linux机群环境的FFT算法的并行设计与实现

发布时间：2017-09-09 13:16

  本文关键词：基于MPI和Linux机群环境的FFT算法的并行设计与实现

  更多相关文章： 机群 MPI 并行编程 胖二叉树 FFT

【摘要】：在数字时代,几乎所有的实际系统都离不开数字信号中的频域处理。快速傅里叶变换是数字信号处理的核心技术,是频域处理最常用的方法,得到了广泛地应用。伴随着通信领域的快速发展,利用FFT处理的数据量越来越大,利用串行FFT进行大数据量运算耗时过久,这已无法满足现实要求。当处理的数据量非常大时,并行计算是应对运算消耗时间太长的有效方法,并且机群系统是并行计算编程实现的主流平台,那么以机群系统为平台实现FFT并行化的研究具有重要的意义。本文首先阐述了课题研究背景意义及主要工作,然后介绍了庞大复杂的并行计算相关知识中的并行机体系结构和几种典型的并行机系统,在并行机系统中着重介绍了当前的主流平台机群系统,然后详细介绍了并行算法相关理论,分析对比了几种并行编程模型,结合机群的体系机构选择了消息传递编程模型,并选择了其中应用更为广泛的MPI作为通信标准。基于理论研究,利用实验室条件分别具体实现了基于Windows和Linux两种操作系统环境下的PC机群的搭建。接着对FFT算法的原理进行研究,主要研究了FFT算法的蝶式运算结构特点,同时对胖二叉树网络拓扑结构进行分析,根据两者之间相似的结构特点,提出了基于胖二叉树逻辑结构将FFT并行化的思路,在理论上详细分析了此并行化思路的可行性,并基于MPI进行了编程实现。在实验部分,本文首先介绍了所利用的实验环境,然后将并行编程实现的FFT并行算法和串行算法在曙光集群TC5000进行了多组多次实验测试,得到一系列实验数据,比较了在不同处理数据量的情况下并行FFT和串行FFT运算时间的不同。根据实验结果体现出来的情况,验证了基于胖二叉树逻辑结构将FFT并行化在机群环境下实现的可行性,并得到并行计算方面一些有意义的结论。最后,论文对前面所做工作进行了概括总结,并结合机群系统的体系结构特点,提出了进一步提高FFT并行算法性能的一些方法。
【关键词】：机群 MPI 并行编程 胖二叉树 FFT
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP338.6
【目录】：

• 摘要4-5
• Abstract5-9
• 第一章 绪论9-13
• 1.1 课题研究背景及意义9-11
• 1.1.1 课题研究背景9-11
• 1.1.2 课题研究意义11
• 1.2 本文的主要工作11-12
• 1.3 本文结构12-13
• 第二章 并行计算13-22
• 2.1 并行计算13-14
• 2.2 并行计算机系统结构14-16
• 2.2.1 SM与DSM多处理机系统15-16
• 2.2.2 分布式主存DM16
• 2.3 典型并行计算机系统16-21
• 2.3.1 阵列机16-17
• 2.3.2 向量机17
• 2.3.3 对称多处理机SMP17-18
• 2.3.4 大规模并行处理系统MPP18-19
• 2.3.5 机群19-21
• 2.4 小结21-22
• 第三章 并行算法相关理论及MPI程序设计22-34
• 3.1 并行算法22
• 3.2 并行算法的性能评价指标22-23
• 3.3 并行算法的分类23
• 3.4 并行算法的设计过程23-24
• 3.5 并行编程模式的主要类型24-26
• 3.5.1 消息传递模型24-25
• 3.5.2 共享变量模型25
• 3.5.3 数据并行模型25-26
• 3.6 MPI简述26-33
• 3.6.1 MPI常用函数26-28
• 3.6.2 MPI的主要实现28
• 3.6.3 MPI程序设计28-30
• 3.6.4 MPI通信分析30-33
• 3.7 小结33-34
• 第四章 搭建小型PC机群34-41
• 4.1 基于MPI和Windows的PC机群的搭建34-38
• 4.1.1 机群硬件环境34-35
• 4.1.2 软件配置环境35-38
• 4.2 基于MPI和Linux的机群的搭建38-40
• 4.2.1 机群硬件环境38-39
• 4.2.2 机群的搭建39-40
• 4.3 小结40-41
• 第五章 基于MPI的FFT并行实现41-49
• 5.1 离散傅里叶变换（DFT）41
• 5.2 快速傅里叶变换41-44
• 5.3 胖二叉树44-45
• 5.4 FFT蝶式计算的并行化45-47
• 5.5 本章小结47-49
• 第六章 总结与展望49-51
• 6.1 本文工作总结49
• 6.2 进一步工作49-51
• 参考文献51-53
• 在校期间发表的学术论文53-54
• 致谢54

【参考文献】

中国期刊全文数据库 前6条

1 秦广军;祝明发;肖利民;阮利;;胖树的网络演算模型[J];计算机工程与科学;2014年12期

2 卢可佩;祝永志;;基于MPI的Jacobi迭代算法的并行化[J];电脑知识与技术;2014年31期

3 王文义;王春霞;王杰;;基于CMP多核集群的混合并行编程技术研究[J];计算机科学;2014年02期

4 祝永志;张丹丹;曹宝香;禹继国;;基于SMP机群的层次化并行编程技术的研究[J];电子学报;2012年11期

5 陈国良;孙广中;徐云;龙柏;;并行计算的一体化研究现状与发展趋势[J];科学通报;2009年08期

6 吴明,陈国良,孙凝晖;并行计算机用户环境的设计与实现[J];计算机学报;2000年10期

，

本文编号：820650