Share Email Print

Proceedings Paper

Computing The Two Dimensional Fast Fourier Transform On A General Purpose Mesh Connected Multiprocessort
Author(s): E. M. Johansson; A. J. De Groot; S. R. Parker
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 6 December 1989
PDF: 10 pages
Proc. SPIE 1154, Real-Time Signal Processing XII, (6 December 1989); doi: 10.1117/12.962381
Show Author Affiliations
E. M. Johansson, Lawrence Livermore National Laboratory (United States)
A. J. De Groot, Lawrence Livermore National Laboratory (United States)
S. R. Parker, Lawrence Livermore National Laboratory (United States)

Published in SPIE Proceedings Vol. 1154:
Real-Time Signal Processing XII
J. P. Letellier, Editor(s)

© SPIE. Terms of Use
Back to Top