arXiv preprint ·
PACO: A Fully Cache-Oblivious Parallel FFT with One Global Redistribution
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Fast Fourier transforms on parallel machines incur two forms of data movement: processor-local transfers through the memory hierarchy and global redistribution between processors. Four-step FFT organizations switch the active transform dimension with one global transpose-like exchange, but this alone does not yield cache-efficient local computation. Cache-oblivious FFTs achieve asymptotically optimal local memory traffic through recursive layout transformations, whose direct materialization can require extra data-rearrangement passes and global exchanges. We present PACO, a fully cache-oblivious parallel FFT framework that reconciles these objectives. PACO executes LocalFFT -> OneGlobalPermutation -> LocalFFT. Its local stages recursively partition both transform and batch dimensions without knowledge of the cache parameters. Rather than materializing the transpose-like layouts induced by this recursion, PACO defers them, showing that they compose into a base-b digit-reversal permutation that 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. Under an exact base-b slab decomposition in a hybrid ideal-cache/BSP model, PACO computes an N-point DFT exactly with maximum per-processor work $Θ((N/p) \log N)$ and maximum per-processor cache complexity $Θ((N/(pB))(1 + \log_M N))$, using exactly one global redistribution round. PACO returns canonical logical DFT coefficients under a factor-swapped target slab ownership. The single redistribution is necessary under the stated no-replication ownership model, while its communication volume is optimal for the prescribed fused permutation and source-target slab distributions.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Phase-cycled randomized benchmarking of quantum processors: recovering hidden classical noise correlations
Online Draft Co-Training for Speculative Decoding in Large-Scale, Long-Context RL Post-Training
Robust Decentralized Federated Distillation via Multi-Modality Knowledge Collaboration
EStream: Fast and Memory-Efficient MoE Prefill through Expert Virtualization on Mobile NPUs
Parallelism Strategy Chaining for Fast Training Convergence
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.