Latticework — Master the skills engineers actually use

Explanation

Summing n numbers sequentially takes n - 1 additions, one after another — no way to speed that up with more processors, since each addition needs the previous one's result. Tree (pairwise) reduction restructures the same computation to expose parallelism: in each round, combine independent PAIRS of values simultaneously. Since every pair in a round is independent, they can all run on separate processors at once — and the number of values still roughly HALVES every round, so the whole reduction finishes in only O(log n) rounds instead of O(n) sequential steps.

def tree_sum(values):
    rounds = 0
    current = list(values)
    while len(current) > 1:
        next_round = []
        for i in range(0, len(current), 2):
            if i + 1 < len(current):
                next_round.append(current[i] + current[i + 1])
            else:
                next_round.append(current[i])
        current = next_round
        rounds += 1
    return (current[0], rounds)

Try it

This function itself still runs sequentially in Python -- it's SIMULATING what a parallel reduction would do round-by-round, counting rounds as the metric that matters (since on real parallel hardware, every pair within a round genuinely executes at the same time, making rounds -- not total additions -- the thing that determines wall-clock speed).

Loading editor…

Exercise

Write `tree_sum(values)`: sum a list of numbers using PAIRWISE reduction — each round, combine adjacent pairs (carrying over any unpaired final element unchanged) until only one value remains. Return `(total, rounds)`.

Quiz

Why does pairwise tree reduction only need O(log n) ROUNDS to sum n elements, versus O(n) sequential additions?

Checkpoint

You can simulate pairwise tree reduction and count its rounds, and understand why restructuring a sequential reduction this way exposes O(log n) parallelism.

Parallel Reduction