基于ARMv8处理器的实数FFT实现与性能优化研究

FFT(快速傅里叶变换)是离散傅里叶变换或其逆变换的一种常见快速算法,是高性能计算领域最重要的基础核心算法之一,在科学、工程和数学等领域的应用十分广泛.实数FFT算法,即输入或者输出为实数的FFT算法,其中包括R2C(Real-to-Complex)、C2R(Complex-to-Real)等变换类型.相比复数FFT算法,实数FFT算法在图形图像处理、数据压缩等领域有着不可替代的作用.传统实数FFT实现针对的是输入规模为偶数,一般转变为复数FFT进行运算.然而当前鲜有针对输入规模为奇数的实数FFT高效实现.对此,本文提出了一种实数FFT高效算法(DRFFT),并采用蝶形网络优化、蝶形计算优化、访存优化、SIMD优化以及数据转置等方法进行优化,大幅提升了实数FFT算法性能,最终构建了一种针对实数FFT的高性能算法库.实验结果表明,本文实现的DRFFT R2C变换在单双精度浮点数处理方面较FFTW库性能分别平均提升了37.6%和4.6%,较ARMPL库性能分别平均提升了67.6%和28.1%.DRFFT C2R变换在单双精度浮点数处理方面则较FFTW库性能分别平均提升了58.6%和10.8...     

一种偶数基Cooley-Tukey FFT高性能实现方法

快速傅里叶变换(Fast Fourier Transform,FFT)是最重要的基础算法之一,在科学计算、信号处理、图像处理等领域都有着广泛的应用。随着这些应用领域对实时性需求的进一步提高,FFT算法面临着越来越高的性能要求。在现有的FFT算法库中,FFT算法的求解速度和计算精度受到一定程度的限制,而且也少有研究者对偶数基Cooley-Tukey FFT的高性能实现提出相应的优化策略并对技术进行深入研究。基于此,文中提出了一套针对偶数基的Cooley-Tukey FFT的优化策略和方法。首先构建一个SIMD(Single Instruction Multiple Data)友好、支持混合基的蝶形网络,然后根据偶数基旋转因子特性最大限度地降低蝶形计算的复杂度,接着通过SIMD汇编优化、汇编指令重排及选择、寄存器分配策略制定、高性能矩阵转置算法等方法来优化应用,最后实现一个高性能的FFT算法库。目前,最流行、应用最广的FFT有FFTW和Intel MKL。实验结果表明,在X86计算平台上,新提出的这套针对偶数基Cooley-Tukey FFT的技术所实现的FFT算法库的性能全面优于MKL和FFTW。所提出的这套高性能算法优化和实现技术体系,可推广到除偶数基以外的其他基的实现和优化上,为进一步的研究开发工作奠定一定的基础,进而突破FFT算法在硬件平台上的性能瓶颈,实现一套针对特定平台的高性能FFT算法库。     

基于异构编程模型的FFT算法实现和优化

FFT（快速傅立叶变换）是一种广泛应用于科学和工程领域的算法,现实应用中数据规模较大,需要高效实现才能满足实际应用需求。为了研究使用异构编程模型高效实现FFT算法,以华为鲲鹏处理器和昇腾AI加速芯片为实验平台,以SYCL语言为异构编程语言,实现了Cooley-Tukey基-2时域抽取FFT算法的方法和优化策略,并且提出了一种数据对切重组优化算法,大幅提高了对硬件并行能力的利用率。使用异构编程模型实现快速傅立叶变换算法可以更好地发挥异构计算设备的性能优势,易于编程且具有更高的兼容性。测试表明,在一定规模下,优化后的算法性能相比于优化前快了220.39倍。     

基于软硬件的协同支持在众核上对1-DFFT算法的优化研究

随着高性能计算需求的日益增加,片上众核(many-core)处理器成为未来处理器架构的发展方向.快速傅立叶变换(FFT)作为高性能计算中的重要应用,对计算能力和通信带宽都有较高的要求.因此基于众核处理器平台,实现高效、可扩展的FFT算法是算法和体系结构设计者共同面临的挑战.文中在众核处理器Godson-T平台上对1-D FFT算法进行了优化和评估,在节省几乎三分之一L2 Cache存储开销的情况下,通过隐藏矩阵转置,计算与通信重叠等优化策略,使得优化后的1-D FFT算法达到3倍以上的性能提升.并通过片上网络拥塞状况的实验分析,发现对于像FFT这样访存带宽受限的应用,增加L2 Cache的访问带宽,可以缓解因为爆发式读写带给片上网络和L2 Cache的压力,进一步提高程序的性能和扩展性.     

FFT Snake模型研究

从3方面入手,对Snakes的外部力引入时空图光流特征,内部力引入傅立叶变换滤波平滑曲线,能量函数极小化方法改为法线方向寻优,从而使FFT Snake模型具有很好的实用价值。实验对比验证,在复杂背景FFT、Snakc模型依然可以有效跟踪运动物体,此时普通Snakes模型必须做大量手动调整。而它同时也解决了帧差等视频分割方法难于识别、提取目标轮廓的问题。FFT Snake模型抓住了运动目标的图像特征,在简单的优化算法下依然可以得到较好的分割效果,并可以用于实时系统。     

网络环境中FFT算法的优化设计

以并行FFT算法为例,研究微机构成的网络计算平台上的并行程序设计与优化问题。由于整个系统的性能取决于网络消息通讯,为减少实施负载平衡策略本身所带来的通信开销,在进行数据分配时尽可能使计算数据局部化。由于异构性,数据分配还应考虑节点机的性能。     

一种基于遗传算法的FFT Snake模型图像分割方法

本文针对Snake模型用于轮廓跟踪时存在抗噪性能差、易于从弱边界溢出的不足,对其能量函数进行改进,提出一种新的FFT Snake模型。该模型较好地解决了以上问题,并将FFT Snake模型的解作为遗传算法的搜索空间,利用遗传算法的全局优化性能,有效地克服了Snake轮廓局部极小化的缺陷,从而可得到对目标更精确的分割。实验结果表明,该方法分割效果十分理想。     

LTE系统中转换预编码的设计及实现

在比较已有FFT实现方法的基础上,提出一种基于FPGA的通用FFT处理器的设计方案。这种FFT实现结构根据不同的输入数据长度动态配置成相应的处理器,可以支持多种基数为2、3、5的FFT计算,硬件资源得到了优化,处理速度及数据精度满足LTE系统中SC-FDMA基带信号的生成要求。     

基于CUDA的高速FFT计算*

针对快速傅里叶算法FFT在图形图像处理和科学计算领域的重要作用,提出了一种基于CUDA的高速FFT计算方法,在分析GPU硬件平台执行模式及FFT算法并行性特征的基础上,采用多线程并行的映射方法实现算法,并从存储层次优化算法。实验结果表明该算法的高效性,优化后的FFT加速比能达到CUFFT库加速比的2-6倍。     

混合专家模型在抗瞬态干扰信号处理中的应用

瞬态干扰脉冲信号可使电子系统功能混乱，计算机死机，通讯、导航等系统紊乱甚至烧毁电子元器件等。通过采取屏蔽、滤波、旁路和瞬变电压抑制等硬件加固措施，可以使干扰信号不至于对仪器设备造成“硬损伤”，但信号可能已经失真，需要采取一定的措施来恢复信号。应用混合专家网络模型，选用能够提高网络学习效率的优化目标函数，可以有效地解决传统信号处理方法难以解决的参杂信号恢复问题，通过仿真试验也证明了ME模型改进算法与常用的FFT低通滤波方法处理特定掺杂信号的效果差异。     

基于存储技术的高速嵌入式处理器的设计与实现

SoPC(片上可编程系统,System on a Programmable Chip)在嵌入式系统中有着广泛的应用,通常用FPGA(现场可编程门阵列,Field Programmable Gate Array)实现.一类嵌入式处理器,例如小波变换处理器、压缩和解压缩处理器、FFT处理器,都可以采用基于存储技术的设计方法.FPGA的片内存储资源相对较少,如何有效地利用FPGA的片内存储资源实现高速的嵌入式处理器成为需要研究的问题.文中以FFT处理器为例说明这种方法的有效性,通过采用一种地址映射调度策略和两种无冲突操作数地址映射方式,减少了所使用的FPGA片内存储资源,提高了处理速度.该FFT处理器在实际系统中起到了关键作用.     

A general purpose subroutine for fast fourier transform on a distributed memory parallel machine

One issue which is central in developing a general purpose FFT subroutine on a distributed memory parallel machine is the data distribution. It is possible that different users would like to use the FFT routine with different data distributions. Thus there is a need to design FFT schemes on distributed memory parallel machines which can support a variety of data distributions. In this paper we present an FFT implementation on a distributed memory parallel machine which works for a number of data distributions commonly encountered in scientific applications. We have also addressed the problem of rearranging the data after computing the FFT. We have evaluated the performance of our implementation on a distributed memory parallel machine, the Intel iPSC/860.     

Portable parallel FFT for MIMD multiprocessors

A portable parallelization of the Cooley–Tukey FFT algorithm for MIMD multiprocessors is presented. The implementation uses the virtual machine for multiprocessors (VMMP) and PVM portable software packages. Since VMMP provides the same set of services on all target machines, a single version of the parallel FFT code was used for shared memory (25-processor Sequent Symmetry), shared bus (MOS-running distributed UNIX) and distributed memory multiprocessor (transputer network and 64-processor IBM SP2). It is accompanied with detailed performance analysis of the implementations. The algorithm achieved high efficiencies on all target machines. The analysis indicates that most overheads are caused by the target architecture and not by VMMP or PVM inefficiencies. The portability analysis of the FFT provides several important insights. On the message passing architecture, the parallel FFT algorithm can obtain linearly increasing speedup with respect to the number of processors with only a moderate increase in the problem size. The parallel FFT can be executed by any number of processors, but generally the number of processors is much less than the length of the input data. The results indicate that the parallel FFT is portable: it achieves very good speedups on either a shared memory multiprocessor with high memory bandwidth or on a message passing multiprocessor without any change in the programs. © 1998 John Wiley & Sons, Ltd.     

适用于多核处理器的簇状片上网络设计

提出一种新型簇状片上网络架构。该架构以二维网状拓扑结构连接各个簇单元,每个簇单元由3个处理器、1个直接访存单元和1个簇共享存储单元组成。基于该架构的多核处理器可以获得更高的通信效率及存储器利用率。在实验系统上实现3 780点的快速傅里叶变换,结果表明,在快速傅里叶变换应用中存储器的利用率能提升至79.5%。     

应用于OFDM系统中的高速FFT处理器设计

针对无线城域网中工作在2GHz~11GHz频带的IEEE802.16a标准,在实现其OFDM系统时提出一种高速而且经济的FFT处理器设计方案。设计中采用了Radix-4的频率抽取算法和并行的蝶型计算单元结构,而且将旋转因子预先存储在ROM中以提高处理器运行的速度。设计方案采用了单个蝶型运算单元以达到控制FFT处理器规模的目的。数据的输入与输出都共用一个存储器,这进一步节约了硬件资源损耗。     

高性能并行FFT处理器的设计与实现

提出一种高性能并行快速傅里叶变换(FFT)处理器的设计方案,采用4个蝶形单元进行并行处理,利用改进的无冲突操作数地址映射方式,保证每个周期同时读取和写入16个数据。给出该处理器的FPGA实现,性能评测结果表明,与其他FFT处理器相比,该并行FFT处理器的性能较优,能满足实际应用需求。     

实序列FFT算法的存储单元图解析方法

为了正确有效地开发实序列FFT的汇编语言程序,提出了以存储单元图的方式解析实序列FFT算法的方法。首先推导了由复序列FFT的实虚部计算实序列FFT的实虚部的公式,指出了计算复序列FFT所包括的级别、蝶组、蝶形三层循环,所涉及的正弦量的计算与存储方式,以及复序列FFT转化为实序列FFT的步骤等。在此基础上利用存储单元图在TMS320C54X汇编语言环境下详细解析了实序列FFT的实虚部计算公式。设计了复序列FFT的实虚部计算的第一级、第二级、第三级到最后级的存储单元图,由复序列FFT的实虚部计算其共轭对称与反对称部分的实虚部的存储单元图,以及由此计算实序列FFT的存储单元图。CCS3.3环境下的仿真结果验证了该解析方法的正确性。     

网络处理器设计中的存储瓶颈问题

网络处理器设计中的存储瓶颈问题是指网络处理进行FIB(forwarding information base)查表、QoS调度、计数器管理等操作对外部控制存储器访问的延时与网络处理性能难以匹配的问题.目前网络处理器设计采用并行处理的方法隐藏访存延时,但由于设计复杂性和功耗问题,大规模并行技术难以在40Gbps以上的网络处理中继续应用.对当前网络处理器中存储瓶颈问题及其解决方法进行研究,指出其局限性,并针对未来更高性能网络处理,如100Gbps接口网络处理的设计提出了一种新的网络处理模型.