Effects of Computer Architecture on FFT (Fast Fourier Transform) Algorithm Performance

摘要

This study examines the effects of computer architecture on FFT algorithm performance. The computer architectures evaluated are those of the Cray-1, CDC Cyber 750, IBM 370/155, DEC VAX 11/780, DEC PDP 11/60, DEC PDP 11/50, and Cromemco Z-2D. The algorithms executed are the radix-2, mixed-radix FFT (MFFT), Winograd Fourier Transform Algorithm (WFTA), and prime factor algorithm (PFA). The execution time of each algorithm for different sequence lengths is determined for each computer. Then the number of assembly language instructions executed are determined for the following categories: data transfers, floating point additions and subtractions, floating point multiplications and divisions, and integer operations. The correlation coefficients between the number of assembly language instructions in each category and the algorithm execution speeds are determined for each computer. The values of the correlation coefficients are then related to the computer architectures. The computer architectures are then compared against each other to determine what features are desireable in an FFT processor.