6 December 1989 Computing The Two Dimensional Fast Fourier Transform On A General Purpose Mesh Connected Multiprocessort
Author Affiliations +
Abstract
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, E. M. Johansson, A. J. De Groot, A. J. De Groot, S. R. Parker, 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
PROCEEDINGS
10 PAGES


SHARE
RELATED CONTENT


Back to Top