基于查找表的FFT CUDA并行算法研究

摘要

离散傅立叶变换（Discrete Fourier Transform）是我们这个时代最有影响力的数学公式之一，广泛应用于许多的科学和工程领域。数字信号处理技术作为一门具有强大生命力的科学技术，其核心算法就是离散傅立叶变换。在算法的实际应用中，算法复杂度以及算法的可行性等都是影响算法效率的重要因素。快速傅里叶变换（Fast Fourier Transform）大大降低了算法复杂度提高了算法效率。近年来， GPU（Graphics Processing Unit）正在不断的高速发展，GPU从原来的三维图像处理过度到更多的用来进行通用计算，科学研究中问题规模的扩大以及复杂度的提高使得GPU在科学计算中的存在意义非凡。GPGPU（General Purpose Computing on Graphics Processing Unit）编程技术尝试使GPU能够像CPU一样用来进行通用计算。NVIDIA公司推出的CUDA（Compute Unified Device Architecture）架构为GPU并行计算提供了新的解决办法。借助CUDA架构，利用CPU+GPU的异构模型进行并行计算为许多数据密集型科学计算提供了帮助。FFT在GPU上的并行实现具有广泛而深刻的意义。因此，本文的主要研究集中在如何利用CUDA提供的CPU+GPU异构环境实现FFT在GPU上的并行实现。
　　为了实现FFT算法的高效设计，本文实现了FFT在GPU上的并行算法，并提出了一种基于GPU纹理存储器的建表优化方法。通过使用GPU纹理存储器设计了两种并行算法，分别基于一维纹理存储器和二维纹理存储器。本文的主要内容为：
　　（1）针对FFT算法在CPU上运行效率不太理想的问题，设计了可以在GPU上运行的并行算法。通过对GPU的硬件体系结构和编程模型的深入分析以及对按时间抽选基-2的快速傅立叶变换的原理以及特性的深入探讨，提出了使用CUDA进行并行FFT算法设计的可行方法。众所周知快速傅立叶变换的时间复杂度为O(N log2 N)，通过并行计算，使得快速傅立叶变换的三层循环嵌套变为两层，使得计算量变小。
　　（2）参考多种优化方法，提出采用两种纹理存储器对算法进行加速，同时还从不同的角度对并行快速傅立叶算法进行了优化。在已经搭建和配置好的并行编程环境中，与CUDA提供的CUFFT库函数进行对比实验，成功的进行了两种不同快速傅立叶变换并行算法的性能评估。最后通过实验数据分析证明，并行FFT算法的高效GPU设计得到了实现。
　　（3）将算法移植到多个GPU上执行，使用GPUDirect技术实现多GPU上的通信，并且通过实验结果证明多GPU算法的高效性。

目录

声明

第1章 绪论

1.1 研究背景

1.2 国内外研究现状

1.3 本文研究内容

1.4 本文组织结构

第2章 相关理论与研究

2.1 GPU架构

2.2 快速傅里叶变换算法

2.3 查找表

2.4 小结

第3章 并行FFT算法设计与优化

3.1 快速傅里叶串行算法

3.2 FFT算法并行设计

3.3 FFT在GPU CUDA上的并行算法

3.4 基于CUDA的并行优化

3.5 多GPU上的并行FFT

3.6 小结

第4章 基于CUDA的FFT算法实现

4.1 实验平台搭建

4.2 并行快速傅里叶算法具体实现

4.3 实验结果分析

4.4 小结

结论

参考文献

附录A 攻读硕士学位期间所发表的学术论文目录

附录B 攻读学位期间所参加的科研项目目录

致谢