a parallel prefix sum

Suppose you have a row of numbers and you want every running total: the first number, the first two added, the first three, and so on, up to the grand total. Done by hand you sweep left to right, carrying the total — each step needs the one before it, so it looks hopelessly sequential. Yet this 'prefix sum' (or scan) is one of the most useful primitives in parallel computing, and the surprise is that it can in fact be done quickly in parallel, in only about log n rounds instead of n steps.

Formally, the prefix sum of an array a is the array p where p_k = a_0 + a_1 + ... + a_k. The naive method does n-1 dependent additions in sequence. The parallel trick works in two passes over a binary tree of the data. In the up-sweep, neighbouring elements are added in pairs, then those partial sums are added in pairs, and so on up the tree — each level halves the count, so the total runs to the top in log n parallel rounds, computing every subtree's sum along the way. A matching down-sweep then distributes those subtree sums back down to fill in every prefix. The whole thing does about 2n additions (twice the serial work) but finishes in O(log n) parallel depth instead of O(n). This pattern — trading a little extra total work for far shorter critical path — is the essence of turning a 'serial-looking' recurrence into a parallel one.

Scan matters because it is the hidden engine behind a startling range of parallel algorithms. It is exactly how you compact an array (keep only the elements passing a test) without knowing in advance where each survivor goes: a prefix sum over a 0/1 keep-flag array computes each survivor's destination index in parallel. It drives parallel sorting (counting sort, radix sort), stream compaction on GPUs, polynomial evaluation, and the resource allocation inside sparse matrix kernels. A parallel reduction (combining all elements into one value, like a sum or max) is the simpler cousin — just the up-sweep, no down-sweep — and is the workhorse collective behind every MPI allreduce and every well-written parallel summation. Recognising that a seemingly sequential dependency is really a scan or a reduction is a core skill in designing parallel numerical algorithms.