Computing The Two Dimensional Fast Fourier Transform On A General Purpose Mesh Connected Multiprocessort
E. M. Johansson, Anthony J. De Groot, S. R. Parker · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1989
This paper discusses an implementation of the two dimensional fast Fourier transform (FFT) on SPRINT, the Systolic Processor with a Reconfigurable Interconnection Network of Transputers. SPRINT is a 64 element multiprocessor developed at Lawrence Livermore National Laboratory for the experimental evaluation of systolic algorithms and architectures. The implementation is a radix two decimation in time algorithm, valid for an arbitrary sized p x q mesh of processors and an arbitrary sized P x Q complex input array (P, Q, p, and q must all be powers of two). The processors are interconnected with their nearest neighbors along North-South-East-West communication links. The problems of array partitioning, bit reversal, subarray transform computation, and weighted (butterfly) combinations are all discussed. Finally, benchmark results are presented, and speedup and efficiency are discussed.