Parallel prefix is about producing every partial result of a sequence in parallel instead of building those results one by one. The easiest way to see it is to replace processors with cooks, prefixes with pizzas, and communication steps with ingredient handoffs.
The Pizza Story
The Goal
Giovani is a rising Italian chef. As a marketing move, he decides to participate in a pizza competition. The competition is unusual: he has to make the final pizza, but he also has to make every intermediate version of it.
For a simple margarita made from dough, tomato, and mozzarella, that means producing:
- Pizza 1: Dough
- Pizza 2: Dough + tomato
- Margarita: Dough + tomato + mozzarella
And, of course, he wants to do it as quickly as possible. Thinking back on the rules, Giovani realizes nothing prevents him from asking other cooks to work in parallel.
The Constraint
There is one catch: each cook has room for only one ingredient or one partial pizza at a time, and each cook can perform only one combination per round.
That means:
- a cook holding dough can add tomato in one round,
- but cannot add tomato and mushrooms in the same round,
- and cannot keep the whole recipe on the table at once.
This restriction makes a normal sequential recipe impossible. The cook responsible for the full pizza cannot simply gather all the ingredients and assemble everything alone. The cooks have to communicate and cooperate.
How To Read The Plan
After thinking about the problem, Giovani comes up with a plan that makes all the required pizzas in roughly the time it would take to make one final pizza.
For the competition, Giovani is going to make his speciality, a pizza with 8 ingredients.
Before looking at the diagram, keep these rules in mind:
- each row is one cook,
- each column is one round of work,
- horizontal arrows carry a cook's current state forward,
- diagonal arrows show a partial pizza being handed to the next cook that needs it.
This is the key idea: no cook ever holds the entire recipe at once, yet the team still produces every prefix of the final pizza by exchanging partial results in a fixed pattern.
In each round, every cook combines whatever is on the table with the partial pizza that was handed over during the previous round. That pattern of local work plus structured handoff is parallel prefix.
The Computer Story
Mapping The Analogy
The pizza story maps directly to computing:
- each cook is a processing unit,
- the one-ingredient table limit is the memory limit on each processor,
- combining ingredients is an operation such as
+,*,min, or/, - and a partial pizza is a partial prefix result.
Parallel prefix is useful whenever you want every running result, not just the final one.
A Numeric Example
Let's take the * operation with a list of integers [1,2,3,4] as the data.
The final pizza in that setting is 1 * 2 * 3 * 4, but the full prefix set is:
11 * 21 * 2 * 31 * 2 * 3 * 4
Parallel prefix computes all of those values while each processor still starts with only one piece of input data. The win is that the system can expose every intermediate prefix in nearly the same time it would normally take to compute only the final result.
PS: Thanks to Bonnie Ding for helping me with the English on this.