High Performance FFT Algorithms for Cache-Coherent Multiprocessors

Abstract

Computing one-dimensional fast Fourier transforms (FFTs) on microprocessors requires different algorithms, depending on whether the problem fits in the data cache. This paper describes efficient algorithms for both cases. Some implementations of out-of-cache one-dimensional FFTs use a six-step approach to reduce the number of cache misses. The six-step approach may be altered into a seven-step approach that allows increased data cache reuse. A natural parallelism is also developed. Performance results using these techniques are given for the Hewlett-Packard HP 9000 V-Class V2250 server.