Parallel patterns: map, reduce, scan

Most parallel algorithms are built from a startlingly small vocabulary. You map a function over a collection, independently. You reduce a collection to one value by combining pairs. You scan a collection to produce all the running prefixes. Merge sort is divide-and-reduce; a histogram is map then reduce; a convolution is pattern-dependent map. Learn these three shapes and a surprising amount of parallel programming becomes "which combination is this?"

The vocabulary matters because these shapes have known costs. For each, you can compute two numbers — work (total operations, the cost on one processor) and span (the longest dependency chain, the cost on infinite processors) — and those two numbers bound the achievable speedup before you build anything. This is the discipline that separates parallel design from parallel fiddling.

Resize the array and switch between reduction and scan below.

Map #

Map applies a pure function to every element:

$$\text{out}[i] = f(\text{in}[i]) \quad\text{for all } i$$

Work is $W = n$ calls to $f$; span is $S = O(1)$ — every element is independent, so with enough processors the whole map takes one function's time. Map is embarrassingly parallel and the easiest pattern to get right, precisely because there are no dependencies and therefore no races. In practical libraries (OpenMP, std::for_each, CUDA) a map is where you start.

Reduce #

Reduce combines a collection to a single value with an associative operator $\oplus$:

$$\text{out} = a_1 \oplus a_2 \oplus \cdots \oplus a_n$$

Associativity is the licence to reorder. A sequential reduce does $W = n-1$ combines in a chain of span $n-1$ — no parallelism at all. A tree reduction pairs neighbours and collapses level by level:

$$\text{span} = \lceil \log_2 n \rceil \approx \log n, \qquad \text{work} = n-1$$

The work is the same but the span shrinks from $n$ to $\log n$, so the parallelism $W/S$ jumps from roughly 1 to $n/\log n$. That is the entire trick: reassociation turns a chain into a tree. It is why floating-point sum is not bit-identical to the sequential answer — changing the grouping changes the rounding — a genuine, accepted cost of parallel reduction.

Scan #

A prefix scan computes all prefixes of the operator:

$$y_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i$$

It is the sequence operation behind streams compaction, radix sort, run-length encoding and many graph algorithms. A sequential scan is again a chain of span $n$. The Hillis-Steele algorithm gets span $\log n$ by, at each step $d$, adding each element's value from $d$ positions back:

$$a^{(d)}_i = a^{(d/2)}_i \oplus a^{(d/2)}_{i-d}$$

The catch is work: every one of the $\log n$ steps touches all $n$ elements, so $W = n\log n$ — a $\log n$ factor of redundant work. Blelloch's scan does an up-sweep (a reduction tree) and a mirrored down-sweep, achieving optimal $W = n-1$ work at span $2\log n$, at the cost of two passes and more code. The choice is the classic work-versus-span trade: Hillis-Steele is simpler and fine when processors are plentiful, Blelloch when work matters.

Putting the numbers together #

Brent's theorem bounds the runtime on $P$ processors:

$$T_P \le \frac{W}{P} + S$$

The $W/P$ term is the work divided across processors; the $S$ term is the unavoidable serial tail. Speedup is then bounded by both the work term and the span:

$$T_P \ge \max\!\left(\frac{W}{P},\ S\right) \quad\Longrightarrow\quad \text{speedup} \le \min\!\left(P,\ \frac{W}{S}\right)$$

You cannot beat $P$ (there are only so many processors) and you cannot beat $W/S$ (there is only so much parallelism). A reduce with $n = 10^6$ has parallelism about $5 \times 10^4$, so a 64-core machine is nowhere near the span limit. A scan algorithm whose span is $2\log n = 40$ on the same data has parallelism $10^6/40$, still comfortable. But a naive program with a serial fraction of 5% has $W/S = 20$ no matter how large $n$ — the chain, not the work, is the wall.

Check yourself

Eduspheria wiki · Systems for AI, Concurrent programming

0 / 5 answered

1. 1A tree reduction of n = 1024 elements has what span (number of parallel steps)?

   steps

   Check Hint Show answerNumeric answer
2. 2Why is a tree reduction faster than a sequential reduction despite doing the same work?

   A.It avoids floating-point roundingB.It uses less memoryC.It shortens the dependency chain from n to log nD.It does fewer additions

   Check Hint Show answerMultiple choice
3. 3Hillis-Steele scan is work-optimal.

   TrueFalse

   Check Show answerTrue / false
4. 4A computation has work W = 800 and span S = 100. What is its maximum possible speedup on any number of processors?

   Check Hint Show answerNumeric answer
5. 5Which mathematical property of the combine operator permits the reordering a parallel reduce relies on?

   Check Show answerShort answer

From the exam paper

Modeled on NITJ AI-619, End-Sem June 2025

0 / 5 answered

1. 1A tree reduction of n = 2048 elements has what span, in parallel steps?

   steps

   Check Hint Show answerNumeric answer
2. 2A computation has work W = 640 and span S = 40. What is its maximum possible speedup on any number of processors?

   Check Hint Show answerNumeric answer
3. 3Building a histogram of an image — mapping each pixel to a bin and summing the bins — is which combination of patterns?

   A.Reduce then scanB.Scan then mapC.A single reduce with no mapD.Map then reduce

   Check Show answerMultiple choice
4. 4A map over n independent elements has constant span, which is why it is called embarrassingly parallel.

   TrueFalse

   Check Show answerTrue / false
5. 5Which scan algorithm touches all n elements at each of its log n steps, giving n log n work?

   Check Show answerShort answer

Where next: into the serving stack — containers, orchestration, and turning a model into a service.