Design of a modern fast Fourier transform and cache effective bit-reversal algorithm

ABSTRACT

This article deals with efficient vectorization of the fast Fourier transform algorithm while focusing on Cooley–Tukey versions with power-of-two radixes. Aside from examples of optimizations for 256 and 512-bit vectors, this work also discusses relations between individual radix-based versions, vectorization and OpenMP threading. Ideas are progressing into a timeless design of the FFT algorithm, which can work with any vector size and radix version through conversion into radix-2 output permutation. Furthermore, the implementation of the Cache Optimized Bit-Reversal algorithm, which doubles the performance of its predecessor, is introduced.

KEYWORDS:

• Fast Fourier transform
• bit-reversal algorithm
• cache utilization
• SIMD
• vectorization
• OpenMP

Data availability statement

The source codes of this project are available in the GitHub repository under the name SAFFT [25].

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the Grant Agency of the Czech Technical University in Prague [grant number SGS20/212/OHK3/3T/18].