Search papers, labs, and topics across Lattice.
The paper introduces a graph-based approach to optimize FFT implementations by modeling instruction scheduling and cache effects. They formulate shortest-path problems on directed acyclic graphs, with nodes representing computation stages and edge weights representing instruction costs, both in context-free and context-aware variants. Applying this to Apple M1 NEON, the context-aware Dijkstra search discovers a novel radix arrangement (R4 -> R2 -> R4 -> R4 -> Fused-8) achieving 29.8 GFLOPS, a 34% improvement over the context-free approach and a 5.2x improvement over pure radix-2.
Forget hand-tuning FFTs: a graph search that models cache effects finds a 5.2x faster implementation on Apple M1 by sandwiching radix-2 passes between radix-4 passes.
An $N$-point FFT admits many valid implementations that differ in radix choice, stage ordering, and register-blocking strategy. These alternatives use different SIMD instruction mixes with different latencies, yet produce the same mathematical result. We show that finding the fastest implementation is a shortest-path problem on a directed acyclic graph. We formalize two variants of this graph. In the \emph{context-free} model, nodes represent computation stages and edge weights are independently measured instruction costs. In the \emph{context-aware} model, nodes are expanded to encode the \emph{predecessor edge type}, so that edge weights capture inter-operation correlations such as cache warming -- the cost of operation~B depends on which operation~A preceded it. This addresses a limitation identified but deliberately bypassed by FFTW \citep{FrigoJohnson1998}: that optimal-substructure assumptions break down ``because of the different states of the cache.'' Applied to Apple M1 NEON, the context-free Dijkstra finds an arrangement at 22.1~GFLOPS (74\% of optimal). The context-aware Dijkstra discovers $\text{R4} \to \text{R2} \to \text{R4} \to \text{R4} \to \text{Fused-8}$ at 29.8~GFLOPS -- a $5.2\times$ improvement over pure radix-2 and 34\% faster than the context-free result. This arrangement includes a radix-2 pass \emph{sandwiched between} radix-4 passes, exploiting cache residuals that only exist in context. No context-free search can discover this.
