Optimizing the Fast Fourier Transform over memory hierarchies for embedded digital systems: a fully in-cache algorithm

Abstract. We present a new algorithm for the Fast Fourier Transform which is a factor of 2 to 4 times faster than our previous records (that often outperformed well-tested library routines) resulting from a scheme that optimizes data locality in the cache. The algorithm was developed and implemented based on the techniques of Conformal Computing: a design approach based on a sys-tematic, rigorous mathematical system (the Mathematics of Arrays (MOA) and the ψ-calculus). The algorithm is presented and discussed using traditional concepts familiar to scientists and engineers. In this paper (the first of a two-part series), new concepts based on Conformal Computing techniques are introduced gradually and illustrated in context. The following paper (the second part in this series), serves as a stand-alone tutorial on Conformal Computing techniques that are developed and illustrated in the context of the new FFT algorithm. The results presented in these two papers are promising for further developments in terms of optimizations over cache and processors. Key words. Fast Fourier Transform, cache, optimization, psi calculu