Lecture 22: Caches

What this lecture covers

This lecture answers a central question left open from the memory-hierarchy discussion: once you decide to build a hierarchy of small fast memories and large slow ones, how do you actually design the cache that sits between the processor and DRAM? It builds on the temporal- and spatial-locality arguments from the previous lecture and works through the fundamental cache design decisions: how memory blocks map into the cache (placement), what to evict when the cache is full (replacement), how to handle writes, and how instruction and data caches differ from one another and across levels of the hierarchy.

By the end, you can explain the difference between direct-mapped, set-associative, and fully associative caches, reason about why higher associativity has diminishing returns, describe how LRU is approximated in real hardware, and explain the trade-offs behind write-back versus write-through caches and inclusive versus exclusive multi-level hierarchies.

Key ideas

• Cache (general definition): any structure that memorizes previously used or produced data to avoid repeating a long-latency operation, whether it is a hardware processor cache, a web browser cache, or a programmer-managed scratchpad memory.
• Placement: the policy that decides where in the cache a given memory block can be stored; it defines direct-mapped, set-associative, and fully associative caches.
• Direct-mapped cache: each memory block maps to exactly one cache location, which is simple to build but can suffer 0% hit rate under conflict misses even when the cache has free space.
• Set-associative cache: an index selects a set of multiple locations (ways), and a block can go into any way within that set, trading extra comparison hardware for fewer conflict misses.
• Average memory access time (AMAT): hit rate * hit latency + miss rate * miss latency, where miss latency itself depends on the hit/miss behavior of the lower levels of the hierarchy.
• Replacement policy: the rule for choosing which block to evict on a miss when a set is full; options include LRU, random, FIFO, not-most-recently-used, and Belady's optimal (OPT) policy, which needs knowledge of future accesses and so is only used as an analytical upper bound.
• Write-back vs. write-through: write-back delays updating lower levels until eviction (using a dirty bit) and can combine multiple writes, while write-through updates every level immediately, which is simpler but uses more bandwidth and energy.
• Sub-blocked (sector) cache: splits a cache block into sub-blocks with separate valid bits so a write or read can allocate only part of a block instead of the whole block.
• Inclusive vs. exclusive hierarchy: inclusive caches duplicate data across levels (simplifying coherence), exclusive caches avoid duplication (using capacity better), and non-inclusive caches make no guarantee either way.

Walkthrough

Recap: memory hierarchy and what a cache is (4:55)

The lecture opens by recapping why memory hierarchies exist: an ideal memory would have zero latency, infinite capacity, and infinite bandwidth, but these goals conflict, so systems instead use multiple levels of storage that get progressively larger and slower moving away from the processor, relying on temporal and spatial locality to keep most accesses fast. The lecture then generalizes the term "cache" beyond the processor context, giving web caching and GPU scratchpad memory as examples, and stresses that a cache can be hardware-managed (automatic) or software/programmer-managed, which is why "is cache handling an ISA or microarchitecture problem" does not have a single answer.

Mapping memory to the cache: direct-mapped, set-associative, fully associative (13:02)

The core placement question is which cache location(s) a given memory block can occupy. In a fully associative cache, any block can go to any location, giving maximum flexibility at the cost of needing to search the whole cache. In a direct-mapped cache, part of the block's address (the index) determines exactly one possible location, which is simple but rigid. Set-associative caches sit between the two: the index selects a set containing multiple ways, and within that set a block can be placed freely. The lecture notes that direct-mapped and fully associative are just the two extremes of set-associativity (one way, and one set, respectively).

Cache access basics and the direct-mapped toy example (21:08)

Using an 8-bit address space and 8-byte blocks, the lecture walks through how an address splits into byte-offset, index, and tag bits, and how a cache access checks the valid bit, compares the stored tag to the address tag, and returns a hit or miss. It defines hit rate and AMAT, and poses the open question of whether minimizing AMAT is always the right goal for improving overall program performance (the answer, developed later, is no, because not all misses cost the same). The direct-mapped toy cache example shows concretely how blocks 0, 8, 16, and 24 all map to the same cache line, illustrating conflict misses: accesses can thrash a location even while other locations sit empty.

Associativity trade-offs and conflict misses (36:18)

Moving to two-way and four-way set-associative designs reduces conflict misses by giving each index multiple candidate ways, at the cost of extra tag comparators and multiplexers. The lecture works through an access pattern (A, B, C, D repeating) to show how a two-way cache can still thrash while a four-way cache resolves it. It then discusses the general trend: higher associativity increases hit rate but with diminishing returns, while increasing access latency and hardware cost, so real designs pick a point where added complexity no longer pays for itself.

Replacement policies: LRU and its approximations (45:27)

For a set with multiple candidate blocks, the cache needs an eviction policy. The lecture covers insertion, promotion, and eviction as the three decisions that shape block priority, then focuses on LRU (evict the block used least recently) versus alternatives like random, FIFO, and not-most-recently-used. It shows that implementing perfect LRU needs log2(n!) bits for an n-way set, which grows quickly, so real processors approximate it with schemes such as not-MRU or hierarchical LRU. A worked example shows LRU failing completely (0% hit rate) on a cyclic access pattern larger than the set's associativity ("set thrashing"), where random replacement can actually do better. Belady's optimal (OPT) policy, which evicts the block referenced furthest in the future, is presented as an unimplementable but useful analytical bound for measuring how much room there is to improve a real replacement policy.

Handling writes: write-back, write-through, and sub-blocking (1:20:01)

The lecture explains write-back caches, which use a dirty bit to defer propagating updates to lower levels until eviction, versus write-through caches, which update every level immediately. Write-back saves bandwidth and energy by combining repeated writes but is more complex; write-through keeps all levels consistent, which simplifies coherence. It also covers the write-miss allocation decision (allocate the block into the cache versus writing straight to the next level) and introduces sub-blocked or sector caches, which add separate valid bits per sub-block so a write can update only part of a cache block without transferring the whole line.

Instruction vs. data caches and multi-level cache design (1:31:05)

The lecture compares unified caches (shared capacity, better utilization, but instructions and data can evict each other) with separate instruction and data caches, noting that L1 is almost always split because fetch and memory-access stages sit in different parts of the pipeline, while L2 and beyond are usually unified. It then contrasts design goals across levels: L1 prioritizes low latency (small, low associativity, parallel tag/data access), while L2 and L3 prioritize hit rate and energy efficiency (larger, more associative, serial tag/data access). Real examples from Apple M1, AMD's 3D-stacked L3, IBM Power10, and Nvidia GPU scratchpad memory illustrate these trade-offs, and the lecture closes by defining inclusive, exclusive, and non-inclusive multi-level hierarchies.

Before you watch

• Review the previous lecture on memory hierarchy, temporal locality, and spatial locality, since this lecture builds directly on those ideas.
• Be comfortable with binary address arithmetic (splitting an address into offset, index, and tag bits).
• Recall content-addressable memory (CAM) from the out-of-order execution lectures, since set-associative lookups use the same idea.

Check your understanding

1. Why can a direct-mapped cache have a 0% hit rate on some access patterns even when the cache is not full?
2. How many bits are minimally needed to implement perfect LRU for a four-way set-associative cache, and why does real hardware usually avoid that exact scheme?
3. Under what conditions does write-back outperform write-through, and vice versa?
4. Why is Belady's optimal replacement policy not implementable in a real cache, and what is it used for instead?
5. Why are L1 instruction and data caches almost always separate while L2 and L3 caches are usually unified?