Design of a modern fast Fourier transform and cache effective bit-reversal algorithm. Issue 3 (4th May 2023)

• Record Type: Journal Article
• Authors: Simek, Adam; Šimeček, Ivan
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 38:Issue 3(2023)
• Page Start: 229
• Page End: 248
• Publication Date: 2023-05-04
• Subjects: Fast Fourier transform -- bit-reversal algorithm -- cache utilization -- SIMD -- vectorization -- OpenMP; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2023.2179049
• Languages: English
• ISSNs: 1744-5760

Abstract

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.