大规模集群上多维FFT算法的实现与优化研究  

Implementation and Optimization of Multidimensional FFT Algorithm on Large-Scale Clusters

作　　者：李琨[1,2] 贾海鹏[1] 曹婷[1] 张云泉[1] 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)

机构地区：[1]中国科学院计算技术研究所计算机体系结构国家重点实验室,北京100190 [2]中国科学院大学计算机与控制学院,北京100190

出　　处：《计算机科学与探索》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;中科院高效空间天气预报模式科技创新交叉与合作团队项目~~

摘　　要：快速傅里叶变换(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.

关 键 词：集群 快速傅里叶变换(FFT) 消息传递接口(MPI) 性能优化 

分 类 号：TP302.7[自动化与计算机技术—计算机系统结构]