5.1 Motivation · Consistency & Coherence

Beyond the strong models

SC and TSO are sometimes called strong models because each one’s global memory order usually respects per-thread program order: SC preserves all four load/store combinations, TSO all but Store→Load. This chapter examines relaxed (weak) models that go much further, seeking to preserve only the orders programmers “require.”

The trade is explicit:

Benefit — mandating fewer orderings lets both hardware and software (compilers and runtime systems) apply more optimizations, for higher performance.
Drawbacks — a relaxed model must formalize when ordering is required and give programmers or low-level software a way to say so; and vendors never agreed on one relaxed model, compromising portability.

Mastering relaxed models is genuinely harder than SC or TSO, so this chapter is a primer: motivation (§5.1), an example relaxed model XC defined and formalized (§5.2) and implemented (§5.3), the crucial “SC for data-race-free” contract (§5.4), deeper concepts (§5.5), the RISC-V and IBM Power case studies (§5.6), further reading and commercial models (§5.7), model comparisons (§5.8), and high-level-language models (§5.9).

5.1.1 Opportunities to reorder memory operations

Take the flag idiom from §3.1, now with two data locations (Table 5.1):

Core C1	Core C2	Comments
`S1: data1 = NEW;`		/* Initially, data1 and data2 = 0 & flag ≠ SET */
`S2: data2 = NEW;`		/* Initially, data1 and data2 = 0 & flag ≠ SET */
`S3: flag = SET;`	`L1: r1 = flag;` `B1: if (r1 ≠ SET) goto L1;`	/* spin loop: L1 & B1 may repeat many times */
	`L2: r2 = data1;`
	`L3: r3 = data2;`

For r2 and r3 to always get NEW, the program needs exactly two order chains:

S1 → S3 → L1 loads SET → L2 (so r2 gets NEW), and
S2 → S3 → L1 loads SET → L3 (so r3 gets NEW).

SC and TSO additionally enforce S1 → S2 and L2 → L3 — orders the program never needed. Explore that gap: under the SC preset only (NEW, NEW) appears; toggle Store→Store or Load→Load reordering and the extra outcomes show which required chain broke:

Table 5.1: what order ensures r2 and r3 always get NEW?

Core C1	Core C2
S1: data1 = NEW;	L1: r1 = flag;
S2: data2 = NEW;	L2: r2 = data1;
S3: flag = SET;	L3: r3 = data2;

Initially data1 = 0, data2 = 0, flag = 0. Table 5.1: what order ensures r2 and r3 always get NEW?

Model:

Possible outcomes (r2, r3) under Custom reorderings:

(NEW, NEW)SC

1 execution — show one

S1 → S2 → S3 → L1 → L2 → L3

Only executions where C2's spin loop has exited (r1 = SET) are shown — the book's L1/B1 loop repeats until flag reads SET.

Table 5.2 generalizes the point to the handoff between two critical sections protected by the same lock — assume hardware lock acquire (e.g., a test-and-set RMW looping until it wins) and release (a store of 0):

Core C1	Core C2	Comments
`A1: acquire(lock)`
/* Begin Critical Section 1 / Some loads L1i interleaved with some stores S1j / End Critical Section 1 */		/* Arbitrary interleaving of L1i's & S1j's */
`R1: release(lock)`	`A2: acquire(lock)`	/* Handoff from critical section 1 to 2 */
	/* Begin Critical Section 2 / Some loads L2i interleaved with some stores S2j / End Critical Section 2 */	/* Arbitrary interleaving of L2i's & S2j's */
	`R2: release(lock)`

Correct handoff depends only on the bulk order (commas separate operations whose mutual order is unspecified):

All L1i, All S1j → R1 → A2 → All L2i, All S2j

Within each critical section, loads and stores may run in any order with respect to each other — unless they target the same address, where order is required to keep sequential core semantics. And here is the performance argument in one sentence: loads and stores are far more frequent than lock acquires and releases, so relaxing the order among the many to pay only at the few is exactly what relaxed models do.

5.1.2 Opportunities to exploit reordering

Assume, for now, a relaxed model that may reorder any two memory operations unless a FENCE separates them. The programmer must now reason about which operations need order — the drawback — but look at what the implementation gets to do:

Non-FIFO, coalescing write buffer

TSO’s buffer must stay FIFO to preserve Store→Store order. A coalescing write buffer merges two stores to the same entry even when they aren’t consecutive in program order — illegal under TSO, fine here so long as no FENCE separates them.

Speculation without the checking

The SC-preserving R10000 compares every evicted block’s address against its speculatively loaded addresses, squashing on a hit — hardware cost, power, and a finite resource that caps ILP. Under a relaxed model, out-of-order loads simply aren’t speculative with respect to consistency (they remain speculative w.r.t. branches and same-address earlier stores).

Opening the coherence box

Let a subset of cores load a new value while others still load the old one — temporarily breaking the SWMR invariant defined in Chapter 2 — open in glossary (e.g., two thread contexts sharing a write buffer, or two cores sharing an L1).

Check yourself

1.In Table 5.1's two-data flag idiom, which orders does the PROGRAM actually require for r2 and r3 to always get NEW?

2.For the critical-section handoff of Table 5.2, what ordering is required for correctness?

3.Why does a non-FIFO COALESCING write buffer violate TSO, and why is it fine under a relaxed model?

4.Relaxed models can simplify dynamically scheduled cores. What machinery can they drop, compared with the SC-preserving MIPS R10000?

5.What does "opening the coherence box" mean, and what does it cost?

5 questions