The Fast Fourier Transform is probably one of the most studied algorithms of all time. New techniques regarding hardware and software are often applied and tested on it, but the interest in FFT is still large because of its applications - signal and image processing, numerical computations, etc. In this paper, we start from a trivial recursive version of the algorithm and we speed it up using AVX-512 Single Instruction Multiple Data (SIMD) instructions on an Intel i7 CPU with native support to AVX-512. In particular, we study the impact of two different storage choices of vector of complex numbers: block interleaving and complex interleaving. Experimental results show that automatic vectorization provides a 10.65% (∼ 1.12×) speedup, while with vectorization done by hand the speedup reaches 33.78% (∼ 1.51×). We have made our code publicly available, which could be helpful for SIMD instructions teaching purposes.
Experiments on Speeding Up the Recursive Fast Fourier Transform by using AVX-512 SIMD instructions
Marco CococcioniCo-primo
2022-01-01
Abstract
The Fast Fourier Transform is probably one of the most studied algorithms of all time. New techniques regarding hardware and software are often applied and tested on it, but the interest in FFT is still large because of its applications - signal and image processing, numerical computations, etc. In this paper, we start from a trivial recursive version of the algorithm and we speed it up using AVX-512 Single Instruction Multiple Data (SIMD) instructions on an Intel i7 CPU with native support to AVX-512. In particular, we study the impact of two different storage choices of vector of complex numbers: block interleaving and complex interleaving. Experimental results show that automatic vectorization provides a 10.65% (∼ 1.12×) speedup, while with vectorization done by hand the speedup reaches 33.78% (∼ 1.51×). We have made our code publicly available, which could be helpful for SIMD instructions teaching purposes.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
