Caches and coherence

You know a program is a stream of loads, stores and arithmetic. The architect’s problem is that a load-to-use latency of a few cycles is possible only for a few tens of kilobytes: Intel lists 4 cycles for a 32 KB L1, 12 for a 256 KB L2 and 44 for the shared L3 on one recent client core, against about 80 ns (hundreds of cycles) for DRAM.⁸ Caches exploit locality to make the average access look like the fast case. Four topics organize the chapter:

• Organization and policy. Line size, associativity, replacement, write and inclusion policies, and the three Cs as the language for what each choice fixes.²
• Latency arithmetic. AMAT composed recursively across levels, and why out-of-order cores and prefetchers turn it into a question of memory-level parallelism.
• Translation. TLBs, page walks and the virtually indexed, physically tagged L1.³
• Coherence and consistency. MESI, snooping versus directories, false sharing, and a brief look at the memory models of x86, Arm and RISC-V.⁴

Product numbers come from vendors’ and open projects’ own documents, x86 (AMD, Intel), Arm and RISC-V side by side, in dated boxes. The same principles shape GPU memory systems, covered in SIMT and GPUs, and the AI-specific limits of HBM and the KV cache in The memory wall.

Locality is a property of the access stream, and it can be measured. For a line, the reuse distance is the number of distinct other lines touched between two uses. A fully associative LRU cache of $C$ lines hits exactly the accesses whose reuse distance is less than $C$, so the histogram of reuse distances gives the miss rate of every LRU cache size at once (Under the hood shows the algorithm). Spatial locality appears as short strides: a unit-stride walk over 4-byte words touches a new 64-byte line every 16 accesses, a stride of 64 bytes or more touches a new line every time.

In the column walk of the figure, each line is reused only after five others, so the cache must hold all six lines (and not map them to colliding sets) for the reuse to become hits. Drepper’s 1000 × 1000 matrix multiply has the same structure at scale: each pass of the inner loop touches 1,000 lines of each matrix, far more than a 32 KB L1 holds, which is why the transposed version ran 4.3× faster, and why blocking (tiling the loops so a sub-matrix is reused while it is resident) did better still, at 17.3% of the original time.⁷ Pointer-chasing workloads are the hard case: their reuse distances are long, their strides irregular, and each load’s address depends on the previous load, which defeats both caches and prefetchers.

Each level filters the traffic seen by the next. For a two-level hierarchy, distinguish the local miss rate of the L2 (misses ÷ accesses that reach the L2) from the global miss rate (L2 misses ÷ all CPU accesses), and normalize by work with misses per instruction.² A deep hierarchy can have an L2 with a poor-looking local miss rate that is still doing its job, because the L1 has already removed the easy hits.

The inclusion choice trades capacity against coherence cost. With an inclusive LLC, a lookup there answers “does any core hold this line?”, so external requests need not probe the private caches. The price is duplication and inclusion victims: evicting a line from the LLC must also invalidate it above, even if a core is actively using it. Jaleel et al. found that these victims, not the lost capacity, account for most of the gap between inclusive and non-inclusive performance.²³ Intel’s Skylake server parts made the switch explicit: a larger 1 MB, 16-way private L2 (14 cycles) and a smaller, non-inclusive L3 of 1.375 MB per core, which can behave like a victim cache of the L2s.⁸ AMD’s exclusive L3 holds lines swapped out of the L2s² and keeps shadow copies of each L2’s tags, so it can still answer coherence questions inside a core complex.¹⁰ Non-inclusive and exclusive designs need that separate tracking (shadow tags, snoop filters or directories), because a miss in the LLC no longer proves that no core holds the line.

A victim cache is the small-scale version of the same idea: a few fully associative entries holding lines just evicted from a direct-mapped L1, which removes many conflict misses at almost no hit-time cost.²

A set-associative lookup is a decode of the index, a parallel read of $N$ tags and $N$ data words, $N$ comparators and an $N$-to-1 multiplexer driven by the hit signals.¹ Reading all ways in parallel keeps latency down but spends energy on $N - 1$ useless data reads; larger caches often read tags first and then only the matching way (serial lookup), or predict the way. Tag storage is not free: for a 48-bit physical address, a 32 KB, 8-way, 64 B cache stores 36-bit tags plus state for 512 lines, about 7% on top of the data.

Index functions need not be the plain low-order bits. Power-of-two strides collide in plain-indexed caches (matrices with power-of-two row lengths are a classic trap), and hashing upper address bits into the index spreads them out at the cost of a little latency and a larger tag.¹ Large shared caches are also split into slices spread across the die, so each address has a home slice somewhere on the on-chip network.⁸

Where the index comes from interacts with translation. If index plus offset fit inside the page offset (12 bits for 4 KiB pages), the L1 can be indexed with virtual-address bits while the TLB translates the tag in parallel: the virtually indexed, physically tagged (VIPT) arrangement.³ That constraint, capacity ≤ page size × ways, is one reason L1 caches grew in ways rather than sets (the Under the hood section works the arithmetic).

The three Cs are defined operationally, by simulation: count compulsory misses with an infinite cache; capacity misses are the additional misses of a fully associative LRU cache of the same size; conflict misses are what remains for the real organization.² The definitions are relative to LRU, so a policy better than LRU can produce “negative” conflict misses, and a real cache can occasionally hit where the fully associative LRU reference misses. The sim uses exactly this classifier.

For a two-level hierarchy:

With Intel’s Skylake client figures (4-cycle L1, 12-cycle L2) and illustrative rates of 5% L1 misses, 30% local L2 misses and a 300-cycle memory access, AMAT is $4 + 0.05\,(12 + 0.3 \times 300) = 9.1$ cycles.⁸ Two caveats keep this honest. First, AMAT is a latency model; an out-of-order core overlaps independent misses and keeps working past them, so the stall time per miss is less than the penalty (how is the subject of Branch prediction and out-of-order execution). Second, memory latency rises with load as queues fill, so a 300-cycle idle latency is optimistic under bandwidth pressure.

Each lever moves a different C: capacity attacks capacity misses but raises hit time; associativity attacks conflict misses but raises hit time and energy; line size attacks compulsory misses when there is spatial locality, but past a point it raises the miss penalty and fetches unused bytes.²

The Expert view adds a replacement-policy choice (true LRU, tree pseudo-LRU, random) and the miss penalty, and shows the tag, index and offset bit widths for 18-bit addresses. Capacity and conflict misses are separated with a fully associative LRU shadow cache, as in the formal definition. Try:

• Stride with 1,024- or 4,096-byte steps: every stride that is a multiple of the set span lands in one set, and no number of ways short of full associativity helps. Then 4,160 bytes (4,096 + one line): the conflicts vanish. That is the padding trick for power-of-two arrays.
• Matrix columns at 2 KB, 4-way, with LRU versus random replacement. LRU’s worst case is a loop slightly larger than the set: it evicts exactly the line needed next. Random does better, the effect RRIP was designed to exploit.²²
• The two-core pattern with the invalidation count: each write costs one invalidation once the line ping-pongs.

The model is deliberately simple: one level, fixed latencies, no overlap between misses, and no prefetching, so every miss pays the full penalty.

Exact LRU for an $N$-way set must encode a permutation, $\lceil \log_2 N! \rceil$ bits (5 for 4 ways, 16 for 8), updated on every hit. Tree PLRU uses $N - 1$ bits: each access sets the bits on its root-to-leaf path to point away, and the victim is found by following the pointers. It approximates LRU well for small $N$ and can diverge from it, which the figure’s sequence shows (PLRU happens to beat LRU there).² Set dueling dedicates a few sets to each of two policies, counts their misses, and applies the winner to the rest of the cache.² RRIP stores a 2-bit re-reference prediction per line, inserts new lines with a “distant” prediction so scans pass through without displacing the working set, and promotes lines on hits; its dynamic variant duels two insertion policies.²²

Write policy interacts with the rest of the system. Write-back caches hold the only valid copy of dirty data, which is what makes the Modified state of coherence protocols necessary and what ECC must protect. Write-through L1s (with a write-back L2 behind them) simplify coherence and error recovery, since the L2 always has current data, at the cost of store bandwidth absorbed by a write buffer. Streaming stores that will never be read back are better written around the cache entirely; x86’s non-temporal stores do this.⁷

A prefetcher is judged by three measures:

• Coverage: the fraction of demand misses it removes.
• Accuracy: useful prefetches ÷ prefetches issued.
• Timeliness: the line must arrive before use, but not so early that it is evicted first.

Timeliness sets the prefetch distance. If each line takes $t_{\text{work}}$ cycles to consume and memory latency is $L$, the prefetcher must run $d \ge \lceil L / t_{\text{work}} \rceil$ lines ahead, which is Little’s law again: requests in flight = latency × rate. The figure’s next-line prefetcher is accurate but late (it is one line ahead when six are needed), so it saves only a sixth of the stall. Distance also costs capacity and miss-handling resources: every in-flight line needs a miss-status holding register, and XiangShan’s data cache has 16.¹⁶

Stride prefetchers index a table by load PC and store last address, last stride and a confidence counter; Intel notes its IP-based prefetcher distinguishes loads by only the low 8 bits of the instruction address, so two loads in a large loop can alias in the table.⁸ Newer designs add patterns (Redwood Cove added an array-of-pointers prefetcher), but the page-boundary limit and the dependence chain of true pointer chasing remain.⁸⁷

The TLB sits on the L1 hit path, so its latency is hidden by overlapping it with the cache index. In a virtually indexed, physically tagged L1 the set is chosen with untranslated low bits while the TLB produces the physical page number, which is then compared with the tags.³ This works without aliasing only if index + offset bits ≤ page-offset bits. A 32 KB, 8-way L1 with 64-byte lines uses exactly 12 bits; Zen 4’s 32 KB 8-way L1D fits.¹⁰ Larger L1s break the rule and must handle synonyms (two virtual addresses for one physical line landing in different sets): XiangShan’s 128 KB, 8-way data cache does so with help from its L2.¹⁶ Fully virtual caches avoid translation on a hit but need address-space IDs in their tags and suffer the same aliasing problem.³

Walk cost is the expensive part of a TLB miss. Each of the four levels is a dependent load that may itself miss in the data caches, so designs add page-walk caches for upper-level entries and per-page-size TLBs; GPUs pay the same cost, and SIMT and GPUs quotes a measured example. Context switches either flush the TLB or tag entries with an address-space ID. Prefetchers stop at page boundaries partly because crossing one needs a translation that may fault.⁷

The invariant MESI maintains is single-writer/multiple-reader per line: at any time either one cache may write (M or E) or any number may read (S). The stable states hide the hard part. Requests are not atomic on a split-transaction bus or a network, so real protocols add transient states (I→S waiting for data, S→M waiting for acknowledgments) and must resolve races between them.⁴

Snooping needs an ordered broadcast medium as the serialization point and a tag lookup in every cache for every miss; both bandwidth and energy grow with the number of caches.⁴ Directories (first proposed by Censier and Feautrier in 1978) make the line’s home the serialization point and allow unordered networks. A full-map directory stores a bit per core per line, which grows linearly with cores; practical designs use sparse directories organized as set-associative caches of tracked lines (whose own evictions force invalidations), limited-pointer or coarse-vector encodings, or embed the sharer bits in an inclusive LLC’s tags.⁵ A read of a line held modified elsewhere becomes a three-hop transaction (requester → home → owner → requester), which is why such hits cost more: on an older Xeon, an L3 hit took about 42 cycles when the line was clean but about 73 when another core held it modified.⁸

Synchronization stresses coherence hardest. A spin lock built on atomic swap makes every waiting core request the line in M on each attempt; test-and-test-and-set spins on a shared copy and attempts the swap only when the lock looks free, and load-reserved/store-conditional pairs avoid locking the bus.⁴

Coherence is not consistency

Coherence orders accesses to one location. A memory consistency model says how accesses to different locations may appear reordered to other cores.⁴ Lamport’s sequential consistency requires a single interleaving that respects every core’s program order.²¹ No mainstream ISA promises it: x86 is total store order, where a store can sit in the core’s store buffer while a later load to another address completes¹⁹; Armv8 and RISC-V RVWMO are weaker still, and code that needs order uses fences (MFENCE, DMB, FENCE) or acquire/release accesses.²⁰¹⁸ Under the hood shows the store-buffering test that separates them.

Beyond the headline numbers: Intel’s Skylake client L1 sustains about 81 bytes per cycle of its 96-byte peak and the L3 about 18 of 32, so bandwidth falls faster than capacity rises.⁸ Remote memory costs about 153 ns against 82 ns local on a two-socket Xeon, the NUMA gap discussed in Multicore and vector units.⁸ The EPYC 9684X in the cited comparison carries 1,152 MB of L3, ten times either of the other two chips.¹⁴ For the hardware cost of SRAM at advanced nodes, and why AI accelerators chase even larger on-chip memories, see The memory wall and Wafer-scale and SRAM-heavy designs.

• Hit time versus miss rate. The L1 is sized to the hit-time budget, not to the miss curve. Every extra pipeline stage of load latency costs on dependent chains, so designers accept a higher L1 miss rate and back it with a fast L2.² The figure’s model shows the optimum moving to larger caches as the penalty behind them grows, which is the economic argument for multiple levels.
• Associativity and the VIPT constraint. To grow an L1 while indexing with page-offset bits, designers add ways rather than sets (capacity ≤ ways × page size), so L1 associativity has risen; going past the limit means handling aliases, as XiangShan’s 128 KB L1 does.³¹⁶
• Inclusion. Inclusive LLCs filter snoops but suffer inclusion victims; non-inclusive and exclusive LLCs gain capacity but need separate tracking of core-cache contents (snoop filters, shadow tags, directories), which itself costs area.²³¹⁰
• Directory storage. Full sharer vectors grow with core count; sparse or imprecise directories trade storage for extra invalidations and broadcasts.⁵
• Replacement at the LLC. LRU is fragile under scans and thrashing; RRIP-style insertion policies and set dueling buy several percent of throughput for 2 bits per line.²²
• Prefetch aggressiveness. Distance and degree trade timeliness against bandwidth and pollution; on shared caches one core’s prefetches evict another’s data, and prefetchers that stop at 4 KiB boundaries waste the start of every page in long streams.⁷
• Caches versus scratchpads. Caches make memory management automatic at the cost of tags, coherence and unpredictable timing. GPUs and AI accelerators move part of the hierarchy to software-managed memory, as in SIMT and GPUs and Dataflow and spatial meshes.

1. Classifying misses: the stack algorithm

Because LRU has the inclusion property (an LRU cache of $C$ lines always contains what an LRU cache of $C - 1$ lines contains), one pass over a trace with an LRU stack gives the miss count of every fully associative cache size at once: an access hits in a cache of $C$ lines exactly when its stack distance (reuse distance) is below $C$. The three-C split then needs one extra run of the real organization²:

seen   = empty set                # every line ever touched
stack  = empty LRU list           # fully associative reference
real   = cache(size, line, ways)  # the organization under test

for addr in trace:
  ln   = addr / line_size
  d    = stack.distance(ln)       # distinct lines since last use, or inf
  stack.move_to_top(ln)
  if real.access(ln) == HIT:  count.hit++
  elif ln not in seen:        count.compulsory++
  elif d >= lines_in_cache:   count.capacity++
  else:                       count.conflict++
  seen.add(ln)

A histogram of $d$ is the program’s reuse profile: its cumulative sum is the hit-rate curve versus cache size for LRU. The sim implements the classifier with a bounded LRU shadow of exactly the cache’s size, which gives the same answer for that one size.

2. Replacement state

Exact LRU over $N$ ways needs $\lceil \log_2 N! \rceil$ bits per set; tree PLRU needs $N - 1$. For 8 ways that is 16 bits versus 7; for 16 ways, 45 versus 15. RRIP uses $M$ bits per line ($M = 2$ in the paper): insert at $2^M - 2$ (“long re-reference”), promote to 0 on a hit, and on a miss evict a line at $2^M - 1$, aging the whole set until one exists.²² The insertion position is what gives scan resistance: a line touched once never climbs above lines with demonstrated reuse.

3. The MESI transitions

state  event            action                 next
I      CPU read         BusRd                  E (no sharer) / S (sharer)
I      CPU write        BusRdX                 M
S      CPU read         -                      S
S      CPU write        BusUpgr (invalidate)   M
E      CPU write        -   (silent)           M
M      CPU read/write   -                      M
S      snoop BusRdX     -                      I
E      snoop BusRd      -                      S
E      snoop BusRdX     -                      I
M      snoop BusRd      supply data, write back S
M      snoop BusRdX     supply data            I
M      evict            write back             I

These are the stable states only; a real controller adds transient states for every transition that waits on the bus or network, and the directory version replaces broadcasts with messages to the home node, which forwards or invalidates as its sharer record requires.⁴⁵

4. Memory consistency in one litmus test

The store-buffering (SB) test is the simplest program whose outcome differs between sequential consistency and the models real processors implement:

initially x = 0, y = 0

core 0            core 1
x = 1             y = 1
r0 = y            r1 = x

question: can r0 == 0 and r1 == 0 ?
  sequential consistency : no
  x86-TSO                : yes  (each store waits in its core's store buffer)
  Armv8, RISC-V RVWMO    : yes
  with a full fence between the store and the load on both cores : no

Sequential consistency is Lamport’s definition.²¹ x86 permits only this store-to-load reordering (TSO), with MFENCE to forbid it.¹⁹ Armv8’s model, revised to be multicopy-atomic and now specified formally, and RISC-V’s RVWMO are weaker still: other cores may observe a core’s accesses to different addresses out of order, so message-passing code needs release/acquire accesses or barriers; RISC-V offers the optional Ztso extension for code ported from x86.²⁰¹⁸⁶ Coherence is still per-location: all of these models guarantee that every core sees the writes to one address in one order.

5. The VIPT limit, worked

With page size $P$, line size $L$ and $W$ ways, a cache of capacity $C$ has $C / (LW)$ sets. Index plus offset bits stay within the page offset when

With 4 KiB pages: 8 ways allow 32 KB, 12 ways 48 KB, 16 ways 64 KB. Zen 4’s 32 KB 8-way L1D sits exactly at the limit.¹⁰ XiangShan’s 128 KB 8-way L1D is four times past it, so two index bits come from the virtual page number and the design resolves the resulting aliases with its L2.¹⁶ Larger pages relax the bound for data that lives in them, but the cache must work for 4 KiB pages too.

The threads left open here continue in Multicore and vector units: the interconnect that carries coherence traffic, NUMA placement, simultaneous multithreading sharing an L1 between threads, and vector units whose wide loads raise the bandwidth each core asks of its caches. For the AI side of the same memory problem, HBM and the KV cache, see The memory wall.