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

1 Introduction

• Four-step organizations can use one global redistribution but do not ensure cache-oblivious local execution; materializing recursive layouts may add local passes or global exchanges.PACO addresses the exact bounded-radix Cooley–Tukey setting.Source: §1 · p. 1
• PACO returns canonical logical DFT coefficients under factor-swapped output ownership, without restoring the input slab distribution.Restoring the initial ownership may require another redistribution.Source: §1 · p. 1
• PACO's batched scheduler recursively partitions transform and batch dimensions without knowing cache capacity or block size.It avoids physical transposes at recursion levels.Source: §1 · p. 2
• Deferred local layout changes compose into a base-b digit-reversal permutation, which PACO fuses with the redistribution that changes the active transform dimension.The middle stage also prepares the layout consumed by the second local stage.Source: §1 · p. 2
• Under the stated memory model, PACO achieves asymptotically optimal local work and cache complexity.The contribution describes a fully cache-oblivious batched Cooley–Tukey scheduler.Source: §1 · p. 2
• One global redistribution is necessary under the no-replication ownership model, and PACO's communication volume is optimal for its prescribed fused slab-to-slab permutation.These claims apply to the stated ownership and permutation contract.Source: §1 · p. 2

2 Model and Main Result

• The model counts one complex scalar as one item and charges BSP communication as g h + L per h-relation.A redistribution round comprises local packing, one BSP h-relation, and local unpacking; packing and unpacking count toward local work and cache misses.Source: §2 · p. 2
• PACO computes the canonical length-N DFT under the specified input ownership and factor-swapped target ownership.The returned coefficients have canonical logical indices, but their physical ownership is factor-swapped.Source: §2 · pp. 2–3
• Exactly one global redistribution round is used, and one round is necessary under the stated owner-computes, no-replication assumptions.Input values are initially unreplicated, and remotely owned values are obtained only through explicit BSP communication.Source: §2 · pp. 2–3
• The optimality claims are scoped: migration is optimal for the prescribed fused permutation, not for all distributed FFT schedules.The work bound applies to the fixed-radix Cooley–Tukey DAG without recomputation; the cache bound matches the lower bound for the local FFT DAGs assigned by PACO.Source: §2 · p. 3

3.1 Two-Factor Cooley–Tukey Decomposition

• The two-factor decomposition uses local length-N1 FFTs, a middle twiddle and redistribution, then local length-N2 FFTs.The ownership change makes each Phase-III transform local to one processor.Source: §3.1 · p. 3

3.2 Lazy Layouts of the Local FFT

• Transpose-free local recursion defers digit-field swaps that compose into a structured base-b digit-reversal layout, rather than arbitrary disorder.Twiddle factors remain correct when evaluated using the logical coordinates represented by each physical item.Source: §3.2 · p. 3

3.3 One Fused Middle Permutation

• The middle permutation cancels Phase I’s deferred layout, swaps factor fields, installs Phase III’s input layout, and changes ownership in one exchange.That ownership change is required because each length-N2 transform needs values distributed across the input slabs.Source: §3.3 · p. 4

3.4 End-to-End Correctness

• PACO computes the canonical DFT coefficients, with each coefficient in the factor-swapped output view under the target ownership.The output’s physical ownership is factor-swapped relative to the input distribution.Source: §3.4 · p. 4
• PACO composes the local operators and fused middle permutation to realize the two-factor four-step DFT operator.The output column coordinate equals k1, so the canonical coefficient resides with its target owner.Source: §3.4 · p. 4

4.1 Cache-Oblivious Batched Local FFT

• The local scheduler recursively splits batch digits and transform dimensions without inspecting cache capacity M or block size B.Its cache-bound proposition assumes an initial contiguous batch width at least B.Source: §4.1 · p. 5

4.2 Fused Redistribution

• Each source-destination processor pair exchanges exactly N/p^2 items in the single balanced BSP exchange.The fused middle stage also applies the top-level twiddle factors and produces the input layout consumed by Phase III.Source: §4.2 · pp. 6, 8
• Packing and unpacking reverse fields through contiguous macro-elements, while the fused twiddle scan adds no separate cache pass.The middle stage combines local packing, one balanced exchange, and local unpacking.Source: §4.2 · p. 8

5.1 Upper Bounds

• Under assumptions (2)–(5), PACO has maximum per-processor local-work and cache-complexity bounds, and performs exactly one global redistribution round.Source: §5.1 · p. 9

5.2 Lower Bounds and Exact Scope

• One redistribution is necessary under owner-computes and no-replication assumptions, while work and cache lower bounds match PACO under fixed-radix, no-recomputation, and exact-slab scopes.The cache lower bound applies to the complete execution under the exact slab decomposition and no arithmetic recomputation.Source: §5.2 · pp. 9–10

5.3 Related Work

• Unlike prior cache-oblivious FFTs that materialize recursive layout transformations, PACO defers them and fuses their composed digit reversal with the ownership change; related distributed FFTs do not establish its local ideal-cache bound and fused-permutation guarantee [5] [6].PACO’s factor-swapped slab contract differs from exact cyclic-to-cyclic transforms that retain cyclic ownership [12].Source: §5.3 · p. 10

5.4 Discussion: Ownership, Permutations, and Composition

• The sole redistribution changes input-column slabs to factor-swapped output-column slabs and fuses the recursive base-b digit reversal, routing exactly N/p^2 items per source-destination pair.The resulting migration cost is optimal for materializing this prescribed permutation between the source and target slab ownerships.Source: §5.2 · p. 9, §5.4 · p. 11

5.5 Limitations

• PACO assumes a fixed power-of-two radix, exact divisibility, aligned slab decomposition, homogeneous ideal-cache and BSP parameters, and no arithmetic recomputation; broader distributions and configurations remain open.It returns canonical coefficient indices under factor-swapped ownership; restoring the original ownership may require another redistribution.Source: §5.5 · p. 11, §5.6 · p. 11

A Deferred Layout Algebra and Local FFT Correctness

• The deferred-layout analysis proves that recursive transform splits do not physically transpose data and that their lazy layouts are base-b digit reversals; layout-aware twiddles use represented logical coordinates without physical permutation.The lazy twiddle is evaluated from the view descriptor.Source: A Deferred Layout Algebra and Local… · p. 13, §A.2 · p. 13

A.3–A.5 Admissible Views and Legal Operations

• Admissible digit-field views preserve distinct physical addresses and a contiguous batch run, while legal batch and transform splits retain the view invariants without exchanging fields.Transform splits reinterpret the same parent working set; the view-closure theorem covers arbitrary interleavings of legal splits.Source: §A.3 · p. 13, §A.4 · p. 14, Outer-batch split · p. 14

A.5 Closure Under Arbitrary Split Interleavings

• Induction shows that outer-batch, contiguous-field, and transform splits preserve Definition 6, including the required digit intervals, partitions, and physical-slot mappings.The transform-split child maps are bijective reindexings, and relabeling T1 → A preserves slots.Source: §A.5 · p. 14
• Fixed assignments are necessary when splits interleave: even nonadjacent fixed slots can leave a contiguous run as the remaining field varies.The example records fixed values for c1 and A1 in F, which—together with P—captures the contiguous-run property.Source: §A.5 · p. 14

• Each transform split changes logical roles, the active transform field, and the descriptor while leaving items in their original physical positions.Source: §A.6 · p. 14
• The first child computes its stage, after which the second child accesses inherited slots through view-defined strides, without an address-to-address copy or transpose.Source: §A.6 · p. 14
• The complete execution's only physical digit permutation is the fused middle permutation; its macro-element digit reversals are components of that one materialization.Source: §A.6 · p. 14

A.7 Output-Layout Local FFT Correctness

• The output-layout traversal implements A_l = P_pi_l Omega_b^l, so physical output coordinate r represents logical coefficient pi_l(r).Source: §A.7 · p. 14

A.9 Local Correctness Summary

• Phase I uses A_m1, the fused middle stage converts its output layout to Phase III's input layout, and Phase III uses B_m2 to produce natural-order coefficients.Source: §A.9 · p. 15

A.8 Input-Layout Local FFT Correctness

• The input-layout traversal implements B_l = Omega_b^l P_pi_l; when its input is digit-reversed, it computes the DFT in natural order.Source: §A.8 · p. 15

B Cache-Oblivious Batched Local FFT

• The scheduler is independent of cache capacity M and block size B, and its analysis supplies the cache analysis underlying Proposition 1.Source: §A.8 · p. 15, B Cache-Oblivious Batched Local FFT · p. 15

B.1 Scheduler Pseudocode

• The scheduler uses batch splits when s ≥ n and balanced digit-aligned transform splits when s < n, with twiddles fused into the second child group.Source: §B.1 · p. 15

• Each logical transform incurs O(n log_b n) leaf, butterfly, and twiddle work across its radix-b levels.Source: §B.2 · p. 16
• Batch-split administration and constant-size leaf calls contribute O(ns) additional work over s transforms.Source: §B.2 · p. 16
• Because transform splits are view transformations rather than physical transposes, they incur no additional Θ(ns) rearrangement pass at each split.Source: §B.2 · p. 16

B.3 Recursion Depth and Stack Space

• The scheduler has O(log(ns)) total recursion depth and uses O(log(ns)) words of stack space.Along each root-to-leaf path, batch splits number at most O(log_b(ns)).Source: §B.3 · p. 16

B.4 Analytical Cache-Fitting Frontier

• The cache-fitting frontier is an analysis device: the scheduler continues recursively and never tests M, B, or the fitting condition.A maximal fitting view groups descendant work that can remain resident in the ideal cache.Source: §B.4 · p. 16

B.5 Frontier Geometry

• A non-fitting view can first become cache fitting only after a batch split, and each nonroot maximal fitting view has mass within a factor b of the fitting threshold.Transform splits preserve each child group’s mass.Source: §B.5 · p. 16, §B.4 · p. 16

B.6 Contiguous Width at the Frontier

• Every maximal cache-fitting view has contiguous width Ω(B), provided the root begins with contiguous width at least B.This width condition supports the block-footprint bound used downstream.Source: §B.6 · p. 17

B.7 Transform Length and Number of Transform Splits

• The number of transform splits before the frontier is O(1 + log_M n), based on the shrinking transform length along balanced splits.The proof also bounds transform length at a frontier reached after a transform split.Source: §B.7 · p. 17

B.8 Block Cover of a Frontier View; B.9 Total Frontier Mass

• A frontier view’s descendant execution costs the same asymptotic cache misses as its block cover, while total frontier mass is at most ns·2^K for at most K transform splits.The block-cover argument uses contiguous runs of length c, with c = Ω(B).Source: §B.8 · p. 17, §B.9 · p. 18

B.10 Cache Complexity

• A cache-fitting frontier analysis bounds each view’s descendant cache cost by its block footprint and controls total frontier mass through the number of transform splits.The resulting argument establishes the batched local-FFT cache-complexity theorem under the tall-cache assumption and root-width condition.Source: §B.10 · p. 18, §B.9 · p. 18

B.11 Application to the Two PACO Local Phases

• The two local-phase cache analyses combine because log_M N1 + log_M N2 = log_M N, with the fused middle stage’s linear cache cost absorbed.Phase I requires slab width N2/p ≥ B for direct application of the local bound.Source: §B.11 · p. 18

C Data Movement: Local Primitives and the Fused Redistribution

• The data-movement appendix specifies primitives on contiguous macro-elements rather than individual scalars, and composes them into the fused redistribution procedure.In both local applications, macro-element length is at least one cache line.Source: C Data Movement: Local Primitives and… · p. 18

C.1 Macro-Element Digit Reversal

• Macro-element digit reversal swaps each nontrivial two-cycle once in place; for element length s ≥ B, it costs O(ns) work and O(ns/B) cache misses.Each contiguous macro-element is scanned at most once.Source: §C.1 · pp. 18–19

C.2 Fusing Destination-Indexed Unary Operations

• Destination-indexed twiddle multiplication is applied as entries are written during digit reversal, requiring no separate pass.For this middle stage, the coefficient uses the destination macro-element and global column.Source: §C.2 · p. 19

C.3 Use in Phases I and III

• Both local field reversals cost O(N/p) work and O(N/(pB)) misses when macro-element widths are at least B.The width condition provides spatial locality, avoiding a scalar-level cache-oblivious digit-reversal traversal.Source: §C.3 · p. 19

C.4 Local Rectangular Transposition

• The local rectangular transpose uses Frigo et al.’s algorithm [8], with O(rc) work and O(1 + rc/B) misses for an r × c rectangle.This is the per-block transpose accounting; aggregation across a processor’s blocks is handled separately.Source: §C.4 · p. 19

C.5 The Per-Processor Fused Redistribution Procedure

• Each processor packs by reversing its N1 field with fused twiddles, exchanges balanced blocks once, transposes received blocks, then reverses the N2 field.The incoming raw regions form the mandatory target slab; the only auxiliary storage is a single transpose scratch array.Source: §C.5 · pp. 19–20

C.6 Line-by-Line Correctness

• The procedure maps each Phase-I coordinate (a,c) to (π_m2(c), π_m1(a)) and returns canonical DFT coefficients under the factor-swapped target ownership.The resulting layout is the digit-reversed input layout consumed by the second transform group.Source: §C.6 · p. 20

C.7 Cost and Workspace

• The fused redistribution’s local work is O(N/p), cache misses are O(N/(pB)), and non-output workspace is one N/p^2-item transpose buffer plus O(log N) stack words.The fused twiddle adds Θ(N/p) arithmetic without an extra cache pass.Source: §C.7 · p. 20

D Lower Bounds: Deferred Proofs

• The main text establishes lower bounds for one redistribution round, migration for the prescribed fused permutation, and maximum per-processor work; the detailed cache lower-bound proof is deferred here.The appendix completes the maximum per-processor cache lower bound’s proof.Source: D Lower Bounds: Deferred Proofs · p. 20
• The cache lower-bound proof imports an FFT-DAG boundary theorem, converts boundary growth to block-cache misses, extends it to disjoint batches, and applies it to PACO’s local phases.The argument assumes arithmetic vertices of the fixed-radix Cooley–Tukey DAG are not recomputed.Source: D Lower Bounds: Deferred Proofs · p. 20
• The lower bounds apply when each radix-b butterfly is expanded into its constituent radix-2 layers; treating a complete radix-b DFT as one atomic vertex is outside their scope.Here b = 2^t with t = O(1).Source: D Lower Bounds: Deferred Proofs · p. 20

D.1 Imported FFT-DAG Input-Boundary Theorem

• For the radix-2 FFT DAG, any set of at least k log2(4k) noninput vertices has an input boundary of at least k.This graph-theoretic boundary-growth result is imported from prior work.Source: §D.1 · p. 20

D.2 From Input Boundaries to Block Cache Misses

• If a schedule segment requires at least k boundary values, it incurs at least ⌈(k−M)/B⌉ cache misses when k > M.At most M boundary values can begin resident, and each loaded block supplies at most B missing values.Source: §D.2 · pp. 20–21

D.3 Finite Block-Aware Lower Bound for One FFT DAG

• For every integer k > M, any no-recomputation topological schedule of one radix-2 FFT DAG satisfies the finite block-aware cache lower bound.The proof partitions execution into complete segments and applies the boundary-to-misses bound to each.Source: §D.3 · p. 21

D.4 A Stronger Constant-One Asymptotic Bound

• Under its stated conditions, every no-recomputation schedule has a miss-only lower bound with normalized constant at least 1 − o(1), not a matching upper bound.The passage explicitly does not assert that PACO or any known schedule attains a (1 + o(1)) upper bound.Source: §D.4 · p. 21

D.5 Disjoint Unions of FFT DAGs

• For a disjoint batch of FFT DAGs, an input boundary of at least k follows when a vertex set has size at least 4k log2(4k); the constant 4 is not claimed tight.Source: §D.5 · p. 21

D.6 Cache Lower Bound for a Batch of Local FFTs

• The batch lower bound combines boundary-driven misses with the independent compulsory-input scan, yielding an asymptotic cache lower bound under the stated initial-cache or batch-mass conditions.The stated conditions are an initially empty cache or ns at least a sufficiently large constant times M.Source: §D.6 · pp. 21–22

• Each processor evaluates N2/p transforms of length N1 in Phase I and N1/p transforms of length N2 in Phase III, with batch size N/p in both phases.Source: §D.7 · p. 22
• Under exact slab decomposition and no arithmetic recomputation, the two local FFT phases and complete execution require Ω(N/(pB)(1 + log_M N)) cache misses per processor.Source: §D.7 · p. 22
• For N/p ≥ κM, applying Corollary 36 to each sequential phase yields bounds that sum using log_M N1 + log_M N2 = log_M N.Source: §D.7 · p. 22
• For N/p < κM, divisibility by p implies N1,N2 ≤ N/p and N < κ²M², so 1 + log_M N = O(1); Phase I touches Θ(N/p) distinct inputs from an empty cache.Source: §D.7 · p. 22
• Identical batch sizes make the lower bound apply to maximum per-processor cost, and the fused middle stage can only add cache misses.Source: §D.7 · p. 22