PACO: A Fully Cache-Oblivious Parallel FFT with One Global Redistribution

Parallel fast Fourier transforms (FFTs) face two distinct data-movement costs: processor-local transfers through the memory hierarchy and global redistribution between processors. Four-step FFT organizations reduce global communication to a single transpose-like exchange by switching the active transform dimension, but they do not guarantee cache-efficient local computation. Cache-oblivious FFTs achieve asymptotically optimal local memory traffic via recursive layout transformations, yet materializing those layouts can introduce extra data-rearrangement passes and additional global exchanges. PACO addresses this tension by combining cache-oblivious local stages with a single, fused global permutation. The framework targets exact N-point DFT computation under a hybrid ideal-cache/BSP model with an exact base-b slab decomposition.

PACO executes three stages: LocalFFT → OneGlobalPermutation → LocalFFT. The local stages recursively partition both the transform and batch dimensions without knowledge of cache parameters. Instead of materializing the transpose-like layouts induced by this recursion, PACO defers them and shows that they compose into a base-b digit-reversal permutation. This permutation is fused with the redistribution already required to change the local transform dimension. The resulting middle stage is a perfectly balanced parallel cache-oblivious digit-reversal permutation in which each source-destination processor pair exchanges exactly $N/p^2$ elements. The framework assumes an exact base-b slab decomposition and a hybrid ideal-cache/BSP model. The single redistribution is necessary under the stated no-replication ownership model, and its communication volume is optimal for the prescribed fused permutation and source-target slab distributions. PACO returns canonical logical DFT coefficients under a factor-swapped target slab ownership.