4.4Implementing TSO/x86

SC’s implementations, plus buffers

The implementation story for TSO is chapter 3’s story plus per-core FIFO write buffers. Update the switch of §3.6 (the book’s Figure 4.4a):

• Loads and stores leave each core in its program order <p.
• A load either bypasses a value from the write buffer or awaits the switch as before.
• A store enters the tail of the FIFO write buffer — or stalls the core if the buffer is full.
• When the switch selects core Ci, it performs either Ci’s next load or the store at the head of Ci’s write buffer.

And exactly as in §3.7, the switch can then be replaced by a cache-coherent memory system (Figure 4.4b), with everything from §3.8 — speculation, multithreading, non-binding prefetching — carrying over. Indeed, most real TSO implementations seem to be just that: take an SC implementation and insert write buffers. (How speculative cores physically organize them — combined store queue + write buffer, separate load/store queues — is beyond this chapter’s scope.)

One subtlety: on a multithreaded core, TSO write buffers are logically private to each thread context. A shared physical buffer tags entries with thread-context identifiers and permits bypassing only when the tags match.

4.4.1 Implementing atomic instructions

Think of the RMW as a load immediately followed by a store. The load part cannot pass earlier loads (TSO keeps Load→Load). Could it pass earlier stores waiting in the write buffer? No — by an indirect argument: the RMW is an atomic pair, so if its load passed an earlier store, its store would have to pass that store too, and Store→Store reordering is forbidden.

The implementation consequences:

1. The RMW effectively drains the write buffer before performing its load part.
2. The load part needs read-write coherence permission (not the read permission ordinary loads need), so the store part can be ordered immediately after it.
3. The cache controller holds the block between the load and store parts, as in §3.9.

Optimized implementations skip the drain when (a) every buffered entry already has — and keeps — read-write permission in the cache until the RMW commits, and (b) the core performs R10000-style load-speculation checking (§3.8). All the earlier stores and loads then logically commit as a chunk immediately before the RMW.

4.4.2 Implementing FENCEs

TSO doesn’t order a store before a later load — when the programmer needs that order, a FENCE fence Instruction forcing all program-order-earlier memory operations into memory order before all later ones (a.k.a. memory barrier). defined in Chapter 4 — open in glossary between them supplies it. Watch the FENCEs kill the (0, 0) outcome operationally:

And confirm across all interleavings — with the FENCEs in place, TSO yields exactly the three SC outcomes:

Because TSO permits only one type of reordering, FENCEs are infrequent, and a simple implementation — drain the write buffer at the FENCE, and stall later loads until the FENCE commits — may provide acceptable performance. For the relaxed models of chapter 5, where FENCEs are everywhere, their implementation becomes performance-critical.