There is a small operation hiding inside a surprising amount of parallel software:

[3, 1, 7, 0, 4]  ->  [0, 3, 4, 11, 11]

At first it looks like a cumulative sum with an off-by-one convention. That is not wrong, but it is too small a story.

The operation is an exclusive scan, also called a prefix sum or prescan. For inputs \(x_0,\ldots,x_{n-1}\) and associative operator \(\oplus\) with identity \(I\), it returns

\[[I,\ x_0,\ x_0 \oplus x_1,\ \ldots,\ x_0 \oplus \cdots \oplus x_{n-2}].\]

Blelloch’s classic survey calls this the all-prefix-sums operation and shows why it is a primitive, not a trick.1 The operator can be addition, maximum, a matrix-like recurrence operator, or the carry operator in a binary adder. The requirement is associativity. The order of operands still matters, so commutativity is not required.

The version I keep reaching for is even plainer:

\[a_i = \sum_{j < i} f_j,\quad f_j \in \{0,1\}.\]

If \(f_i=1\), then \(a_i\) is the output address for item \(i\) in a stable compaction. Each row only knows whether it survives. Scan tells every survivor where to go.

That is the magic: scan converts local predicates into global coordinates.

The Address Factory

Imagine a GPU block, a vectorized database kernel, or a SIMD image pipeline. Every lane can decide locally whether its record should be kept. But “write the kept records contiguously” is not local. If I am a kept record at position 19, my destination depends on how many earlier records survived.

A serial loop solves this with a counter:

write = 0
for i in 0..n-1:
  if keep[i]:
    out[write] = x[i]
    write += 1

That counter is a dependency chain. Every iteration waits for the previous one.

Scan breaks the chain without changing the answer. Compute the keep flags, run an exclusive scan over those flags, then let each kept item write to its scanned address. The writes are independent because the addresses are unique.

This is the same move behind stream compaction, radix-sort split steps, histogram offsets, sparse frontier construction, parser bookkeeping, line-of- sight tests, and carry-lookahead addition.2

The loop was not “inherently serial.” It was hiding a prefix problem.

A Lab With Two Prefix Machines

The lab below builds a small flagged array, runs three scans, and uses the exclusive scan of the flags to compact the kept items.

It compares:

  • Serial scan: minimal arithmetic, but span grows linearly.
  • Hillis-Steele scan: logarithmic span and lots of parallelism, but \(O(n \log n)\) adds.3
  • Blelloch scan: an up-sweep and down-sweep over a conceptual tree, with \(O(n)\) adds and roughly twice the logarithmic span.1

Default audited facts for n = 32, density 47%, seed 29:

  • kept rows: 15 / 32;
  • serial span: 31;
  • Hillis-Steele adds: 129;
  • Blelloch adds: 62;
  • audit grid: 288 / 288 parameter cases passed.
kept item exclusive address Hillis-Steele schedule Blelloch schedule compacted output

Deterministic integer experiment. The audit checks serial, Hillis-Steele, and Blelloch scans against each other, verifies the work formulas, and confirms stable compaction across 288 parameter settings.

Move Items upward. Hillis-Steele keeps span low, but its add count grows faster. Blelloch spends two tree traversals and stays work-efficient.

Move Keep density. The compacted output changes, but the scan schedules do not. This is why scan is a primitive: the coordination cost mostly depends on the shape of the array, not on how many lanes happen to survive.

Work Is Not Span

The important distinction is not “parallel is faster.” The important distinction is that parallel algorithms have at least two budgets.

Work is the total amount of arithmetic. If you had to run the algorithm on one processor, work is the bill.

Span is the length of the dependency chain. With enough processors and cheap synchronization, span is the part you cannot parallelize away.

For power-of-two \(n\):

\[\begin{aligned} \text{serial work} &= n - 1, & \text{serial span} &= n - 1, \\ \text{Hillis-Steele work} &= n\log_2 n - (n - 1), & \text{span} &= \log_2 n, \\ \text{Blelloch work} &= 2(n - 1), & \text{span} &= 2\log_2 n. \end{aligned}\]

Hillis-Steele is impatient. At stride 1, every element looks one step left. At stride 2, it looks two steps left. Then four, eight, and so on. After \(\log_2 n\) rounds, every element has accumulated everything to its left.

That impatience costs arithmetic. Many partial sums are recomputed at different destinations.

Blelloch is more frugal. The up-sweep builds partial sums into a tree. The down-sweep pushes the sums of left siblings into the right places. It takes more rounds than Hillis-Steele, but it does only linear work. GPU Gems presents this as the step from a straightforward parallel scan to a work-efficient one, before the hardware-specific fight with shared-memory bank conflicts begins.2

Ladner and Fischer showed that this is a family of tradeoffs, not a single algorithmic personality.4 Prefix circuits can buy smaller depth with more nodes, or save nodes with more depth. The lab only shows two famous corners of that design space.

The Associativity Clause

Scan is not allowed to reorder arbitrarily. It is allowed to reparent.

That sounds pedantic until floating point shows up. Integer addition of small values is associative for this lab, so all three scans agree exactly. Floating point addition is not associative in real machines. A parallel scan over floats can be mathematically faithful to a parenthesized expression and still differ from a serial left fold.

This is not a bug in scan. It is the contract becoming visible.

If the operator is associative, scan exposes parallelism in a prefix computation. If the operator is only approximately associative, the algorithm is also choosing a numerical policy. Production libraries need to decide whether speed, reproducibility, error bounds, or compatibility with a serial reference is the governing promise.

The same issue appears in reductions, but scan makes it harder to hide because it returns every intermediate prefix, not just the final total.

The Shape to Notice

Once you see scan as an address machine, a lot of parallel code gets simpler.

Filtering is not “append from many lanes”; it is flags, scan, scatter.

Radix sort is not “sort the whole key”; it is repeated partitioning where each bit gets a destination range.

Graph traversal is not “many threads push into one queue”; it is each frontier edge deciding whether it emits work, then using a prefix count to reserve space.

Even a binary adder is not just rippling carries from right to left. It can be a prefix computation over generate/propagate pairs. The long dependency chain is real, but it is not inevitable.

The scan asks every element one question:

How much relevant history is before me?

The answer is a coordinate. Once every lane has a coordinate, the machine can stop arguing over a shared counter and start writing in parallel.

That is why a prefix sum is more than a cumulative sum.

It is a scheduler for ordered data.

  1. Guy E. Blelloch, “Prefix Sums and Their Applications”, CMU-CS-90-190, 1990. ↩ ↩2

  2. Mark Harris, Shubhabrata Sengupta, and John D. Owens, “Parallel Prefix Sum (Scan) with CUDA”, GPU Gems 3, 2007. ↩ ↩2

  3. W. Daniel Hillis and Guy L. Steele Jr., “Data Parallel Algorithms”, Communications of the ACM, 1986. ACM record. ↩

  4. Richard E. Ladner and Michael J. Fischer, “Parallel Prefix Computation”, Journal of the ACM, 1980. ↩