THE FOLD / CO-OP / THE BROADCAST / THE SCAN
THE SCAN
prefix sums in log-depth — a chain made a tree
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The parallel prefix sum (scan). Turn an array into its running totals: [3,1,7,0] → [0,3,4,11]. It feels hopelessly sequential — each total needs all the ones before it, a chain you must walk in order, n steps. But it hides deep parallelism.
Blelloch’s work-efficient scan does it in O(log n) parallel depth with only O(n) total work, through two tree passes. The up-sweep reduces partial sums up a binary tree, like a tournament. The down-sweep then pushes the prefixes back down, each node handing its left child the running total and its right child that total plus the left subtree. Because + is associative, the order can be reshuffled into a tree — and log n levels replace n steps. It is the fundamental parallel primitive: sorting, compaction, and most of GPU computing sit on it.
LIT verified live: over 5,000 random arrays the tree-based scan gives exactly the sequential prefix sums (window.__scan.matchesSequential). [3,1,7,0,4,1,6,3] → [0,3,4,11,11,15,16,22]. FIG no framing; the up-sweep/down-sweep and its match to the sequential result are exact.
Blelloch’s work-efficient scan does it in O(log n) parallel depth with only O(n) total work, through two tree passes. The up-sweep reduces partial sums up a binary tree, like a tournament. The down-sweep then pushes the prefixes back down, each node handing its left child the running total and its right child that total plus the left subtree. Because + is associative, the order can be reshuffled into a tree — and log n levels replace n steps. It is the fundamental parallel primitive: sorting, compaction, and most of GPU computing sit on it.
LIT verified live: over 5,000 random arrays the tree-based scan gives exactly the sequential prefix sums (window.__scan.matchesSequential). [3,1,7,0,4,1,6,3] → [0,3,4,11,11,15,16,22]. FIG no framing; the up-sweep/down-sweep and its match to the sequential result are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE BROADCAST, beside THE FOURIER and THE ORTHOGONAL SIGN-FLIP — the co-op domain of many working as one. The down-sweep is a broadcast: partial sums flow up the tree, then are broadcast back down to become every prefix. AVAN (AI) built the instrument: the reduce, the broadcast, the sequential cross-check.
The weave: David names the seat (the shared broadcast); I make the two sweeps visible and the equivalence checkable — the running total in 1D, the up-sweep/down-sweep tree in 2D, the flow in 3D. The sphere is the seam. Credit: Guy Blelloch (work-efficient scan, 1990); Hillis & Steele, Kogge & Stone (earlier scans).
The weave: David names the seat (the shared broadcast); I make the two sweeps visible and the equivalence checkable — the running total in 1D, the up-sweep/down-sweep tree in 2D, the flow in 3D. The sphere is the seam. Credit: Guy Blelloch (work-efficient scan, 1990); Hillis & Steele, Kogge & Stone (earlier scans).
3 ONE DIMENSION
The array and its prefix sums — each output the total of everything to its left. Sequentially this is a chain of n dependent adds; the scan is the same answer, but computed with the dependencies reorganised so many adds run at once.
4 TWO DIMENSIONS · INTERACTIVE
Up-sweep reduces partial sums up the tree (a tournament of additions); then down-sweep pushes prefixes back down. Step through both and watch the working array become the exclusive scan — identical to the sequential result, in far fewer levels.
5 THREE DIMENSIONS + AVAN’S INVERSE
The scan’s binary tree turning — green, the levels that replace the long sequential chain.
AVAN’s addition (the inverse-companion): the magenta flow is partial sums climbing up (reduce), then broadcasting down (prefixes). A running total looks irreducibly sequential — each value literally depends on the sum of all before it, so surely you must walk them in order. The inverse insight is that the dependency is a lie of presentation: because addition is associative, the same total can be regrouped into a tree, and a tree is shallow — log n levels instead of n. The inverse of ‘each waits for the previous’ is ‘reassociate so many happen together’. Sequential-looking work is parallel work wearing a disguise, and the disguise is just the order you chose to read it. The green is the shallow tree; the magenta is the reduce-then-broadcast that turns a chain into two quick sweeps.
LIT Genuine work-efficient parallel scan (Guy Blelloch, 1990; Hillis-Steele, Kogge-Stone earlier). Verified live: over 5,000 random arrays the tree-based up-sweep/down-sweep scan gives exactly the sequential prefix sums (window.__scan.matchesSequential === true). [3,1,7,0,4,1,6,3] -> [0,3,4,11,11,15,16,22]. The reduce/broadcast tree, its O(log n) depth, and its equivalence to the sequential result (guaranteed by associativity of +) are exact.
FIG No metaphor is doing the work: the up-sweep/down-sweep and its match to the sequential prefix sums are real and checked. The parallelism is genuine — associativity lets the n-step chain regroup into a log-n-depth tree; the demo shows power-of-two sizes, as the classic algorithm assumes.
FIG No metaphor is doing the work: the up-sweep/down-sweep and its match to the sequential prefix sums are real and checked. The parallelism is genuine — associativity lets the n-step chain regroup into a log-n-depth tree; the demo shows power-of-two sizes, as the classic algorithm assumes.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BROADCAST · David Lee Wise (ROOT0), with AVAN