The idea: running totals without waiting for the one before

A prefix sum, also called a scan, turns a list into its running totals. For x = 3 1 7 0 4 1 6 3 the inclusive scan is 3 4 11 11 15 16 22 25: cell i holds x[0] + … + x[i]. The exclusive scan is 0 3 4 11 11 15 16 22: cell i holds the sum of everything before i. The loop x[i] = x[i − 1] + x[i] does only 7 additions, but each one needs the result of the one before it. That chain is 7 steps long, and no number of processors can shorten it (Demo 1). The parallel algorithms on this page add the numbers in a different order, so that many additions can run at the same time.

Left: the sequential loop as a chain of 7 additions, 4, 11, 11, 15, 16, 22, 25, each one below the last. Right: Blelloch on the same 8 values as a tree drawn twice. The up-sweep sums pairs to 4 7 5 9, then 11 14, then 25 at the root; the root is cleared to 0; the down-sweep hands values back down to 0 11, then 0 4 11 16, then 0 3 4 11 11 15 16 22.
The loop is a chain of 7 additions; Blelloch uses 14 additions but they form trees only 6 rounds deep.

On the canvas each row is the shared array after one round, with time going down. A blue line goes from a value that is added, an orange line from a value that is moved, and a grey line from a cell to itself. Grey numbers were only copied in that round. The results table on the right keeps one row per algorithm, so you can compare them.

The PRAM, work and span

A PRAM (parallel random-access machine) is the textbook model: p processors share one memory and run in lock-step rounds. In a round every processor reads, computes and writes once. Two numbers describe an algorithm on it:

  • Work W: the operations in total. It is the time on one processor.
  • Span S (or depth): the number of rounds when processors are unlimited. It is the longest chain of operations that depend on each other.

An algorithm is work-efficient if its work is of the same order as the best sequential algorithm, here O(n). With p processors, a round of k operations takes ⌈k / p⌉ time steps. Adding that up gives Brent's bound: Tp ≤ W / p + S. The page uses the processor counts p = 8 (one per element) and p = 2.

Hillis–Steele: few rounds, more work

In round d = 1, 2, 4, every i ≥ d adds x[i − d]. After round d each cell holds the sum of the last 2d values, so after log₂ 8 = 3 rounds it holds everything (Demo 2). The rows are 3 4 8 7 4 5 7 9, then 3 4 11 11 12 12 11 14, then 3 4 11 11 15 16 22 25. Every processor reads its cell and a cell to its left, which another processor is writing, so a real machine needs a second buffer: the new row. The price is work. Round d does n − d additions: 7 + 6 + 4 = 17, against 7 for the loop.

nsequential work = spanHillis–Steele workspanBlelloch workspan
87173146
10241023921710204620
220 ≈ 10610485751992294520209715040

Hillis–Steele's work is n log₂ n − (n − 1). At a million values that is 19 times the loop's work, so it pays only when there are about as many processors as values, as inside one GPU warp.

Blelloch: up-sweep and down-sweep

Blelloch's scan works on a balanced binary tree laid over the array, without building the tree: the tree nodes are array cells.

  • Up-sweep (a reduction): at distance d = 1, 2, 4, the right cell of each block of 2d adds the left half's total. 4 + 2 + 1 = 7 additions. The rows are 3 4 7 7 4 5 6 9, then 3 4 7 11 4 5 6 14, then x[7] = 25, the total.
  • Clear: x[7] = 0, one write.
  • Down-sweep: at d = 4, 2, 1, each pair (i − d, i) does t = x[i − d]; x[i − d] = x[i]; x[i] += t. The left child gets the parent's value, which is the sum of everything to its left. The right child gets that plus the left subtree's total. 1 + 2 + 4 = 7 additions.

The result is the exclusive scan 0 3 4 11 11 15 16 22 after 14 = 2(n − 1) additions in 2 log₂ n = 6 rounds (Demo 3). It does twice the loop's work, which is still O(n), so it is work-efficient. If you need the inclusive scan, add x[i] to each cell: one more round.

Eight rows of 8 cells: the input 3 1 7 0 4 1 6 3, then the up-sweep rows: 3 4 7 7 4 5 6 9, then 3 4 7 11 4 5 6 14, then 3 4 7 11 4 5 6 25. Clear row: last cell set to 0. Down-sweep rows: 3 4 7 0 4 5 6 11, then 3 0 7 4 4 11 6 16, then 0 3 4 11 11 15 16 22. Cells written in each row are shaded.
Up-sweep sums blocks of 2, 4 and 8; down-sweep hands each cell the sum of everything to its left.

With only two processors

Span counts rounds as if processors were free. With p = 2 every round of k additions takes ⌈k / 2⌉ time steps (Demo 5):

algorithmworkroundssteps, p = 8steps, p = 2
sequential7777
Hillis–Steele17334 + 3 + 2 = 9
Blelloch14662 + 1 + 1 + 1 + 1 + 2 = 8

With 8 processors Hillis–Steele is fastest (Demo 4). With 2, the extra work shows: Blelloch beats it, and on only 8 values both lose to the plain loop. Real libraries therefore use a blocked scan: each of p processors scans its own block of n / p values with the loop, the p block totals are scanned (with Blelloch when p is large), and each block adds its offset. That does about 2n work in about 2n / p + log p time.

A use: stream compaction

Scan answers the question "where does my value go?" in parallel. To keep only the odd values of 3 1 7 0 4 1 6 3 (Demo 6):

  1. Each processor sets a flag: f = 1 1 1 0 0 1 0 1. One round, 8 tests.
  2. An exclusive scan of the flags gives pos = 0 1 2 3 3 3 4 4: each kept value's slot is the number of kept values before it. 14 additions in 6 rounds.
  3. Each kept value writes itself to out[pos[i]]: out = 3 1 7 1 3. No two values share a slot, so no locks are needed. One round, 5 writes.

That is 27 operations in 8 rounds. The count is pos[7] + f[7] = 5. The same pattern splits values in radix sort on GPUs, where counting sort's running totals of the counts are a scan too.

Four rows: x = 3 1 7 0 4 1 6 3; flags 1 1 1 0 0 1 0 1; pos = exclusive scan 0 1 2 3 3 3 4 4; out = 3 1 7 1 3 with arrows from each kept value to its slot.
Flags, an exclusive scan, and one write per kept value pack 3 1 7 1 3 to the front in order.

A tree reduction is the up-sweep alone; on distributed memory it is MPI_Reduce on a binomial tree, and MPI also has MPI_Scan. How much speedup the parallel rounds buy for a whole program is the subject of Amdahl's and Gustafson's laws. On a GPU, 32 threads of a warp run in lock-step much like a PRAM. When the array changes and prefix sums are asked again and again on one processor, a Fenwick tree or a segment tree answers each in O(log n).

See also OpenMP loop scheduling for how a parallel for splits a loop over threads with static, dynamic and guided schedules.

What the page leaves out

The page uses n = 8, a power of two; other sizes pad the array or stop the tree early. Real GPU scans (CUB, Thrust) run a blocked scan per thread block and pass block totals with "decoupled look-back" in a single pass over memory, and they avoid shared-memory bank conflicts by padding. Left out: other associative operators (max, logical or, matrix product) that scan works for; segmented scan; carry-lookahead adders, which are a scan in hardware; Kogge–Stone, Brent–Kung and Ladner–Fischer networks; the CREW vs EREW details; and memory traffic, which matters more than additions on real machines. Floating-point sums can differ slightly between the algorithms because they add in a different order.

On the mind map

Open the Computer Architecture mind mapComputerArchitectureAbstraction and numbers: layers and bit patternsAbstraction and numbersCombinational logic: output depends only on inputsCombinational logicSequential logic: state held by a clockSequential logicMIPS software: how C becomes machine wordsMIPS softwareThe processor: datapath plus controlThe processorPipelines and parallelism: more instructions at oncePipelines and parallelismMemory and I/O: small fast near, big slow farMemory and I/OMIPS pipelineMIPS pipelineforward data, stall on load-useBranch predictionBranch prediction2-bit counters guess, flush if wrongOut-of-order executionOut-of-order executionrenaming removes WAR and WAW hazardsSIMD, threads, multicoreSIMD, threads, multicoreAmdahl's law caps the speedupAmdahl vs GustafsonAmdahl vs Gustafsonfixed job caps at 1/s; scaled growsMPI Send/Recv & CollectivesMPI Send/Recv & CollectivesTrees: log₂ p rounds; Send may blockParallel Prefix SumBlelloch: 2(n−1) work, 2 log n spanOpenMP loop schedulesOpenMP loop schedulesUneven costs: dynamic beats static blocksGPU and SIMT warpsGPU and SIMT warps32 lanes, one instruction; branches splitOpen the Computer Architecture mind mapComputer Architecturemore instructions at oncePipelines and parallelismMIPS pipelineMIPS pipelineforward data, stall on load-useBranch predictionBranch prediction2-bit counters guess, flush if wrongOut-of-order executionOut-of-order executionrenaming removes WAR and WAW hazardsSIMD, threads, multicoreSIMD, threads, multicoreAmdahl's law caps the speedupAmdahl vs GustafsonAmdahl vs Gustafsonfixed job caps at 1/s; scaled growsMPI Send/Recv & CollectivesMPI Send/Recv & CollectivesTrees: log₂ p rounds; Send may blockParallel Prefix SumBlelloch: 2(n−1) work, 2 log n spanOpenMP loop schedulesOpenMP loop schedulesUneven costs: dynamic beats static blocksGPU and SIMT warpsGPU and SIMT warps32 lanes, one instruction; branches split
This page on the Computer Architecture mind map · 42 pages in 7 branches · open it to see the whole map and test yourself in recall mode.