Mixed-radix FFT for improving cache performance

The increasing difference between processors and dynamic memories speeds causes that the problem of cache performance 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^rK^s, where K is an odd number, and K^s 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. Computer simulations for K^s=243, and 125 show that this is the case, indeed, and that in spite of higher numbers of arithmetical operations for conservative cache miss delays the mixed-radix FFTs do perform better than the radix-2 FFT.