• Home
• Tools
• Fast Fourier Transform
• Linear Algebra
• Consulting
• Downloads
• Contact

 

Fast Fourier Transform

Performance

The best way to assess the capabilities of a new algorithm/architecture/circuit approach is benchmark it with respect to the “best” available standard.  A good nominal basis for this comparison is a “streaming” (continuous data in and out) type architecture in two FFT sizes, 256 and 1024-points.  After an investigation of different parallel FFT implementations, it was concluded that Altera’s streaming block floating point (BFP) FFTs (Megacore v7.2) were the best in terms of dynamic range, throughput and device utilization.  For example, in 90nm technology Xilinx’s (Virtex-4) and Altera’s (Stratix II) best 16-bit 1024-point FFT times are 3.16 and 3.1 µsec, respectively, yet Altera’s BFP capability provides a higher dynamic range (Xilinx doesn’t offer a BFP streaming FFT).

To facilitate accurate comparisons Altera and base-4 FFT circuits were designed and targeted to the same hardware, specifically to the Altera Stratix III EP3S50F (speed grade -2) for both designs.  Altera Quartus II tools (v7.1, Classic Timing Analyzer) were used to design, synthesize, compile and evaluate the two FFT circuits.  The Quartus II compilation report includes information about resource usage and routing, the Quartus native timing analyzer finds the critical path that determines the maximum clock frequencies and the Quartus PowerPlay Analyzer estimates power dissipation.  (The timing analyzer uses worst case estimates of timing parameters, so that it is likely actual implementations would run at higher speeds than listed in the table.)

Performance results for 256-point and 1024-point streaming base-4 FFT circuits are shown in Table 1 and compared to Altera BFP circuits that have a comparable signal-to-quantization-noise.  The higher throughputs in the base-4 circuits are due to a reduced number of clock cycles per FFT and higher clock speeds associated with the simple implementation.  For the Altera design the clock speed listed in Table 2 is also the complex sample rate.  However, the base-4 design incorporates a special I/O clock and associated circuitry that runs at 389*256/240=415Mhz in the case of the 256-point circuit. This same approach doesn’t work for the 1024-point circuit because the I/O rates approach 600MHz, which is at the limits of Stratix III internal clock speeds and beyond its I/O speeds.  Instead the circuit accepts and generates two complex data streams, one containing even data and the other odd data.  In this way the I/O clock and associated circuitry only have to run at 387*1024/(689*2)=288MHz.

Latency in Table 1 is defined as the time to complete the first  FFT in a series of FFTs, assuming data is streaming into and out of the circuit in normal order.  If normal I/O ordering is not required, the latencies (cycles) for the 256/1024-point base-4 circuits are approximately the same as the throughputs (240/689), and the latencies (cycles) of the Altera circuits are approximately twice the transform size (512/2048).

 

Table 1.  Comparison of Altera BFP streaming FFTs to base-4 implementations for 256 and 1024-point transforms obtained using Quartus II v7.1 tools.

 

 

A different comparison can be made by combining throughput, area (ALMs) and memory in one figure of merit (FOM) and is shown in Table 2.  Here the base-4 FOM is >50% lower for both FFT sizes so it can be seen that the added performance is obtained with reduced resource usage.

 

 

Table 2.  Comparison of base-4 and Altera streaming FFT FOM = Area (ALMs) x Throughput (cycles/DFT) x Memory (bits)/Clock speed (Hz).  

 

Consequently, higher throughput can be obtained with reduced overall usage of resources and with comparable power dissipation.

More recent data obtained using the same underlying hardware, but with slightly newer compilation and synthesis tools (Quartus II v7.2) showed markedly increased performance levels as shown in Table 3.

 

 

Table 3.  Base-4 design FFT results after compilation using Quartus II v7.2 tools

 

 Here complex throughput rates can be seen to be greater than 600MHz for a 1024-point FFT.  The most likely explanation for this improved performance is that the compiler can more effectively localize the computations, reducing interconnect overheads. We are not aware of any other FPGA FFT circuits running with internal clocks at greater than 400MHz maximum frequencies.