Reduction Trees and What Associativity Buys

Folding a collection into one value is the most common parallel pattern after the map, and it is the one where the parallel version can quietly disagree with the sequential one. The disagreement is not a bug in the scheduler. It follows from what the operator is, and knowing the difference between the cases decides whether a parallel reduction is a pure speedup or a change in semantics.

What a fold actually requires

A left fold of an operator ⊕ over x₀…xₙ₋₁ computes ((x₀ ⊕ x₁) ⊕ x₂) ⊕ … . To compute it as a tree, regrouping must preserve the answer. That is exactly the statement of associativity: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c). Commutativity, a ⊕ b = b ⊕ a, is a separate and weaker convenience — it lets a tree visit its children in either order, but associativity is what licenses the tree at all.

Integer addition and multiplication, bitwise and/or/xor, minimum and maximum, set union, string concatenation, and matrix multiplication over a fixed field are associative. Subtraction, division, exponentiation, and averaging are not: 1 − (2 − 3) = 2 but (1 − 2) − 3 = −4, and the average of averages weights groups by size rather than by element. When a non-associative operator appears, the usual repair is to carry the extra state that makes it associative: subtraction becomes addition of signed values, averaging becomes a (sum, count) pair whose combination is (s₁+s₂, c₁+c₂).

Identity matters for the same reason. A tree over a non-power-of-two length must either pad with the identity element or build an unbalanced tree. Padding with 0 is harmless for sum, but padding with 1 for a product is only harmless if the extra factors are exactly 1.0 and not, say, a sentinel like −1, and a minimum over padded slots is wrong unless the pad is larger than every real element. Zero, one, +∞, and the empty set are the identities that make the padding legal; anything else silently corrupts the result.

Where floating-point addition breaks the licence

IEEE 754 binary64 addition is not associative. Each addition rounds its exact result to 53 significant bits, and the rounding error depends on the magnitudes involved, so the same set of numbers summed in two orders gives two answers that differ in the last bits — and occasionally by more.

The classic demonstration is absorption: adding 10⁻¹⁶ to an accumulator holding 1.0 returns exactly 1.0, because the small term falls below half an ulp of the result and the addition rounds it away. In binary64 the significand is 53 bits, so a term smaller than roughly 2⁻⁵³ times the accumulator is lost this way; in binary32 the threshold is 2⁻²⁴. A sequential loop over a million such terms can lose all of them, while a tree loses only those whose immediate parent is already far larger than they are. Reordering cannot recover information a particular addition already discarded, but it changes how often that happens: a balanced tree keeps partial sums small and of comparable magnitude, so far fewer terms fall below the rounding threshold of their parent.

The error analysis makes the difference quantitative. For naive left-to-right summation of n terms, the standard bound is

$$|\hat{S} - S| ;\le; (n-1),u \sum_i |x_i| + O(u^2)$$

where u is the unit roundoff, 2⁻⁵³ for binary64. Error grows linearly in n. For pairwise summation, which is the balanced tree, the bound becomes

$$|\hat{S} - S| ;\le; \lceil \log_2 n \rceil, u \sum_i |x_i| + O(u^2)$$

Error grows with the depth of the tree, not its width. Summing 2²⁰ terms, the worst-case bound shrinks from a factor near 10⁶ to a factor of 20 in front of the same u·Σ|xᵢ| term. This is why the parallel reduction is often more accurate than the loop it replaces: the tree depth is smaller than the loop length by orders of magnitude.

The same reasoning explains why blocked summation in a sequential library is arranged as several accumulators combined at the end. The parallel tree is that idea taken to its limit, and a sequential cut-off is the practical compromise between tree depth and per-node overhead.

Tree shape as a semantic choice

Once reordering is permitted, the shape is a design variable with visible consequences. Three shapes cover most implementations:

• Left-deep (sequential): depth n−1, error linear in n, bit-identical to the naive loop. Correct when reproducing a specified result matters more than accuracy.
• Balanced binary tree: depth ⌈log₂ n⌉, error logarithmic in n, requires the length to be known and pads the tail. The natural shape for a divide-and-conquer reduction.
• Fixed fan-in (say 8 or 16 children per node): depth ⌈log_k n⌉, error bounded by (k−1)⌈log_k n⌉uΣ|xᵢ|. Slightly worse in the bound than binary but cheaper per level on wide machines, because a node’s children can be accumulated in one register-resident loop before the parent sees a value.

The fan-in choice also interacts with how the reduction is scheduled. A binary tree exposes only two tasks per level near the root, so the tail of the computation has little parallelism; a wide tree exposes more tasks but each is shorter. That is the same work-span tension described in the DAG model, restated in terms of a fan-in parameter.

#include <stddef.h>

/* Pairwise (balanced-tree) sum: depth ceil(log2 n), error O(log n). */
double pairwise_sum(const double *a, size_t n)
{
    if (n == 0) return 0.0;
    if (n == 1) return a[0];
    size_t h = n / 2;                 /* split, do not round down to power of two */
    return pairwise_sum(a, h) + pairwise_sum(a + h, n - h);
}

Splitting at n/2 rather than at the largest power of two below n keeps the depth minimal for every length; rounding to powers of two can nearly double the depth for lengths just above one.

Getting the same answer twice

Reproducibility is a separate requirement from accuracy, and parallel reductions violate it by default: the tree shape may depend on how many tasks the scheduler happened to create, so two runs of the same binary on the same input can differ in the last bits. Three approaches exist.

Fix the order by construction. Give every element a fixed position in an explicit tree whose shape depends only on n, and compute the tree regardless of the machine width. The result is deterministic across processor counts; the cost is that the schedule must respect the fixed shape, which limits load balancing.

Use an exactly-rounded accumulation. Sums computed with a compensated or expansion-based accumulator, or with a fixed-point representation, produce a result independent of order to within a stated guarantee. The cost is typically several extra floating-point operations per element and more registers, so the arithmetic throughput drops by a constant factor.

Accept the variance and specify a tolerance. Many numerical codes do, but the tolerance has to be derived from the error bound rather than observed, or a rare large deviation will be mistaken for a bug in unrelated code.

Reductions over integers, and over floating point under a fixed schedule, are free of this problem, which is why reductions of counts and indices are the ones that can be reordered without a second thought. The general rule: associativity permits the tree, but only a fixed shape or an order-independent accumulator permits a reproducible answer. Floating point supplies neither for free.

Reductions that are not folds

Two nearby patterns look like reductions but are not, and misclassifying them produces wrong code. A prefix sum is a fold whose intermediate values are all outputs, so it cannot be a plain tree — it needs the upward-then-downward structure of a scan. A selection such as “the k-th smallest” combines by discarding rather than by an associative binary operator, so it parallelises through partitioning instead. And a reduction whose operator is associative but not commutative, such as list concatenation, requires the tree to preserve child order; a scheduler that reorders tasks will reverse segments of the result. Most runtime reduction primitives state whether order is preserved, and the answer is worth checking before relying on it.