Title :
FFTS with near-optimal memory access through block data layouts
Author :
Akin, Bilal ; Franchetti, F. ; Hoe, James C.
Author_Institution :
Dept. of Electr. & Comput. Eng., Carnegie Mellon Univ., Pittsburgh, PA, USA
Abstract :
Fast Fourier transform algorithms on large data sets achieve poor performance on various platforms because of the inefficient strided memory access patterns. These inefficient access patterns need to be reshaped to achieve high performance implementations. In this paper we formally restructure 1D, 2D and 3D FFTs targeting a generic machine model with a two-level memory hierarchy requiring block data transfers, and derive memory access pattern efficient algorithms using custom block data layouts. Using the Kronecker product formalism, we integrate our optimizations into Spiral framework. In our evaluations we demonstrate that Spiral generated hardware designs achieve close to theoretical peak performance of the targeted platform and offer significant speed-up (up to 6.5x) compared to naive baseline algorithms.
Keywords :
discrete Fourier transforms; signal representation; 1D FFTs; 2D FFTs; 3D FFTs; Kronecker product formalism; block data transfers; custom block data layouts; fast Fourier transform algorithms; generic machine model; inefficient access patterns; inefficient strided memory access patterns; near-optimal memory access; spiral framework; two-level memory hierarchy; Algorithm design and analysis; Discrete Fourier transforms; Layout; Random access memory; Signal processing algorithms; Spirals; Three-dimensional displays; Discrete Fourier transforms; algorithm design and analysis; data layout; fast Fourier transforms;
Conference_Titel :
Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on
Conference_Location :
Florence
DOI :
10.1109/ICASSP.2014.6854332