论文部分内容阅读
离散傅立叶变换(Discrete Fourier Transform)是我们这个时代最有影响力的数学公式之一,广泛应用于许多的科学和工程领域。数字信号处理技术作为一门具有强大生命力的科学技术,其核心算法就是离散傅立叶变换。在算法的实际应用中,算法复杂度以及算法的可行性等都是影响算法效率的重要因素。快速傅里叶变换(FastFourierTransform)大大降低了算法复杂度提高了算法效率。近年来,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的异构模型进行并行计算为许多数据密集型科学计算提供了帮助。FFIT在GPU上的并行实现具有广泛而深刻的意义。因此,本文的主要研究集中在如何利用CUDA提供的CPU+GPU异构环境实现FFT在GPU上的并行实现。为了实现FFIT算法的高效设计,本文实现了FFIT在GPU上的并行算法,并提出了一种基于GPU纹理存储器的建表优化方法。通过使用GPU纹理存储器设计了两种并行算法,分别基于一维纹理存储器和二维纹理存储器。本文的主要内容为:(1)针对FFIT算法在CPU上运行效率不太理想的问题,设计了可以在GPU上运行的并行算法。通过对GPU的硬件体系结构和编程模型的深入分析以及对按时间抽选基-2的快速傅立叶变换的原理以及特性的深入探讨,提出了使用CUDA进行并行FFIT算法设计的可行方法。众所周知快速傅立叶变换的时间复杂度为O(Nlog2N),通过并行计算,使得快速傅立叶变换的三层循环嵌套变为两层,使得计算量变小。(2)参考多种优化方法,提出采用两种纹理存储器对算法进行加速,同时还从不同的角度对并行快速傅立叶算法进行了优化。在已经搭建和配置好的并行编程环境中,与CUDA提供的CUFFIT库函数进行对比实验,成功的进行了两种不同快速傅立叶变换并行算法的性能评估。最后通过实验数据分析证明,并行FFT算法的高效GPU设计得到了实现。(3)将算法移植到多个GPU上执行,使用GPUDirect技术实现多GPU上的通信,并且通过实验结果证明多GPU算法的高效性。