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

• 作者: 张广婷 袁良 贾海鹏 龚彤艳
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 快速傅里叶变换算法 偶数基 蝶形计算优化 蝶形网络优化 SIMD汇编优化 高性能FFT库
• 年，卷（期）: 2020,（1）
• 所属期刊栏目: 计算机体系结构
• 页码范围: 31-39
• 页数: 9页
• 分类号: TP311.52
• 字数: 8227字
• 语种: 中文
• DOI: 10.11896/jsjkx.190900179

摘要

快速傅里叶变换(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算法库.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贾海鹏	中国科学院计算技术研究所计算机体系结构国家重点实验室	11	94	5.0	9.0
2	袁良	中国科学院计算技术研究所计算机体系结构国家重点实验室	11	25	2.0	4.0
3	龚彤艳	贵州财经大学信息学院	2	1	1.0	1.0
7	张广婷	中国科学院计算技术研究所计算机体系结构国家重点实验室	3	2	1.0	1.0