liveBook · Manning

Associative binary operation

As explained in Grokking GPU Programming

An associative operation is an operation whose result is unchanged when its operands are regrouped.

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

How Grokking GPU Programming covers it

How deep it goes
Defines grouping invariance, gives qualifying and failing operators, and notes floating-point rounding differences.
Examples
Compares addition, multiplication, maximum, and minimum with subtraction, and notes floating-point regrouping effects.
What you can do after
Evaluate whether an operator can support a parallel scan or reduction by checking whether regrouping preserves results.
How it connects
Connects associative operations to parallel scans, reductions, and identity elements.

Related concepts

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