6 December 1989 Computing The Two Dimensional Fast Fourier Transform On A General Purpose Mesh Connected Multiprocessort
Author Affiliations +
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.
© (1989) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
E. M. Johansson, A. J. De Groot, S. R. Parker, "Computing The Two Dimensional Fast Fourier Transform On A General Purpose Mesh Connected Multiprocessort", Proc. SPIE 1154, Real-Time Signal Processing XII, (6 December 1989); doi: 10.1117/12.962381; https://doi.org/10.1117/12.962381


Massively parallel processors in real-time applications
Proceedings of SPIE (July 01 1990)
Real Time Movement Detection An Algorithm For The...
Proceedings of SPIE (November 01 1989)
Parallel FFT approach for derivative pricing
Proceedings of SPIE (July 27 2001)
ASP: a parallel computing technology
Proceedings of SPIE (September 01 1990)

Back to Top