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 Cococcioni
Co-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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1153584
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact