9.1System Models

Chapters 7 and 8 used the simplest system model that could teach the fundamentals: one level of physically addressed, write-back data cache per core. Real systems have more moving parts — six of them, each with its own coherence story.

9.1.1 Instruction caches

Truly self-modifying code is rare, but instruction blocks do get written: the OS loading a program, a JIT generating code, a runtime re-optimizer. I-cache coherence instruction cache coherence Keeping instruction caches coherent with code-modifying stores (OS program loading, JIT compilation, runtime re-optimization). I-cache blocks are read-only (I or S); a GetM invalidates them. The hard part is in-pipeline instructions: AMD Opteron tracks in-flight instructions and flushes on change; Power leaves it to software via icbi. defined in Chapter 9 — open in glossary looks trivial — blocks are read-only (only I or S; the core modifies code via stores to its data cache), so the i-cache controller just invalidates on an observed GetM (possibly from its own L1D).

The genuine subtlety: a fetched instruction may sit buffered in the pipeline for many cycles (picture a 128-entry window stalled on DRAM misses) — coherent i-cache, stale pipeline. Two answers:

• Hardware (AMD Opteron): a structure tracks which instructions are in flight; a detected change flushes the pipeline.
• Software (Power): code changes are rare, so let software manage it — the icbi icbi Power's 'instruction cache block invalidate' instruction — software-managed instruction-cache coherence: explicitly invalidates an i-cache entry after code is modified. defined in Chapter 9 — open in glossary instruction invalidates an i-cache entry explicitly.

9.1.2 TLBs

TLBs are caches too — of virtual-to-physical translations — and must be kept coherent. Traditionally they sit outside the hardware protocol, handled by TLB shootdown tlb shootdown The traditional software-managed TLB coherence scheme: the initiator invalidates the page-table entry, interrupts all cores; each traps, invalidates/flushes its TLB entries, flushes the pipeline, and acks back; the initiator waits for all acks before modifying the translation. Power's tlbie instruction replaces the inter-processor interrupts with a hardware broadcast. defined in Chapter 9 — open in glossary :

1. The initiator invalidates the translation (clears the PTE’s valid bit) and sends inter-processor interrupts to all cores.
2. Each core traps, invalidates the entry (or flushes its whole TLB), and flushes its pipeline — no in-flight instruction may keep using the stale translation.
3. Each core acks the initiator (another interrupt).
4. Only after all acks does the initiator modify the translation or reuse the physical page.

Power accelerates this: tlbie (TLB invalidate entry) broadcasts the invalidated virtual page in hardware and completes only when every core is done — no interrupts. Research (UNITD) goes further, folding TLBs into the regular all-hardware protocol by making them snoopable by the physical addresses of the translations they hold — more scalable than shootdown, at the cost of modified TLBs.

9.1.3 Virtual caches

A virtual cache virtual cache A cache accessed with virtual addresses, taking address translation off the hit critical path. Costs: coherence requests (physical addresses) need REVERSE translation, and synonyms can put one physical block in multiple cache locations. Rare today — VIPT (virtually indexed, physically tagged) gets the latency win without the problems. defined in Chapter 9 — open in glossary takes translation latency off the hit path — tempting for L1s, irrelevant lower down. The coherence architect pays twice:

• Coherence invariably runs on physical addresses (memory would otherwise need its own TLB) — so incoming requests need reverse translation.
• Synonyms synonyms Multiple virtual addresses mapping to the same physical address — in a virtual cache they can be resident simultaneously, so one physical block lives at several cache locations, complicating coherence and reverse translation. defined in Chapter 9 — open in glossary : several VAs mapping to one PA can be resident simultaneously, so one reverse translation may name several cache locations.

Hence their rarity today — a VIPT cache (virtually indexed, physically tagged) collects the latency win without either problem.

9.1.4 Write-through caches

Writing every store through to the LLC costs bandwidth and power — which confines the choice to the L1. In exchange ( write-through write-through cache A cache where stores propagate immediately to the next level. Practical only at L1 (bandwidth/power). Buys: a two-state VI protocol, free evictions, an always-current LLC, single-flip-flop state bits, and parity-only fault tolerance (the LLC always holds a valid copy). Complication: TSO write atomicity for multithreaded cores sharing an L1. Used by Sun Niagara and AMD Bulldozer. defined in Chapter 9 — open in glossary L1s appear in Sun Niagara and AMD Bulldozer):

1. A two-state VI protocol vi protocol The two-state (Valid/Invalid) coherence protocol enabled by write-through caches: a store writes through to the LLC and invalidates all other Valid copies; observing another core's write just clears Valid. defined in Chapter 9 — open in glossary : a store writes through and invalidates all other Valid copies. That’s the whole protocol.
2. Evictions are free — just flip to I; the LLC is always current.
3. The LLC responds immediately to coherence requests — it always has up-to-date data.
4. Observing another core’s write just clears one flip-flop — no complex arbitration or dual-ported state RAMs.
5. Fault tolerance on the cheap: the L1 never holds the only copy, so parity suffices — on error, invalidate and refetch.

One complication: with a multithreaded core sharing an L1, TSO’s write atomicity demands that thread T1 not see T0’s store until every other cache’s copy is invalidated or updated.

9.1.5 Coherent DMA

Coherence’s original villain wasn’t a second core — it was DMA coherent dma DMA that participates in coherence so reads find the latest version (even M/O in a cache) and writes invalidate stale copies. Simplest form: give the DMA controller a coherent (single-block) cache. Streaming whole-block writes motivate special ops: GetM-NoData (permission without data) or PutNewData (update memory, invalidate everything). Alternative: OS page-flushing, shootdown-style (embedded only). defined in Chapter 9 — open in glossary . A DMA read must find the latest version (even in a cache’s M or O); a DMA write must invalidate every stale copy. The clean solution: give the DMA controller a coherent cache, making it indistinguishable from a core. But DMA is a strange core:

• It streams — no temporal reuse, so a one-block cache is plenty.
• It writes whole blocks — fetching the old data with a GetM is waste. Protocols add GetM-NoData (M permission, ack instead of Data) or PutNewData (update memory, invalidate all copies — including M and O).

The hardware-free alternative — the OS flushes page P from all caches before any DMA touching P, shootdown-style — is conservative and slow; it survives only in some embedded systems.

9.1.6 Multi-level caches and hierarchical protocols

Multi-level caches. Simplest: every level snoops every request independently (AMD Opteron). Smarter: inclusion cache inclusion A lower-level cache is inclusive if it holds a superset of the upper levels' blocks — enabling it to act as a SNOOP FILTER (miss ⇒ upper caches can't hold the block; AMD Bulldozer). Costs redundant storage and maintenance (recall/invalidate L1 copies on L2 eviction). Alternatives: exclusive (L2 block ⇒ not in L1) and non-inclusive (neither) hold more distinct blocks. defined in Chapter 9 — open in glossary — if the L2 holds a superset of its L1s, then an L2 miss on a snooped block proves the L1s can’t hold it, so the L2 becomes a snoop filter shielding L1 bandwidth (AMD Bulldozer). The bill: redundant storage (an exclusive or non-inclusive hierarchy holds more distinct blocks) and the maintenance complexity of invalidating L1 copies when the L2 evicts (the Recall machinery of §8.6 in another costume).

Multi-chip LLC roles. In one-chip systems the LLC is memory-side and coherence can ignore it. With multiple chips it can instead be a core-side cache holding blocks whose homes are anywhere — and then the LLCs and memories of the chips run a coherence protocol among themselves — or a hybrid of both, with the split to be engineered.

Hierarchical protocols. Everything so far was flat — one protocol, every controller equal. A multi-chip system invites an intra-chip protocol plus an inter-chip protocol: requests satisfied on-chip never escape; each chip looks like a single (coarsely tracked) node to the outer directory. The levels mix freely — snooping inside, directory outside (Sun Wildfire, Stanford DASH) or directory-of-directories (AlphaServer GS320). The strategic payoff for a hierarchical design hierarchical coherence protocol Separate intra-chip and inter-chip coherence protocols composed hierarchically: requests satisfiable on-chip never touch the outer protocol; each chip appears as one node (with coarse state) to the outer directory. Lets commodity chips use simple non-scalable designs. Examples: Sun Wildfire, AlphaServer GS320, Stanford DASH; Marty/Hill virtual hierarchies do it dynamically on flat multicores. defined in Chapter 9 — open in glossary : the commodity chip keeps a simple, deliberately non-scalable protocol instead of one sized for the largest conceivable machine. And at hundreds or thousands of cores, systems will likely be carved into workload/VM domains anyway — Marty and Hill’s virtual hierarchies superpose a hierarchical protocol on a flat multicore so intra-domain sharing is fast but cross-domain sharing still works.