Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Berkin Akin, Franz Franchetti and James C. Hoe (Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2014)
FFTs with Near-Optimal Memory Access Through Block Data Layouts
Preprint (1.8 MB)
Published paper (link to publisher)
Bibtex

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 naïve baseline algorithms.

Keywords:
Fast Fourier Transform