Memory Bandwidth Efficient Two-Dimensional Fast Fourier Transform Algorithm and Implementation for Large Problem Sizes

Berkin Akin, Peter A. Milder, Franz Franchetti, James C. Hoe
Electrical and Computer Engineering Department, Carnegie Mellon University, Pittsburgh, PA, USA
IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), 2012


   title={Memory Bandwidth Efficient Two-Dimensional Fast {Fourier} Transform Algorithm and Implementation for Large Problem Sizes},

   author={Berkin Akin and Peter A. Milder and Franz Franchetti and James C. Hoe},

   booktitle={IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM)},



Download Download (PDF)   View View   Source Source   



Prevailing VLSI trends point to a growing gap between the scaling of on-chip processing throughput and off-chip memory bandwidth. An efficient use of memory bandwidth must become a first-class design consideration in order to fully utilize the processing capability of highly concurrent processing platforms like FPGAs. In this paper, we present key aspects of this challenge in developing FPGA-based implementations of two-dimensional fast Fourier transform (2D-FFT) where the large datasets must reside off-chip in DRAM. Our scalable implementations address the memory bandwidth bottleneck through both (1) algorithm design to enable efficient DRAM access patterns and (2) datapath design to extract the maximum compute throughput for a given level of memory bandwidth. We present results for double-precision 2D-FFT up to size 2,048-by-2,048. On an Altera DE4 platform our implementation of the 2,048-by-2,048 2D-FFT can achieve over 19.2 Gflop/s from the 12 GByte/s maximum DRAM bandwidth available. The results also show that our FPGA-based implementations of 2D-FFT are more efficient than 2D-FFT running on state-ofthe-art CPUs and GPUs in terms of the bandwidth and power efficiency.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: