摘要
快速傅里叶变换(fast Fourier transform,FFT)是用于计算离散傅里叶变换(discrete Fourier transform,DFT)或其逆运算的快速算法,在工程、科学和数学领域的应用非常广泛,例如信号分解、数字滤波、图像处理等。因此,在实际应用中对FFT算法进行细粒度优化是非常重要的。研究了FFT算法常用的分解策略以及FFT算法在大规模集群系统上的并行实现,并提出了相关的优化策略。在此基础上,对多种FFT算法在不同平台上进行了性能评估,并分析了各算法的实现、优缺点及其在大规模计算时的可扩展性。实验结果表明,相关研究有助于对现有的FFT算法进行进一步的优化,以及指导如何在大规模CPU+GPU的异构系统上根据不同需求选择实现性能更优的FFT算法。
Fast Fourier transform(FFT)is a fast algorithm which computes the discrete Fourier transform(DFT)of a sequence,or its inverse.Fast Fourier transform is widely used for many applications in engineering,science and mathematics,such as signal decomposition,digital filter and image processing.As a result,the fine-grained optimization of FFT is extremely important in application.This paper studies the typical decomposition strategies of FFT,the parallel implementation of FFT algorithms on large-scale clusters and proposes some optimization strategies.On that basis,this paper also evaluates a variety of FFT algorithms performance on different platforms,then analyzes the implementation,strength and weakness,and the computing scalability on large-scale clusters of these algorithms.The experimental results show that the research of this paper can contribute to the further optimization on existing FFT algorithms,and instruct to choose an FFT algorithm which performance is better on large-scale heterogeneous systems(CPU and GPU)in order to satisfy the specified requirements.
作者
李琨
贾海鹏
曹婷
张云泉
LI Kun;JIA Haipeng;CAO Ting;ZHANG Yunquan(State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences,Beijing 100190, China;School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100190, China)
出处
《计算机科学与探索》
CSCD
北大核心
2017年第6期863-874,共12页
Journal of Frontiers of Computer Science and Technology
基金
国家自然科学基金Nos.61432018
61133005
61272136
61521092
61502450
国家重点研发计划No.2016YFB0200803
中国博士后科学基金No.2015T80139
国家高技术研究发展计划863计划Nos.2015AA01A303
2015AA011505
广东省科技计划项目No.2015B010108006
中科院高效空间天气预报模式科技创新交叉与合作团队项目~~