📄 Prefix Sums and Their Applications

Summary

This chapter presents the all-prefix-sums operation (called a scan) as a basic building block for parallel algorithms. Given an associative operator and a sequence, a scan returns every running combination of the elements. A related prescan returns, at each position, the combination of all earlier elements only. Computing prefix sums looks inherently sequential, because each output depends on the previous one. Blelloch nevertheless gives a simple, work-efficient parallel algorithm for the vector version on an EREW PRAM. It uses two passes over a balanced binary tree: an up-sweep that computes partial sums (a reduce) and a down-sweep that spreads offsets back to the leaves. With p processors, each one first handles a block of n/p elements, which gives O(n/p + lg p) time. That is an optimal speedup whenever n/p ≥ lg p. The rest of the chapter shows how many problems reduce to scans, including line-of-sight, radix sort, quicksort, recurrence solving, processor allocation and line drawing. This makes the scan a reusable primitive that is also suitable for hardware.

Key points

• Requirements on the operator: it must be associative but need not be commutative, because the tree preserves operand order.
• Costs: the tree reduce takes ⌈lg n⌉ steps with n/2 processors. The prescan down-sweep adds another lg n steps, for about 2⌈lg n⌉ in total.
• Blocked version: each processor sums its block, the processor sums are prescanned, and the results are used as per-block offsets. Total time is 2(⌈n/p⌉ + ⌈lg p⌉).
• Correctness: the down-sweep is proved correct by induction. After it finishes, every tree vertex holds the sum of all leaves that precede it in preorder.
• Applications listed (13): string comparison, multi-precision addition, polynomial evaluation, recurrences, radix sort, quicksort, tridiagonal systems, deleting marked elements, processor allocation, lexical analysis, regex search (grep), tree depths and image component labeling.

Interesting ideas

• I1. Up-sweep/down-sweep pattern: first build partial aggregates bottom-up, then push "everything to my left" top-down. This turns any associative aggregation into a parallel prefix computation, which could serve tasks such as cumulative token counts or running offsets in large corpora.
• I2. Prescan as an allocator: an exclusive prefix sum over per-item sizes yields each item's start offset. This lets variable-length outputs be packed or allocated in parallel, as in the line-drawing example where each line gets a run of pixel slots.
• I3. In-place layout: storing partial sums at the right child positions means the down-sweep can reuse them without extra memory. This careful memory layout matters for GPU and SIMD implementations.
• I4. Two-level blocking: do sequential work locally, run the parallel tree only over the p block totals, then apply the offsets. This is a practical recipe for getting near-linear speedup on real machines with few cores.
• I5. Scans as a primitive: treating scans as a unit-cost primitive, as the paper proposes for the PRAM, simplifies both the design and the analysis of algorithms. Tasks like marking comment spans or tokenizing text become a few scans.