On large chips, moving data — not computing with it — dominates the energy bill. Reaching an off-chip memory module costs orders of magnitude more energy than staying on-chip, and even on-chip, the farther the destination the more energy a message burns — which is why hardware has drifted toward spatial architectures: wafer-scale engines (Cerebras WSE), hierarchical many-cores (Mempool, Manticore), and coarse-grained reconfigurable arrays.
The paper’s model makes this explicit. Processors sit on an unbounded 2-D grid, each with constant-size local memory. In every synchronous time-step a processor may send one constant-size message to any other processor, dequeue one received message, and do O(1) arithmetic. There is no fixed topology — instead, sending a message from p(i,j) to p(x,y) costs |x−i| + |y−j| units of energy (its Manhattan distance). Three quantities describe a computation:
Try it. Click any two processors to send a message; the cost is the Manhattan distance between them. Messages are independent by default — but start a new message on a cell where an earlier one landed and it automatically chains onto that message (it can only depart after its input arrives). Build a few chains and watch depth and wire-depth separate from energy.
Processor p(0,0) knows a value; all n processors need it. Since each processor can send only one message per step, every efficient broadcast is a tree. The surprise is that where the processors sit changes the price of that tree.
On a 1-D line of n processors, a binary broadcast tree pays about n/2 energy at every level — halving the segments doubles their number, so each round of messages covers the same total distance: Θ(n log n) energy. On a √n × √n square, the paper’s recursive scheme sends the value to the top-left corners of the other three quadrants and recurses. Now each round’s messages shrink geometrically while their number quadruples — the series is dominated by the last, short-range level, giving Θ(n) energy (Lemma 2.2; in general O(hw + h·log h) on an h×w grid — linear unless the grid is exponentially taller than wide). Depth is O(log n) either way.
Step through both layouts of the same 64 processors — drawn as in the paper’s Fig. 1: filled dots hold the value, dotted boxes outline the subgrids being seeded, copper arrows are the current round, faded arrows are past rounds.
A scan (prefix sum) turns A₀, A₁, …, A₉₉₉ into A₀, A₀+A₁, A₀+A₁+A₂, … — a workhorse inside sorting, filtering, and load balancing. The classic up-sweep/down-sweep algorithm has O(log n) depth, but on a spatial computer the data layout decides its energy. Row-major order is a trap: logically adjacent elements at the end of one row and the start of the next are far apart on the chip.
The fix is to store the array along a Z-order (Morton) curve: visit the four quadrants recursively — top-left, top-right, bottom-left, bottom-right. Any aligned block of 4k consecutive indices then lives inside a small 2k×2k subgrid, and walking every edge of the curve costs only O(n) energy total (Observation 1).
The scan builds a 4-ary summation tree over quadrants. In the up-sweep, each subgrid’s total is collected at a designated cell — the root of a height-i subtree sits at Z-index i of its subgrid (paper Fig. 2a). In the down-sweep, each subgrid root receives the sum x of everything before its subgrid and forwards x + s₀ + … + si−1 to its i-th quadrant. At the leaves, each processor adds its own value: the inclusive prefix sum. Total: Θ(n) energy, O(log n) depth, O(√n) wire-depth. (The paper routes down-sweep values via each subgrid’s top-left processor; our simulator sends them along the up-sweep’s wires in reverse — the bounds are identical, and the symmetry is easier to see.)
To multiply two n×n matrices, the tempting approach — broadcast A and the columns of B across a bigger stretch of the chip so everything can happen at once — explodes the computation onto a much larger subgrid, and sending A alone already costs Ω(n9/2) energy (paper Fig. 5a). Distance punishes replication.
Cannon’s algorithm (1969) instead stays on the n×n subgrid where the matrices already live. First a one-time skew: row i of A shifts left by i; column j of B shifts up by j. After the skew, processor (i,j) holds a matching pair A[i,k], B[k,j] with k = i+j mod n. Then n rounds: multiply-accumulate locally, shift A one step left and B one step up (circularly). Every needed pair meets exactly once — all with distance-1 hops (plus wrap-around messages that travel back across the row).
This is Θ(n³) energy and Θ(n) depth, and the energy is optimal: multiplying by a row-reversal permutation matrix is a permutation of the rows, which already costs Ω(n³) on this layout (Lemma 4.1). Watch the teal A-values glide left along their row lanes and the violet B-values glide up their column lanes — wrap-around entries slide out one edge while re-entering from the opposite one (the physical message still pays the full return distance) — as every processor’s accumulator grows and the C matrix below fills in. Press ▶︎ play to watch it run.
Cannon is energy-optimal but its depth is linear. The paper’s S3MM schedule for Strassen’s algorithm trades a √log n factor of energy for polynomially smaller depth — O(n³√log n) energy with O(n0.861) depth — by unrolling Strassen’s recursion twice and running the resulting 343 block-multiplications in chunks of 64 on a slightly enlarged subgrid. A BFS/DFS hybrid turns this into a smooth energy–depth tradeoff. Whether sublinear depth is possible at exactly optimal energy is an open problem.
A recurring villain organizes the whole story: permutation is expensive. Reversing the order of n elements on a √n×√n grid forces a third of the elements to cross a third of the grid, so any permutation-heavy algorithm pays Ω(n3/2) energy (Lemma 3.1). This kills many classic designs that casually shuffle data — including direct PRAM ports — and it makes the following results sharp:
| Problem | Input shape | Energy | Depth | Wire-depth |
|---|---|---|---|---|
| Broadcast / Reduce | √n × √n | Θ(n) | O(log n) | O(√n) |
| Parallel scan (Z-order) | √n × √n | Θ(n) | O(log n) | O(√n) |
| Rank selection (randomized) | √n × √n | Θ(n) | O(log² n) | O(√n) |
| Sorting | √n × √n | Θ(n3/2) | O(log³ n) | O(√n) |
| Matmul — Strassen (S3MM) | n × n | O(n³ √log n) | O(n0.861) | O(n √log n) |
| Matmul — Cannon (cubic) | n × n | Θ(n³) | Θ(n) | O(n) |
Sorting in Θ(n3/2). Bitonic sort loses a log factor — not because it compares too much, but because its 1-D recursion eventually degenerates into a single row and pays line-layout prices (paper Fig. 3). The optimal algorithm is a 2-D Mergesort: sort the four quadrants recursively, then merge pairwise — the top pair, the bottom pair, then the two results. Each merge splits its two sorted arrays at their global ranks n/4, n/2, 3n/4, routes the four pieces into the four quadrants, and recurses — always on square, local subgrids (paper Fig. 4).
Selection beats sorting — by a polynomial factor. The highlighted row is the paper’s most striking result: finding the median (or any rank-k element) costs only Θ(n) energy, despite the Ω(n3/2) sorting floor. The trick is sampling: each round, elements survive independently with probability ~N−1/2, the ~√N-sized sample is cheap to gather and sort, and two pivots chosen from it discard all but ~N3/4 of the candidates with high probability — so a constant number of rounds suffices. Sampling sidesteps the permutation bottleneck because the whole input never has to move.
Bridging results. Any EREW PRAM algorithm (p processors, m memory cells, T steps) can be simulated in O(p(√p + √m)·T) energy by laying out the simulated shared memory as a square subgrid — with sorting-based routing handling concurrent reads/writes at a log³ depth premium. An S-fat variant (local memories of size S) scales all energy bounds down by √S, which transfers every result to hierarchical many-cores: at every level of the hierarchy, at most E/(k√Sᵢ) messages need to travel distance k or more — exactly the decreasing-bandwidth-with-distance profile that tree-like interconnects provide.
Open problems, in the authors’ order of difficulty: sorting at optimal energy with O(log² n) depth; energy-optimal rectangular matmul with depth O(n); energy-optimal square matmul with depth o(n); and energy-optimal rectangular matmul with depth o(n).