An associative binary operation combines two values at a time, and regrouping the same values does not change the result: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c). This property lets parallel algorithms combine values in groups rather than only in sequence. section 6.1 section 5.8
Common examples and a useful contrast:
- Addition, multiplication, maximum, and minimum are associative; each can be used in a scan or reduction. section 6.1
- Subtraction is not associative: (5 − 3) − 1 differs from 5 − (3 − 1), so it cannot be used for a parallel subtraction-scan. section 6.1
- Floating-point addition can produce slightly different low-order bits when regrouped, because each step rounds. section 6.1
