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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题研究背景及意义

1.2 本文的主要工作

1.3 本文结构

第二章 并行计算

2.1 并行计算

2.2 并行计算机系统结构

2.3 典型并行计算机系统

2.4 小结

第三章 并行算法相关理论及MPI程序设计

3.1 并行算法

3.2 并行算法的性能评价指标

3.3 并行算法的分类

3.4 并行算法的设计过程

3.5 并行编程模式的主要类型

3.6 MPI简述

3.7 小结

第四章 搭建小型PC机群

4.1 基于MPI和Windows的PC机群的搭建

4.2 基于MPI和Linux的机群的搭建

4.3 小结

第五章 基于MPI的FFT并行实现

5.1 离散傅里叶变换（DFT）

5.2 快速傅里叶变换

5.3 胖二叉树

5.4 FFT蝶式计算的并行化

5.5 本章小结

第六章 总结与展望

6.1 本文工作总结

6.2 进一步工作

参考文献

在校期间发表的学术论文

致谢