Implementation of an N*N Fourier transform in order N instructions on a SIMD array
Arthur W. Chang, John E. Selvage, Arthur V. Forman, P. Walker · 2003
Summary form only given. The discrete Fourier transform has been implemented on a single-instruction, multiple-data (SIMD) machine. The implementation demonstrates how an algorithm that is unsuited for use on a sequential machine can be very effective in a parallel machine. The SIMD machine is based on the Geometric Arithmetic Parallel Processor (GAPP). The Bluestein chirp algorithm, a variation of the chirp-Z algorithm, is the key to parallelizing the Fourier transform. When the chirp-Z is adapted to the parallel architecture of the GAPP array, the transform is reduced to O(N) operations as compared to O(N*N log N) on sequential machines. The GAPP array used to implement this algorithm is a 108*384 array. Each processing element is a one-bit serial ALU with 128 bits of RAM. Each processor is connected to its four nearest neighbors (north, south, east, and west) in a mesh configuration.>