5.3 Implementing XC · Consistency & Coherence

The reorder unit

The implementation follows the same recipe as SC and TSO: separate the core’s (re)ordering rules from cache coherence. Where a TSO core was separated from shared memory by a FIFO write buffer, an XC core sits behind a more general reorder unit that can reorder both loads and stores:

Loads, stores, and FENCEs leave core Ci in program order <p and enter the tail of Ci’s reorder unit.
The unit queues operations and passes them from tail to head, either in program order or reordered within the rules below. A FENCE is discarded when it reaches the head — its work is done inside the unit.
When the switch selects core Ci, it performs the load or store at the head of Ci’s reorder unit.

Figure 5.3 (recreated): two XC implementations. The blue reorder units generalize chapter 4’s FIFO write buffers — they hold and reorder loads and stores. Everything else is the familiar switch (a) or coherence black box (b).

The reorder unit obeys three rule groups — unsurprisingly mirroring §5.2.3’s formalism:

As in the previous two chapters, the switch and memory can be replaced by a cache-coherent memory system (Figure 5.3b). Coherence still implements the global memory order as a black box; what’s new is only that memory order may disrespect program order far more often, thanks to the reorder unit.

5.3.1 Atomic instructions with XC

Assume dynamically scheduled cores, each connected to memory through a non-FIFO coalescing write buffer . The simple solution borrows TSO’s RMW implementation: drain the write buffer, obtain the block with read-write permission, perform the load and store parts (the store goes straight to cache — the block is already writable), never relinquishing the block in between and deferring incoming coherence requests until the store part performs.

Simple, but overly conservative: the drain is unnecessary. XC lets both the load part and the store part of the RMW pass earlier stores. It suffices to obtain read-write permission and perform the pair while holding the block.

The bigger difference is in usage. Under TSO, a lock acquire is just the RMW loop and a release is just a store. Under XC, neither is enough by itself (Table 5.6):

Code	TSO	XC
Acquire lock	`RMW: test-and-set L` /* read L, write L=1 / `if L==1, goto RMW` / if lock held, try again */	`RMW: test-and-set L` `if L==1, goto RMW` `FENCE`
Critical section	Loads and stores	Loads and stores
Release lock	`Store L=0`	`FENCE` `Store L=0`

By default XC would let critical-section operations reorder above the acquire or below the release — so the acquire must be followed by a FENCE, and the release preceded by one.

5.3.2 FENCEs with XC

If core C1 executes Xi, then a FENCE, then Yi, the implementation must enforce Xi <m FENCE <m Yi. Three basic approaches:

SC + no-op FENCEs

Implement SC and treat every FENCE as a no-op. No commercial product does this (yet); academic proposals exist, e.g., via implicit transactional memory.

FENCE as drain

Wait for all Xi to perform, declare the FENCE done, then start the Yi. Common — and costly, since every FENCE stalls.

Aggressive enforcement

Enforce Xi <m FENCE <m Yi without draining. Harder to design and verify, better performance.

Whatever the approach, the implementation must know when each Xi is done (or at least ordered) — surprisingly tricky for a store that bypasses normal cache coherence, such as a store to an I/O device or one using a fancy write-update optimization.

5.3.3 A caveat

Check yourself

1.In the XC implementation of Figure 5.3, what separates each core from the memory system, and what does it do?

2.TSO's RMW implementation drains the write buffer before the load part. Why can an XC implementation skip the drain?

3.Per Table 5.6, how does locking differ between TSO and XC?

4.The book sees three basic ways to implement FENCEs. Which list is right?

5."I'm implementing a relaxed model, so anything goes." What's wrong with this claim?

5 questions