A generalized FFT algorithm on transputers
Herman Roebbers, Peter D. Welch, K.C.J. Wijbrans · University of Twente Research Information · 1990
. A generalized algorithm has been derived for the execution of the CooleyTukey FFT algorithm on a distributed memory machine. This algorithm is based on an approach that combines a large number of butterfly operations into one large process per processor. The performance can be predicted from theory. The actual algorithm has been implemented on a transputer array, and the performance of the implementation has been measured for various sizes of the complex input vector. It is shown that the algorithm scales linearly with the number of transputers and the problem size. 1 Introduction A commonly used algorithm in scientific engineering is the Fast Fourier Transform[1]. In various fields, such as control theory, system identification, coding theory and signal processing, the Fast Fourier Transform is a valuable tool. Therefore, a lot of effort has been spent in the past in finding efficient implementations of this algorithm. Most of the implementations in the past made use of fast...