基于CUDA架构的FFT并行计算研究

FFT（快速傅里叶变换）是基于提高DFT（离散傅里叶变换）计算的高效算法,它在众多科学和工程领域都得到了广泛的应用。自FFT算法出现以后,从早期的以降低复杂度到近年以来的大规模并行FFT计算,各种优化算法得到广泛的研究。在并行运算领域中,随着可编程的、并行化GPU的不断推广,特别是通用并行统一计算架构CUDA的出现,极大增强了GPU的计算能力,在编程和优化等方面都有显著地提升。鉴于此,本文在分析FFT算法实现的基础上,研究了一种适合GPU运算的FFT并行计算方法,并通过CUDA架构实现了FFT算法在GPU上的运算。该方法的引入在理论不计算数据传输的情况下,使一维FFT运算时间的复杂度由O（N logN2）可以降到O（N/rlogN2）。通过验证,本文提出的CUDA的并行FFT方法得到较好的加速效果,在精度计算上也符合实际的要求,从而证明了该方法的正确性和有效性。     

基于FPGA的通用FFT处理器的设计

介绍了一种通用的可以在低端或是高端的FPGA上实现N（N=2M,M=2,3,4…）点FFT变换的方法。设计采用基4布斯编码算法和华莱士树算法设计完成了16X16位有符号数并行乘法器,并采用此并行乘法器为核心设计了FFT算法中的基-2蝶形运算单元,设计了串并转化模块、并串转换模块、移位选择模块、溢出检测模块和地址与控制模块等其它模块,并以这些模块和FPGA内部的双口RAM和ROM为基础组成了基-2FFT算法模块。整个模块采用基-2时域抽取,顺序输入,逆序输出的方法;利用Modelsim完成了FFT模块的前后仿真;利用Matlab编写了用于比较仿真结果和Matlab中FFT函数产生的结果的程序,从而验证了仿真结果的正确性。该模块最后能够在Cyclone EP1C6Q240C8型FPGA上稳定运行在60MHz。整个FFT模块能够在183μs左右完成1024点的16位定点复数FFT运算,能够满足一般工程的要求。该方法也可以用于实现更低点数或是更高点数的FFT运算。     

基于MPSoC平台小波变换并行算法研究

快速小波变换是数字信号处理面临的一个重要问题,针对并行小波算法展开研究,缩减小波变换中卷积运算的规模,提高小波变换过程中的并行效能,以实现小波变换的快速并行计算。通过FFT矩阵代入计算,消去了并行计算过程中的同步通信,降低了乘法运算次数。对算法思想进行了理论分析,说明新算法在短小数据分段情况下能够减少50%~75%的乘法操作;通过搭建两种不同平台进行了对比测试,证明了算法的先进性与有效性。基于FFT矩阵的并行小波变换算法是一种稳定有效的经典小波并行算法。     

一种在多核嵌入式平台上实现FFT的快速并行算法

快速傅利叶变换（fast Fourier transform,FFT）算法是对实时数字信号进行快速分析处理的一个基本方法。针对多核嵌入式实时环境下并行FFT算法进行了研究,以有效提高实时信号处理的速度。提出了一种新的静态多项式FFT算法,充分利用静态多项式奇偶项的不同特点直接代入数据计算,免去了层层迭代的计算过程,减少了运算过程中的通信提高并行性能。对该算法思想本文在理论进行了严密论证,通过嵌入式实时平台上运行测试和仿真实验,证实了在数据分段较短的约束条件下,该多项式静态算法较经典的FFT并行算法在时间复杂度上有一定优势。本文结论:多项式静态FFT算法能够有效提高并行FFT运行速度。     

TMS320C6678的超长点FFT并行计算方法

针对DSP平台算法移植时遇到的超长点FFT实现和运算效率问题,本文结合TI公司的TMS320C6678的DSP,利用FFT的分解算法和L2内存段高效的访存效率,将DSP内存数据EDMA搬移与FFT分解计算相并行,设计出一种超长点FFT计算并行处理方法,通过262144点FFT计算描述了该方法的具体实现过程,将DSP计算...     

基2×2FFT的地址映射算法

FFT处理器是根据 FFT运算特点来进行设计的 ,可以充分提高处理效率 ,达到平均每周期完成一个蝶式运算的处理能力 .在这类芯片中 ,需要并行无冲突的数据访问部件来提供蝶式运算所需的多个操作数 .文中对已有的一些算法进行了比较 ,并提出基 2× 2 FFT的并行数据访问算法 ,通过使用 4个存储体 ,它可以同时完成所需的 4个数据的读取或写入操作 .该算法易于用硬件实现 ,其操作数访问地址的产生速度快于已有的算法 .     

q×2m的高速FFT处理器设计

对非2次幂长度的海量数据FFT处理器设计,采用补零技术会造成巨大硬件资源的浪费,且影响算法性能．提出了一种适合于硬件实现,可处理数据长度为q×2“的FFT算法（q为非2质数）以及基于此算法的FFT处理器设计方法．提出的操作数地址映射方法充分利用了算法的同址特性,使得在最少的存储空间需求下,达到最大的数据并行性;设计的混合运算单元有效地统一了混合基和q点DFT运算,减少了运算部件的资源占用率,使得多个运算单元的并行成为可能．仿真结果表明,计算16位20480点DFT运算需要7181个时钟周期,系统频率达到了105MHz．不仅有效地扩展了FFT处理器的数据处理范围,同时满足SAR等实时系统对处理速度的要求．     

q×2m的高速FFT处理器设计

对非2次幂长度的海量数据FFT处理器设计,采用补零技术会造成巨大硬件资源的浪费,且影响算法性能.提出了一种适合于硬件实现,可处理数据长度为q×2m的FFT算法(q为非2质数)以及基于此算法的FFT处理器设计方法.提出的操作数地址映射方法充分利用了算法的同址特性,使得在最少的存储空间需求下,达到最大的数据并行性;设计的混合运算单元有效地统一了混合基和q点DFT运算,减少了运算部件的资源占用率,使得多个运算单元的并行成为可能.仿真结果表明,计算16位20480点DFT运算需要7181个时钟周期,系统频率达到了105 MHz.不仅有效地扩展了FFT处理器的数据处理范围,同时满足SAR等实时系统对处理速度的要求.     

机群环境下傅立叶变换的并行算法研究

并行FFT是解决大数据量FFT运算耗时过久的重要途径,在PC机群上实现并行FFT是一种低成本、高效率的解决方案。本文讨论了PC机群环境下MPI并行FFT实现,并利用建立的平台,对并行算法进行了测试,得出了一些有意义的结论和方法。     

非基2情况下的GPS捕获算法优化

本文根据GPS捕获过程中相关运算的计算速度要求,针对常用频域FFT算法速度快、但规定采样点的点数N必须为2的整数幂的缺点,分析了如何利用Colley-Tukey算法对部分可分解的N值的相关运算进行优化,从而在时域算法保证精确度,同时又在速度上接近FFT算法.本文最后在Matlab环境下对算法进行验证.     

面向VLSI实现的FFT并行算法

本文提出了一种新的面向ＶＬＳＩ实现的ＦＦＴ并行算法，其中旋转因子所占ＲＯＭ的存储容量达到最小，因而有利于ＦＦＴ处理器的片内集成。     

Efficient implementation of parallel three-dimensional FFT on clusters of PCs

In this paper, we propose a high-performance parallel three-dimensional fast Fourier transform (FFT) algorithm on clusters of PCs. The three-dimensional FFT algorithm can be altered into a block three-dimensional FFT algorithm to reduce the number of cache misses. We show that the block three-dimensional FFT algorithm improves performance by utilizing the cache memory effectively. We use the block three-dimensional FFT algorithm to implement the parallel three-dimensional FFT algorithm. We succeeded in obtaining performance of over 1.3 GFLOPS on an 8-node dual Pentium III 1 GHz PC SMP cluster.     

High-Performance Radix-2, 3 and 5 Parallel 1-D Complex FFT Algorithms for Distributed-Memory Parallel Computers

In this paper, we propose high-performance radix-2, 3 and 5 parallel 1-D complex FFT algorithms for distributed-memory parallel computers. We use the four-step or six-step FFT algorithms to implement the radix-2, 3 and 5 parallel 1-D complex FFT algorithms. In our parallel FFT algorithms, since we use cyclic distribution, all-to-all communication takes place only once. Moreover, the input data and output data are both in natural order.We also show that the suitability of a parallel FFT algorithm is machine-dependent because of the differences in the architecture of the processor elements in distributed-memory parallel computers. Experimental results of 2^p3^q5^r point FFTs on distributed-memory parallel computers, HITACHI SR2201 and IBM SP2 are reported. We succeeded to get performances of about 130 GFLOPS on a 1024PE HITACHI SR2201 and about 1.25 GFLOPS on a 32PE IBM SP2.     

多核计算机上的快速傅里叶变换并行算法

针对现有多核结构上快速傅里叶变换(FFT)并行算法没有利用多级缓存和线程级并行等多核特性问题,通过运用多核多级存储特性合理划分数据,采取子序列FFT计算和多线程并行逐对计算FFT相结合的方法,给出一个N点、一维、有序和基数为2的多核多线程并行计算FFT非递归算法。理论分析和实验结果表明,该算法实用、高效,能获得较好的加速比和可扩展性。     

申威26010众核处理器上一维FFT实现与优化

根据申威26010众核处理器的特点提出了基于两层分解的一维FFT众核并行算法.该算法基于迭代的Stockham FFT计算框架和Cooley-Tukey FFT算法,将大规模FFT分解成一系列的小规模FFT来计算,并通过设计合理的任务划分方式、寄存器通信、双缓冲以及SIMD向量化等与计算平台相关的优化方法来提高FFT的计算性能.最后对所提出算法的性能进行了测试,相比于单主核上运行的FFTW3.3.4库,获得了平均44.53x的加速比,最高加速比可达56.33x,且其带宽利用率最高可达83.45%.     

基于网格的并行FFT计算研究

快速傅里叶变换（FFT）在科学和工程领域有着广泛的应用。在网格环境下进行并行FFT计算可以提高运算速度,促进FFT的应用。在介绍了网格计算发展状况的基础上,详细阐述了基于网格的分布式并行计算。实验以FFT算法为背景,在Globus Toolkit 4平台下实现了并行FFT计算,并对实验数据作了分析,说明了基于网格的并行FFT计算的可行性。最后指出网格资源调度对并行计算的重要性。     

基于MPI的伪谱法大涡模拟并行计算的研究

使用伪谱方法的大涡模拟准确、高效,但在高雷诺数情况下,计算量仍然非常巨大,需要采用并行方法,但是快速傅里叶变换的并行算法在实际应用中有很大的困难。针对这一问题,提出了一种新的基于MPI的伪谱法大涡模拟的并行计算方法。通过实例验证,该方法准确、易行、稳健,并且可以大幅提高计算速度,节省计算时间,这对大涡模拟在工程中的广泛应用具有重要意义。