论文部分内容阅读
离散傅立叶变换是数字信号处理系统中常用的重要数学变换,算法的可行性、复杂度和运行效率等都是影响计算结果的重要因素。近年来,GPU正在以大大超过摩尔定律的速度高速发展,主流GPU的单精度浮点处理能力和外部存储器带宽相对于同时期的CPU都有明显的优势,基于图形硬件GPU的通用计算正成为并行领域的研究热点。特别是NVIDIA公司于2007年推出的CUDA统一计算设备架构,在编程、优化等方面都得到了显著的提升,极大地增强了GPU的通用计算能力。CUDA不需要借助于图形API,采用类C语言进行开发,使开发人员比较容易的从CPU编程模式过渡到GPU编程模式。随着GPU可编程能力、并行处理能力以及应用范围的不断提升和扩展,GPU已发展成为一种高度并行化、多线程、多核的处理器。利用GPU的并行处理能力,以CPU+GPU混合加速为特征的异构并行计算系统将会成为未来高性能计算的主流。本文首先分析了CUDA硬件架构和编程模型,在分析GPU通用计算现状的基础上,提出CUDA程序设计的方法。然后深入探讨了快速傅立叶变换的基本原理,详细介绍了时域抽取基2-FFT算法的实现过程及相关性质,根据快速傅立叶算法高度并行分治的特征,结合CUDA编程模型及实现机制,用CUDA的类C语言设计了快速傅立叶变换的并行算法。改进算法采用CPU+GPU异构模型方式,将GPU引入到计算中来,让GPU承担程序中的大规模计算——复数的加法与算数的乘法。传统串行算法实现N点序列的快速傅立叶变换需要三层循环,时间复杂度为O (Nlog2N)。改进后的算法采用线程层次组织结构,将同一级中相互独立的N/2个蝶形运算实现并行操作,原有的三层循环可以用两层循环来完成,时间复杂度变为O (N),从而实现对快速傅立叶变换的加速与优化。文章最后搭建CUDA实验运行环境,实现传统快速傅立叶算法在CPU上的运行,以及改进后的算法在GPU上的运行,同时还调用了FFTW函数库的程序代码和CUFFT函数库的程序代码,并将以上结果进行比较,通过对实验数据的分析证明了运用CUDA架构实现快速傅立叶算法的优越性,也验证了GPU在处理大量数据计算时所占的优势。