3.8Optimized SC Implementations with Cache Coherence

The golden rule of optimization

Real cores are far more aggressive than §3.7’s basic design: they prefetch, speculate, and multithread to hide memory latency. The license for all of it is one rule: any feature or optimization is legal as long as the end result — the values returned by loads — never violates SC. This section walks through the big four.

Non-binding prefetching

A non-binding prefetch non-binding prefetch A request that changes only a block's coherence state (via GetS/GetM), never registers or data; functionally a no-op for the consistency model. defined in Chapter 3 — open in glossary for block B asks the coherent memory system to change B’s coherence state in one or more caches — via GetS gets Coherence request to obtain a block in a read-only (Shared) state. defined in Chapter 3 — open in glossary (permit loads) or GetM getm Coherence request to obtain a block in a read-write (Modified) state. defined in Chapter 3 — open in glossary (permit loads and stores) — while changing no register and no data in B. Its entire effect stays inside the “cache-coherent memory system” box, making it the functional equivalent of a no-op for the consistency model. So long as loads and stores are performed in program order, it does not matter in what order coherence permissions are obtained. Software, core hardware, and cache hardware (e.g., stream buffers) may all prefetch freely.

Speculative cores

A core with branch prediction executes instructions past the branch — including loads and stores — that may be squashed on a misprediction. The trick: squashed loads look exactly like non-binding prefetches. A speculative load is presented to the L1; it either misses (issuing what amounts to a GetS prefetch) or hits and returns a value to a register. If squashed, the core discards the register update, erasing every functional effect — and the cache deliberately does not undo the state change (unnecessary, and the warm block helps if the load re-executes). Stores are held back: the core may issue a GetM prefetch early, but the store itself touches the cache only when guaranteed to commit.

Dynamically scheduled cores

Out-of-order cores raise the stakes: reordering two loads (say L2 before L1, because L2’s address resolved first) is memory consistency speculation — the core bets that no other core can observe the reordering. Bets must be checked. Step through the two verification schemes:

With non-binding prefetching added, a dynamically scheduled core may take its misses out of order too — program order Load A, Store B, Store C can issue GetM C first, then GetS A and GetM B in parallel. SC is unaffected, because:

• SC dictates the order in which loads and stores (appear to) get applied to coherent memory, but
• SC does NOT dictate the order of coherence activity.

Multithreading

SC accommodates multithreading — coarse-grain, fine-grain, or simultaneous — by making each multithreaded core logically equivalent to multiple virtual cores sharing one L1 via a switch. The one trap: thread T1 must not read what sibling thread T2 stored before that store is visible to threads on other cores. T1 may read the value as soon as the store enters the memory order memory order The total order (<m) on all cores' memory operations that an execution appears to perform. defined in Chapter 3 — open in glossary — e.g., once written to a cache block in state M — but never early out of a shared load-store queue.