GFFT: a Task Graph Based Fast Fourier Transform Optimization Framework
Qinglin Lu, Xinyu Wang, Wenjing Ma, Yuwen Zhao, Daokun Chen, Fangfang Liu · 2023
Fast Fourier Transform (FFT) is a widely used mathematical tool in scientific and engineering applications, and optimizing its performance remains a challenging problem. This paper introduces GFFT, a novel task-graph-based FFT optimization framework that leverages modern hardware and software techniques to achieve high-performance computation. GFFT features a tuning model that uses hardware parameters to optimize FFT decomposition, a bi-directional recursive FFT algorithm that avoids strided load in SIMD implementation, and several graph optimizers inspired by deep learning frameworks to enhance performance. In addition, GFFT utilizes task-based parallelism to exploit performance on multi-core processors and provide potential compatibility with heterogeneous systems. Experimental results demonstrate that GFFT outperforms popular FFT frameworks, achieving an average speedup of 1.17x to FFTW and 1.27x to oneMKL on the Intel Xeon processor, 1.18x to AOCL-FFTW on the AMD EPYC processor, and 2.11x to FFTW on the Sunway multi-core processor with a single thread. Additionally, GFFT achieves an average speedup of 11.48x to FFTW and 1.41x to oneMKL on the Intel Xeon processor, 9.87x to AOCL-FFTW on the AMD EPYC processor with 16-threads.