Design, Optimization, and Implementation of a Universal FFT Processor
DREXEL UNIV PHILADELPHIA PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
There exist Fast Fourier Transform FFT algorithms, called dimensionless FFTs, that work independent of dimension. These algorithms can be configured to compute different dimensional Discrete Fourier Transforms DFTs simply by relabeling the input data and by changing the values of the twiddle factors occurring in the butterfly operations. This observation allows one to design an FFT processor, which with minor reconfiguring can compute one, two, and three dimensional DFTs. In this paper, the authors design a family of FFT processors, parameterized by the number of points, the dimension, the number of processors, and the internal data flow, and show how to map different dimensionless FFTs onto this hardware design. Different dimensionless FFTs have different data flows and consequently lead to different performance characteristics. Using a performance model, the authors search for the optimal algorithm for the family of processors they considered. The resulting algorithm and corresponding hardware design was implemented using FPGA.
- Numerical Mathematics
- Computer Hardware
- Computer Systems