MIXED-RADIX FFT FOR IMPROVING CACHE PERFORMANCE (ThuAmPO4)

Author(s) : Ryszard Stasinski (Poznan University of Technology, Poland) Jacek Potrymajlo (Poznan University of Technology, Poland)

Abstract : The increasing difference between processors and dynamic memories speeds causes that the problem of cache perform-ance is an issue of ever growing importance. In the paper it is proposed to increase cache performance in FFT programs by implementing mixed-radix FFTs for N=2îr*Kîs, where K is an odd number, and Ks is close, but smaller than some power of 2. This guarantees that data samples processed in one FFT butterfly have different cache addresses, hence, the number of cache conflicts is substantially diminished. Com-puter simulations for Kîs=243, and 125 show that this is the case, indeed, and that in spite of higher numbers of arith-metical operations for conservative cache miss delays the mixed-radix FFTs do perform better than the radix-2 FFT.

Menu