liveBook · Manning

Invariant

As explained in Grokking GPU Programming

An invariant is a property that remains true at each stage of an algorithm.

An invariant is a property that remains true as an algorithm progresses. In a parallel scan, it lets you check what each position represents after every round—and why the final values are correct. section 6.7 section 7.4

In scan algorithms, the invariant tracks how partial sums grow:

  • Hillis-Steele: after round r, position i holds the sum of up to 2ʳ input values ending at i. Near the start of the array, the window is clipped at position 0 or the value is copied through. section 6.7
  • Blelloch: during the up-sweep, each active position holds a sum over a growing range. During the down-sweep, each visited node holds the sum of original elements before its subtree. section 7.4

Following a scan

For [3, 1, 7, 0, 4, 1, 6, 3], Hillis-Steele grows each position’s window over three rounds. Once a window covers the whole array, each position holds its inclusive prefix sum: [3, 4, 11, 11, 15, 16, 22, 25]. section 6.7

Table 6.1 The three cases that arise when extending the Hillis-Steele invariant from round r−1 to round r. Each row gives the condition on position i, what happens at position i, and the figure that illustrates the case.
Case
Condition on i
What happens at position i
1
i ≥ 2ʳ − 1
Full window. Both position i and position i − 2ʳ⁻¹ hold sums of 2ʳ⁻¹ elements; adding them produces a sum of 2ʳ elements ending at i (figure 6.6).
2
2ʳ⁻¹ ≤ i < 2ʳ − 1
Partial left window. The left neighbor’s window is clipped at position 0, so it holds fewer than 2ʳ⁻¹ elements; the sum at i still reaches all the way back to position 0 (figure 6.7).
3
i < 2ʳ⁻¹
No left neighbor at stride 2ʳ⁻¹. Position i copies its value through; it already holds the sum of all input elements [0..i] from earlier rounds (figure 6.8).

Use the cases to see how a Hillis-Steele round preserves the invariant at full windows, partial windows, and positions with no left neighbor. section 6.7

How Grokking GPU Programming covers it

How deep it goes
Derives scan invariants across Hillis-Steele rounds and Blelloch phases, including boundary cases and how the final prefixes follow.
Examples
Traces an eight-element array through Hillis-Steele rounds and describes growing ranges in Blelloch’s up-sweep.
What it assumes
Starts from each array position holding its own input value, then builds the reasoning round by round.
What you can do after
Understand scan correctness by checking what each position represents after every round or phase.
How it connects
Connects invariants to parallel scan, prefix sums, Hillis-Steele, and Blelloch algorithms.

Also explained in

Compare how 18 books explain invariant →

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.