liveBook · Manning

Associativity

As explained in GPU Programming with Triton

Associativity is the algebraic property that regrouping operands does not change an operation's result.

An operation is associative when regrouping its operands leaves the result unchanged. For real numbers, addition satisfies (a + b) + c = a + (b + c), which makes associative operations straightforward to divide into partial reductions. section 4.1.1

Floating-point addition is not truly associative: finite precision can make a regrouping change the result. Parallel tree reductions necessarily regroup additions, so results may differ slightly with the reduction order, tile shape, or number of participating warps. section 4.1.1 section 4.3

Regrouping changes a floating-point sum

These expressions use the same values but produce different results: (0.1 + 1e20) - 1e20 gives 0.0, while 0.1 + (1e20 - 1e20) gives 0.1. The small value is rounded away when added to the large partial sum. section 4.1.1

Regrouping matters especially when:

  • Bitwise reproducibility is required across runs or configurations. section 4.1.1
  • Atomic updates combine partial sums in hardware-dependent order. section 4.1.1
  • A reduction feeds a numerically sensitive computation such as softmax. section 4.1.1

How GPU Programming with Triton covers it

How deep it goes
Defines associativity, works through a floating-point counterexample, and traces consequences for parallel reductions.
Examples
Compares two groupings of 0.1 and 1e20 that produce 0.0 and 0.1.
What you can do after
Evaluate why parallel reductions can yield numerically close but nonidentical results across configurations.
How it connects
Connects associativity to parallel reductions, floating-point arithmetic, atomic operations, and softmax.

Also explained in

Compare how 7 books explain associativity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of GPU Programming with Triton. The section links point to the parts of the book it draws on.