3.7A Basic SC Implementation with Cache Coherence

SC, now with parallelism

Cache coherence lets an SC implementation execute non-conflicting loads and stores completely in parallel. Two operations conflict conflicting accesses Two accesses from different threads to the same location where at least one is a store (or RMW). defined in Chapter 3 — open in glossary if they are to the same address and at least one is a store — everything else commutes. And building such a system is conceptually simple.

Coherence stays mostly a black box implementing the SWMR invariant swmr invariant Single-writer–multiple-reader: for any memory location at any moment, either one core may write (and read) it, or some number of cores may only read it. defined in Chapter 2 — open in glossary of chapter 2. The book opens the box just a crack, revealing simple L1 caches that:

• use state modified (M) for an L1 block that one core may write and read;
• use state shared (S) for an L1 block that one or more cores may only read; and
• use GetM getm Coherence request to obtain a block in a read-write (Modified) state. defined in Chapter 3 — open in glossary and GetS gets Coherence request to obtain a block in a read-only (Shared) state. defined in Chapter 3 — open in glossary to denote coherence requests to obtain a block in M or S, respectively.

(No deeper understanding of coherence internals is needed — that’s chapters 6 and beyond.)

The design

Take §3.6’s switch model and replace the switch + memory with a cache-coherent memory system drawn as a black box. As before, each core presents memory operations to the memory system one at a time, in its program order, and the memory system fully satisfies each request before beginning the next request from the same core.

Now open the box a little: each core connects to its own L1 cache. The memory system can respond to a load or store to block B if its L1 holds B with appropriate coherence permission — state M or S for loads, state M for stores. Crucially, it can respond to requests from different cores in parallel, provided their L1s hold the needed permissions:

Why is the arbitrary logical ordering legal? Because operations that can be satisfied by L1 caches are always non-conflicting: if two of them could conflict — same block, at least one writer — the SWMR invariant would forbid both caches from simultaneously holding sufficient permission. So concurrency among permission-holders is invisible to SC, and any placement into 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 tells a consistent story.

Assessment

This implementation of SC:

• fully exploits the latency and bandwidth benefits of caches,
• is as scalable as the cache coherence protocol it uses, and
• decouples the complexities of implementing cores from implementing coherence.

The naive switch’s sequential bottleneck is gone — replaced by per-block permissions that let unrelated work fly in parallel. SC does not preclude parallel execution; it never did. The next section pushes much further: what happens when cores prefetch, speculate, and multithread?