HOME       UP       PREV       NEXT (Classical HLS: Pros and Cons)  

The Perfect Shuffle Network - FFT Example

A number of algorithms have columns of operators that can be applied in parallel. The FFT is one such example. The operator is commonly called a `butterfly'. The operator composes two operands (which are generally each complex numbers) and delivers two results. The successive passes can be done in place on one array whose values are passed by reference to the butterfly code in the software version.

Our diagram shows a 16-point FFT, but typically applications use hundreds or thousands.

(The code fragment shows a single-threaded implementation that does not attempt to put butterflies in parallel.)

Shuffle Data Flow in the Fast Fourier Transform.
Shuffle Data Flow in the Fast Fourier Transform.

The pattern of data movement is known as a shuffle. It is also used in switching and sorting algorithms.

The downside of shuffle computations for acceleration is that there is no packing of data (structural partitioning of the data array) into spatially-separate memories that works well for all of the passes: what is good at the start is poor at the end.


29: (C) 2012-18, DJ Greaves, University of Cambridge, Computer Laboratory.