Technical report · single-core geometry vs. parallel geometry

Depth, wire-depth & energy under the simplified Dally model — and how they compare to the spatial computer

We analyze the algorithms of Gianinazzi et al.'s spatial computer paper (broadcast, reduce, scan, rank selection, sorting, cubic and Strassen matrix multiplication — plus FFT as a bonus) under the simplified explicit-communication model of the simplified-dally-model repo: a single core, memory in the upper half-plane, reads priced at Manhattan distance, writes and arithmetic free. For each algorithm we derive energy, work, depth, and wire-depth, then set the results against the spatial computer's published bounds. The bounds were derived by four parallel analyses (one per problem group), cross-checked at their overlaps and against a separate adversarial verification pass; derivation sketches are included so the results can be checked.

§1 · Setup

Two ways to charge for distance

Both models take Bill Dally's position seriously: the dominant cost of computation is moving data, and movement should be priced by physical (Manhattan) distance. They differ in what the machine looks like.

Model A — simplified Dally model (single core) One sequential core at the origin. Memory cells indexed 1, 2, 3, … fill the upper half-plane; cell i sits at Manhattan distance ⌈√i⌉ (the cells at distance k form a diagonal shell of 2k−1 cells; k² cells lie within distance k). Programs are three-address code op dest,src1,src2. Reads are priced at the source cell's distance; writes and arithmetic are free; the core keeps no state between instructions. The caller chooses where inputs and outputs live and reads each output cell once at the end; this report adopts the compact prefix 1..n for inputs — any other placement only raises costs.

Model B — spatial computer (Gianinazzi et al., arXiv 2205.04934) An unbounded 2-D grid of processors, each with constant memory; in each synchronous step a processor may send one word-sized message to any other processor at energy cost = Manhattan distance. Metrics: energy E (total distance of all messages), depth D (longest chain of consecutively dependent messages), wire-depth D_w (largest total distance along a dependency chain). An input of n words lives on a √n×√n subgrid, one word per processor.

The comparison is fair in a way worth stating: for an input of n words, both machines occupy Θ(n) silicon area and both charge one unit of energy per word per unit of Manhattan distance. Model A is "all that area is passive memory, one core computes"; Model B is "every cell of that area is a tiny processor." The bounds below quantify exactly what that architectural choice buys — and what it doesn't.

Model A's memory geometry

Cell i at Manhattan distance ⌈√i⌉ from the core; shells of 2k−1 cells; the first 16 cells shown (cf. the repo's figure)

§2 · Metrics

What "depth" means on a one-core machine

The spatial computer's E / D / D_w are defined over messages. Model A as specified is sequential, so the mapping needs care. Two readings are honest, and we report both:

Reading 1 — as-specified (serial execution). The core issues one instruction at a time. Then depth degenerates to the instruction count (D = W) and wire-depth to total read cost (D_w = E). True, but uninformative.
Reading 2 — dependency-DAG (used in our tables). Keep Model A's reads and placement, but ask what the data-dependency DAG of the program permits if instruction-level parallelism were unlimited: D = critical path in instructions; D_w = max over dependency chains of the sum of per-instruction read distances (the two reads of one instruction travel in parallel, so each instruction contributes its larger read distance). This is the right analogue of the spatial computer's latency metrics: it measures how long signals must travel end-to-end at unit wire speed. It always obeys the geometric floor D_w ≥ distance of the farthest input the output depends on.

The touch bound — Model A's master lower bound. Any algorithm whose output depends on all n inputs must read every input cell at least once (an unread cell could be perturbed without changing the execution). Reading cells 1..n once costs S(n) = Σ_k≤n⌈√k⌉ = m(m+1)(4m−1)/6 for n = m², i.e. S(n) = (2/3)·n^3/2 + O(n) — and cells 1..n are the cheapest n distinct cells, so no placement does better. Model A therefore has a Θ(n^3/2) floor for everything that reads its input. The same exponent appears in the spatial computer as the permutation lower bound (its Lemma 3.1: permuting n words costs Ω(n^3/2)) — but there it gates only data rearrangement, not mere touching. That one difference generates most of the table below.

§3 · Results

The bounds, side by side

Θ-bounds unless marked. Model A columns are this report's derivations (Reading 2 for D and D_w; E excludes the caller's final output reads — for size-n outputs those add another (2/3)n^3/2, never changing the asymptotics except for broadcast). Spatial columns are the paper's Table 1. For matmul, matrices are n×n (N = n² words per matrix), and both models place them in Θ(n²) area.

Problem	Dally E	Dally W	Dally D (DAG)	Dally D_w (DAG)	Spatial E	Spatial D	Spatial D_w
Broadcast (1→n)	Θ(n) ^a	n	1	1 ^a	Θ(n)	O(log n)	O(√n)
Reduce (sum of n)	Θ(n^3/2) exact ^b	n−1	⌈log₂ n⌉	Θ(√n)	Θ(n)	O(log n)	O(√n)
Scan (prefix sums)	Θ(n^3/2) tight ^c	Θ(n)	O(log n)	Θ(√n)	Θ(n)	O(log n)	O(√n)
Rank selection	Θ(n^3/2) ^d	Θ(n)	O(log² n) whp	Θ(√n) whp	Θ(n)	O(log² n)	O(√n)
Sorting	Θ(n^3/2) flat ^e	Θ(n log n)	O(log² n) ^f	O(√n·log² n) ^f	Θ(n^3/2)	O(log³ n)	O(√n)
Matmul — cubic DAG	Θ(n³ log n)	Θ(n³)	Θ(log n)	Θ(n)	Θ(n³)	Θ(n)	O(n)
Matmul — Strassen	Θ(n³) optimal ^g	Θ(n^2.807)	Θ(log n)	Θ(n)	O(n³ √log n)	O(n^0.861)	O(n √log n)
FFT (bonus)	Θ(n^3/2)	Θ(n log n)	Θ(log n)	Θ(√n)	not analyzed in the paper ^h

a Free-writes artifact: n copy instructions, each reading cell 1 at distance 1; the destinations' distances are never charged. If the caller reads the n copies, that adds (2/3)n^3/2. b Fold into a distance-1 accumulator is exactly optimal: E = S(n)+n−2, matching a read-counting lower bound instruction for instruction; the log-depth tree variant pays ≈1.55× more energy. c (2/3)n^3/2 algorithm + (2/3)n^3/2 caller output reads; both terms individually optimal. d Randomized (Floyd–Rivest-style): expected E = (2/3)n^3/2(1+o(1)) — touch-optimal including the constant; deterministic (median-of-medians): Θ(n^3/2) worst case. e No log or log log factor; see §4. f Bitonic-network schedule, which costs E = Θ(n^3/2 log² n): in Model A no single schedule we found is simultaneously E-optimal and shallow (the E-optimal mergesort has D = Θ(n log log n)). g Touch-optimal; beats the cubic DAG by a genuine Θ(log n) factor in Model A. h A four-step schedule on the spatial computer gives O(n^3/2) energy (our sketch, not the paper's); its PRAM-simulation theorem gives O(n^3/2 log n) generically. The spatial scan row assumes input and output stored in Z-order (the paper's own footnote to Table 1); Cannon's wire-depth is printed in the paper's O-form (its Lemma 4.2 proves the Θ-form).

Exact leading constants (n = m², touch-tight problems)

Quantity	Exact / leading term	Status
Touch bound S(n) = Σ⌈√k⌉	m(m+1)(4m−1)/6 = (2/3)n^3/2 + O(n)	exact closed form
Reduce (fold)	E = S(n) + n − 2	exactly optimal
Scan (running sum, incl. output reads)	E = 2S(n) + O(n) = (4/3)n^3/2 + O(n)	tight to leading order
Selection (randomized, expected)	E = (2/3)n^3/2(1 + o(1))	touch-tight incl. constant (medium conf.)
Sorting (R = log²n mergesort, excl. outputs)	E ≤ (4√2/3)n^3/2(1+o(1)) ≈ 1.89·n^3/2	layout-dependent; ≤2.83× touch
FFT (four-step, incl. outputs)	E ≈ 2n^3/2 + O(n^5/4)	Θ tight; constant gap ≈1.5×
Any n×n matmul: input touch	E ≥ (4√2/3)n³ ≈ 1.89·n³	Strassen achieves Θ(n³)

§4 · Derivations

Where each bound comes from

A1Broadcast Dally Θ(n) vs spatial Θ(n) — but for opposite reasons

One copy dest_j, 1 per destination: n instructions, each paying a single distance-1 read of cell 1; destinations are written free. E = n exactly (lower bound: three-address code writes one cell per instruction, and since the core keeps no state, each write of a runtime value must read some cell holding it, at distance ≥ 1 — immediates like the instruction set's set can't produce a value known only at run time). All copies are independent: D = D_w = 1. This is a model artifact: free writes mean fan-out costs nothing and the value "teleports" — Model A charges the Θ(n^3/2) only if the caller later reads the n copies. The spatial computer charges the movement honestly (Θ(n) energy through a recursive quadrant tree) and its wire-depth Ω(√n) records the physical fact that the value must travel to the far corner. Dally's actual CACM position prices all transport; the simplification "writes are free" is what breaks the symmetry here.

Dally E

n exact

Dally D / D_w

1 / 1

Spatial E / D / D_w

Θ(n) / O(log n) / O(√n)

A2Reduce the cleanest √n separation

Fold is exactly optimal. Keep the accumulator in cell 1; execute add 1,1,i for i = 2..n at cost 1 + ⌈√i⌉ each: E = S(n) + n − 2. Matching lower bound: every input must be read once from its resident cell (that's S(n)), and any n-to-1 computation needs ≥ n−1 binary instructions whose remaining n−2 operand reads cost ≥ 1 each. Curiously the balanced tree — optimal in every parallel model — is worse here: with level-ℓ partials compacted into cells 1..n/2^ℓ, its per-level read costs form the series (2/3)n^3/2·Σ2^−3ℓ/2, totalling ≈1.03n^3/2 ≈ 1.55× fold. The tree's payoff is latency: D = ⌈log₂n⌉ and D_w ≤ (2+√2)√n ≈ 3.4√n (a geometric distance series along any leaf-to-root chain), versus fold's chain that passes every read (D = n−1, D_w ≈ (2/3)n^3/2). Spatial computer: Θ(n) energy — the grid sums in place; nothing ever travels farther than its quadrant. Verdict: turning memory into processors buys a full √n factor of energy on aggregation, the single strongest separation in this report. Worked instance (n = 16): Dally E = 50+16−2+1 = 65 including the output read; the spatial reduce on a 4×4 grid spends exactly 24.

Dally E

S(n)+n−2

Dally D / D_w

⌈log₂n⌉ / ≈3.4√n

Spatial E / D / D_w

Θ(n) / O(log n) / O(√n)

A3Scan (prefix sums) same story as reduce, plus an output subtlety

Running sum with the accumulator in cell 1, writing prefix i back into the just-freed cell i (dead the moment it was read): E = S(n) + 2n + O(1) excluding output reads (the O(1) covers preserving prefix₁ before the accumulator overwrites cell 1) — and the caller's n output reads add exactly one more S(n), for (4/3)n^3/2 total, which a matching two-part lower bound (algorithm reads ≥ S(n); caller reads n distinct cells ≥ S(n)) shows is tight to leading order. A pitfall our analysis flagged: writing prefix i directly to cell i inside the add (add i,1,i-style) forces the next step to re-read the running sum from distance ⌈√i⌉ and doubles the constant. For latency, a Blelloch up/down sweep with temporaries compacted into shrinking near-core blocks gives D = 2⌈log₂n⌉+O(1) and D_w = Θ(√n) at a 2–4× energy premium. Spatial: Θ(n) via the Z-order quadrant tree — again the √n separation, again because partial sums never leave their quadrants.

Dally E (incl. out)

(4/3)n^3/2 tight

Dally D / D_w

O(log n) / Θ(√n)

Spatial E / D / D_w

Θ(n) / O(log n) / O(√n)

A4Rank selection (median) sampling cannot save the single core

In the spatial paper, selection is the marquee result: Θ(n) energy, polynomially below the Ω(n^3/2) sorting floor, because two sampled pivots let most elements be discarded in place — they are inspected locally but never shipped anywhere. Model A enjoys no such escape: the adversary argument forces every cell to be read (an unread element could straddle the rank-k answer), so E ≥ S(n) = (2/3)n^3/2. That floor is achievable — a Floyd–Rivest-style algorithm reads a ~n^2/3 sample (≤ n^7/6 cost), selects two pivots, does one partition pass that compacts the O(n^2/3log n) survivors into the freed near-core cells (free writes!), and recurses — for expected E = (2/3)n^3/2(1+o(1)), touch-optimal including the constant (deterministic median-of-medians stays Θ(n^3/2)). The punchline: the spatial computer's cleverest energy win survives only because its compute is co-located with its data; move the same idea to a single core and geometry claws back the whole √n factor. DAG metrics: D = O(log² n) whp, D_w = Θ(√n) whp (geometrically shrinking survivor sets).

Dally E

(2/3)n^3/2(1+o(1))

Dally D / D_w

O(log²n) / Θ(√n) whp

Spatial E / D / D_w

Θ(n) / O(log²n) / O(√n)

A5Sorting the tie: Θ(n^3/2) in both models

Upper bound, and it is flat. R-way mergesort with R = log²n and one crucial discipline: never recurse on far-resident data — copy each run into the compact prefix first (that copy is the level's touch pass), sort there, park the sorted run high (writes free), then R-way merge with a heap kept in the first O(R) cells (heap reads cost O(√R) = O(log n) each). The recurrence S(m) = R·S(m/R) + (4√2/3)m^3/2 + O(m√R·log R) has level costs decaying like 1/log n per level — summing to (4√2/3)n^3/2(1+o(1)) ≈ 1.89n^3/2, no log, no log log. (The 4√2/3 constant is for this particular layout — runs parked in cells m+1..2m; other natural accountings land between ≈1.2 and ≈2.4·n^3/2. The flat-Θ conclusion is layout-independent.) (Contrast: classic full-pass 2-way mergesort re-touches all n words every pass: Θ(n^3/2log n).) Lower bound: touch, Ω(n^3/2); the comparison term 2n·log₂n only matters below n ≈ 850. Spatial: Θ(n^3/2) as well — there it is the permutation bound (elements must physically cross the grid), matched by 2-D mergesort. So the two models agree on sorting's energy for genuinely different reasons: Model A pays to see the data, Model B pays to move it. All that parallelism buys is time: depth O(log³n) versus a serial machine's Θ(n log n) instructions. One more Model A wrinkle: energy and depth resist joint optimization — bitonic gets D = O(log²n) but re-touches everything each stage (E = Θ(n^3/2log²n)), while the E-optimal mergesort is nearly serial.

Dally E

≈1.89·n^3/2

Dally W

Θ(n log n)

Dally D / D_w (bitonic)

O(log²n) / O(√n log²n)

Spatial E / D / D_w

Θ(n^3/2) / O(log³n) / O(√n)

A6Matrix multiplication — cubic DAG a real Θ(log n) penalty for classical matmul

n×n matrices, 2n² input words in cells 1..2n² (so distances reach √2·n and the touch bound is (4√2/3)n³ ≈ 1.89n³). Upper: cache-oblivious recursive blocking with copy-in — a call on b×b blocks copies operand sub-blocks into a compact child region (O(b²) reads at distance O(b)), recurses 8-fold, re-reads partials for the 4 block-additions: M(b) = 8M(b/2) + Θ(b³). Every one of the log₂n levels costs Θ(n³): M(n) = Θ(n³ log n). (Naive triple loop: Θ(n⁴); one-level √n-blocking: Θ(n^3.5); the full recursion is what removes the polynomial penalty.) Lower, and this is the technical heart of the report: a Hong–Kung/red–blue argument adapted to free writes — phases of 2S loads; Loomis–Whitney bounds each phase's multiply-adds by O(S^3/2) once free-stored partial sums that are later reused are charged to the future loads that bring them back (free stores alone would otherwise let a phase touch unboundedly many C-entries) — yields a loads-only bound Q(S) = Ω(n³/√S) for S ≤ n²/81, assuming no recomputation of product terms. Setting S = d² (the cells within distance d) and summing over dyadic d: each of the ~log₂n scales contributes Ω(n³) of read cost, so E = Ω(n³ log n). The recursion is optimal; the log n gap to the spatial computer's Cannon (Θ(n³), in-place systolic shifts, no hierarchy to traverse) is real for the cubic DAG (under the standard no-recomputation assumption of I/O lower bounds).

Dally E

Θ(n³ log n)

Dally D / D_w

Θ(log n) / Θ(n)

Spatial (Cannon)

Θ(n³) / Θ(n) / Θ(n)

A7Matrix multiplication — Strassen the inversion: Strassen wins in Model A, Cannon wins in Model B

Run Strassen with the same copy-in discipline (operands of a size-b call held compactly at distance O(b); the 7 operand combinations formed one at a time — sequential execution lets scratch be reused, so the working set stays O(b²)): ST(b) = 7·ST(b/2) + Θ(b³). Because 7 < 8, the level costs now decay geometrically — (7/8)^ℓ — and the top level dominates: ST(n) = Θ(n³), touch-optimal (any matmul must read its 2n² inputs: Ω(n³)). Two remarkable consequences. (i) In Model A, Strassen beats classical matmul by a genuine Θ(log n) factor of energy — not by its exponent. Its n^2.807 work advantage shows up in W, but the reads, not the arithmetic, are the currency. (ii) The ranking inverts between models. Spatial computer: Cannon is energy-optimal at Θ(n³) and the Strassen-based S3MM pays O(n³√log n) — recursion forces data off the home subgrid, and the paper buys depth (O(n^0.861) vs Θ(n)) with that energy. Model A: the recursion is free lunch — it matches the geometry of the memory hierarchy — and Strassen is the optimum. Same algorithm, same distance pricing, opposite verdicts, purely because of where the compute sits.

Dally E

Θ(n³) optimal

Dally W

Θ(n^2.807)

Dally D / D_w

Θ(log n) / Θ(n)

Spatial (S3MM)

O(n³√log n) / O(n^0.861) / O(n√log n)

A8FFT (bonus) touch-optimal via the four-step schedule

The four-step (Bailey) schedule — view n = m² points as an m×m matrix; column FFTs, twiddles, row FFTs — with each sub-FFT compacted into a near-core prefix gives F(n) = 2√n·F(√n) + Θ(n^3/2), whose recursive term is only Θ(n^5/4): the top level dominates and F(n) = Θ(n^3/2) ≈ 2n^3/2 including output reads — no log log, no log, unlike sorting's near-miss. A Hong–Kung cross-check is satisfying: the FFT I/O bound Q(S) = Ω(n log n / log S) summed over dyadic distances has its log exactly cancelled by log S at S ≈ n, confirming Ω(n^3/2) with no slack. The spatial paper doesn't treat FFT; its PRAM-simulation theorem gives O(n^3/2log n) generically, and a direct four-step schedule on the grid should give O(n^3/2) energy (transposes are permutations at Θ(n^3/2) each, O(1) of them at the top level) — we flag that as our sketch, not a published bound.

Dally E

≈2·n^3/2

Dally D / D_w

Θ(log n) / ≈3√n

Spatial

O(n^3/2) sketch

§5 · Synthesis

What the comparison actually says

One geometry, two tolls. Both models charge Manhattan distance; they differ in which movements are forced. Model A must haul every operand to one fixed point — its floor is the touch bound (2/3)n^3/2. Model B computes in place — its floor is the permutation bound, charged only when data must genuinely rearrange. Every row of the table is a corollary of that one sentence.
Aggregation is where parallel geometry pays: a √n energy separation. Reduce, scan, and selection cost Θ(n^3/2) on the single core but Θ(n) on the grid. Notably, selection — the spatial paper's most surprising linear-energy result — loses its entire advantage when compute is centralized: sampling still works, but seeing the data at all costs n^3/2.
Sorting is a tie at Θ(n^3/2): parallelism buys only time. When the problem inherently requires global data rearrangement, the grid's energy advantage vanishes — the spatial computer's own permutation lower bound meets Model A's touch bound at the same exponent. The grid still wins depth exponentially (log³n vs n log n serial steps).
Matmul inverts. Classical cubic matmul: the grid wins a Θ(log n) energy factor (Cannon's in-place shifts vs the unavoidable hierarchy traversal of a centralized memory). Allow Strassen and the single core catches up completely — Θ(n³), touch-optimal, log-free — while on the grid Strassen costs a √log n energy premium and is bought for depth. Whether "Strassen helps" is not a property of the algorithm; it is a property of where the compute sits relative to the data.
Wire-depth is architecture-invariant. Θ(√n) for reduce/scan/selection, Θ(n) for n×n matmul — in both models, up to the sorting schedule's polylog. It measures how far information must physically travel, and no arrangement of compute changes the diameter of the data. The models agree wherever geometry alone speaks; they disagree exactly where the single-core serialization (E) or the free-writes shortcut (broadcast) intervenes.
Free writes are the simplification to watch. They make broadcast Θ(n) with wire-depth 1 (physically absurd and pleasantly diagnostic), they let sorted runs / survivors / output blocks be "parked" anywhere at no cost, and they are why several constants above are as small as they are. Pricing writes like reads would roughly double the touch-tight constants and restore broadcast to Θ(n^3/2) — but changes no other Θ-bound in the table, since every algorithm above reads at least as much as it writes.

Worked instance, to make it concrete (n = 16). Summing 16 numbers: Model A pays exactly S(16)+16−2 = 64 reads of energy, +1 to read out the answer → 65; the spatial computer's quadrant-tree reduce on a 4×4 grid pays 24 — and the gap widens as √n. The repo's own worked example (a·b + c·d + e with inputs in cells 1..5) costs 15, of which 10 units are first reads of the five inputs and 5 are near-core bookkeeping (temporary re-reads and the exit read) — the same touch-vs-bookkeeping split that governs the asymptotics.

§6 · Scope & caveats

Epistemic status

These are our derivations. The Dally-model bounds in this report are not published results; they were derived here (four parallel analyses covering disjoint problem groups, then adversarially re-verified, with the derivation sketches above). The spatial-computer column follows Gianinazzi et al.'s Table 1 (with the paper's Z-order proviso for scan, and Lemma 4.2 behind Cannon's row). Confidence is high except where marked: selection is medium-confidence — its expected-energy analysis leans on the standard quickselect-fallback argument, its deterministic constant is unpinned, and its parallel depth is hedged; sorting's leading constant is layout-dependent and its D_w gap of log²n is likely closable with mesh-style networks; the cubic-matmul lower bound assumes no recomputation of product terms.
The model is (essentially) a known one. A single processor with access cost f(address) is the Hierarchical Memory Model of Aggarwal, Alpern, Chandra & Snir (STOC 1987); the simplified Dally model is HMM with f(x) = ⌈√x⌉, plus free writes. Our bounds are consistent with the flavor of that literature (polynomial access costs make "touch" the canonical floor); we did not locate exact published statements for f(x) = √x with free writes, so the report keeps its derivations self-contained.
Conventions that matter: the core holds no state across instructions (every operand is a priced re-read); inputs start in the compact prefix (any other placement only raises costs); D/D_w in the table use the dependency-DAG reading (Reading 2, §2) with write-after-read hazards removed by renaming; leading constants are placement-dependent where flagged (Strassen's and cubic matmul's upper constants are loose; the touch-side constants are exact).
What would change with S-word local memory or registers: a register file of size S turns the model into something closer to the paper's S-fat spatial processor / classic external-memory hybrids; the touch bound is unaffected but constants and the sorting/matmul log factors would shift. The spatial paper's own §6 shows its energy and wire-depth bounds scale by 1/√S (depth unchanged) — the comparison's structure survives.