Lesson 24: Parallel Scan (Prefix Sum) — the Idea
A scan, or prefix sum, turns an array into the sequence of its running totals. In an inclusive scan the output at position i is the sum of all elements from 0 to i inclusive: output[i] = in[0] + in[1] + ... + in[i]. For example [3,1,2,4] becomes [3,4,6,10]. There is also an exclusive variant that st
Imagine a row of people, each holding a number, and each must end up holding the sum of everyone before them, themselves included. Instead of whispering neighbor to neighbor slowly, in each round everyone adds the number of the person one step to their left, then two steps, then four. The jumps double — and the whole row finishes in just a few rounds.
- prefix sum / scan
- Turning an array into its running totals. In an inclusive scan, output[i] is the sum of in[0..i] inclusive.
- inclusive vs exclusive
- Inclusive: each output includes the element at its position ([3,1,2,4]->[3,4,6,10]). Exclusive: starts at zero and shifts right ([0,3,4,6]).
- the doubling idea
- Each round every element adds the neighbor d away, and d doubles (1,2,4,...). After log2(n) rounds each position has accumulated all predecessors.
- running total
- The sum accumulated up to a given point. The sequential version computes it in one loop in O(n) steps.