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

Abstract: 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.

Key words: cluster, fast Fourier transforms (FFT), message passing interface (MPI), performance optimization