关键词：快速傅里叶变换算法 偶数基 蝶形计算优化 蝶形网络优化 simd汇编优化 

摘要：快速傅里叶变换(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算法库。

计算机科学杂志要求:

{1}正文公式的序号一律靠右空两格，用(1)、(2)、(3)等表示。

{2}请勿一稿多投，三个月没有得到用稿通知，可自行处理。

{3}来稿一律文责自负。依照《著作权法》有关规定，本刊可对来稿做文字修改、删节及图像处理。凡有涉及原意的修改，则征求作者意见。修改稿逾3个月不寄回者，视作自动撤稿。

{4}标题序号按照“一”、“（一）”、“1”、“第一”或“首先”顺序排列，一般不用“①”号。根据文章具体内容，序号可适当减少，但不可反顺序使用。

{5}文末注明联系电话、详细单位地址邮编。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社