language: en

An FFT algorithm on Vector Intelligent RAM

Kirby Zhang Nathan Slingerland
CS252: Advanced Computer Architecture
Department of Electrical Engineering and Computer Science University of California, Berkeley
May 18, 1998

Abstract We present an implementation of a Fast Fourier Transform on Vector Intelligent RAM architecture. The algorithm computes the Discrete Fourier Transform in O(N log N) time, is self-sorting (no bit-reversed copy phase is required), and has a minimum vector length of p N=2, where N is the number of data points in the transform. An N-element scratch space is required. The performance of this algorithm on VIRAM is analyzed against two variants of the Stockham [12] algorithm.

1 Introduction