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

来源：计算机科学与探索杂志2017年第6期北京时间：

作者：李琨，贾海鹏，曹婷，张云泉

单位：1. 中国科学院 计算技术研究所 计算机体系结构国家重点实验室，北京 100190 2. 中国科学院大学 计算机与控制学院，北京 100190

摘要：快速傅里叶变换（fast Fourier transform，FFT）是用于计算离散傅里叶变换（discrete Fourier transform，DFT）或其逆运算的快速算法，在工程、科学和数学领域的应用非常广泛，例如信号分解、数字滤波、图像处理等。因此，在实际应用中对FFT算法进行细粒度优化是非常重要的。研究了FFT算法常用的分解策略以及FFT算法在大规模集群系统上的并行实现，并提出了相关的优化策略。在此基础上，对多种FFT算法在不同平台上进行了性能评估，并分析了各算法的实现、优缺点及其在大规模计算时的可扩展性。实验结果表明，相关研究有助于对现有的FFT算法进行进一步的优化，以及指导如何在大规模CPU+GPU的异构系统上根据不同需求选择实现性能更优的FFT算法。

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