Computing The Two Dimensional Fast Fourier Transform On A General Purpose Mesh Connected Multiprocessort

E. M. Johansson; A. J. De Groot; S. R. Parker

doi:10.1117/12.962381

6 December 1989 Computing The Two Dimensional Fast Fourier Transform On A General Purpose Mesh Connected Multiprocessort

E. M. Johansson, A. J. De Groot, S. R. Parker

Author Affiliations +

Proceedings Volume 1154, Real-Time Signal Processing XII; (1989) https://doi.org/10.1117/12.962381
Event: 33rd Annual Technical Symposium, 1989, San Diego, United States

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.

Citation Download Citation

E. M. Johansson, A. J. De Groot, and 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); https://doi.org/10.1117/12.962381

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available