Optimised FFT implementation on architectures with sub-word parallelism and SIMD multimedia instructions
Norbert A. Pilz · 2004
In this paper a radix-2 complex fast Fourier transform (FFT) implementation using single instruction multiple data (SIMD) instructions and sub-word parallelism (SWP) is presented. It is shown that data management and memory access are key to unleashing the arithmetic power of highly parallel digital signal processing (DSP) cores. This is hindered only by the commonly used bit-reversal memory access that most multimedia and DSP architectures natively support. In contrary to normal radix-2 multiplication tables, this design uses what is defined as a staged-multiplication-table (SM-table), which allows for consecutive small-vector table loads. In point of fact, this table is regarded to be the single most effective technique in determining the performance of the presented design. This study results in a 1024-point FFT for unconditioned complex data represented in 16-bit fixed-point format that measures 3998 cycles or 13.3 microseconds on the TigerSHARC® architecture at 300 MHz. This provides a sustained performance that tops 70000 transforms per second.