Lecture 23: Caches II and Prefetching

What this lecture covers

This lecture continues the cache design discussion from the previous session and asks a practical question: given the placement and replacement mechanisms already covered, how do cache size, block size, and associativity actually affect performance across real workloads, and what else can be done to hide memory latency beyond just building a better cache? It moves from cache-parameter trade-offs and the three fundamental categories of cache misses, through techniques programmers can use to get more out of a cache, into memory-level parallelism, and finally into prefetching as a separate latency-hiding technique.

After watching, you can explain why bigger caches, bigger blocks, and higher associativity all have diminishing or even negative returns past a point, classify a cache miss as compulsory, capacity, or conflict, rewrite simple loops for better cache behavior, and describe how a hardware prefetcher decides what, when, where, and how to prefetch.

Key ideas

• Working set size: the amount of data a workload touches within a given time window; performance improves as cache size approaches the working set size and then flattens out.
• Cache block size trade-off: larger blocks exploit more spatial locality and reduce tag overhead, but very large blocks waste bandwidth, energy, and cache space when the extra data brought in is not actually used.
• Associativity does not have to be a power of two: tag-matching hardware can be built for any number of ways by dropping comparators, and some real Intel and ARM processors use associativities like 12-way that are not powers of two.
• The three C's of misses: compulsory (first-ever access to a block), capacity (misses that remain even in a fully associative cache of the same size with optimal replacement), and conflict (misses caused by limited associativity forcing evictions).
• Cache-conscious programming: reordering loops (loop interchange), blocking/tiling computation, and splitting hot and cold fields into separate data structures can dramatically improve cache utilization without changing hardware.
• Memory-level parallelism (MLP): overlapping memory accesses matter more than the raw miss count, because a miss that overlaps with other outstanding misses costs less processor stall time than an isolated miss.
• Prefetching: speculatively fetching data before the processor demands it; unlike branch prediction, a wrong prefetch does not break correctness, only wastes bandwidth, energy, and cache space.
• Prefetcher design questions: what address to prefetch, when to issue the request, where to place the prefetched data, and how (software, hardware, or execution-based) it is generated.

Walkthrough

Cache size, block size, and associativity trade-offs (3:55)

The lecture reviews why caches exist (fast and large are conflicting goals) and then walks through how three parameters affect hit rate using real workload data. Increasing cache size helps until the cache is roughly as large as the workload's working set, after which gains are marginal; different workloads show very different curves, from almost no improvement to steep improvement, so there is no single best cache size. Block size shows a similar pattern: bigger blocks exploit more spatial locality up to a point, then waste bandwidth and cache space if the extra bytes brought in are not used. Associativity behaves the same way, trading lower conflict misses for slower access and higher hardware cost.

Non-power-of-two associativity in real processors (14:01)

Because tag-matching logic is just parallel comparators feeding a multiplexer, associativity does not need to be a power of two; you can build an odd-way associative cache by simply dropping comparators from a larger design (though going up, e.g. to nine ways, requires building for the next power of two and disabling the unused ways). The lecture gives Intel's Lion Cove microarchitecture as a real example of non-power-of-two associativity (12-way caches) used in recent laptop processors.

The three C's of cache misses (18:05)

Misses are classified as compulsory (the first touch of a cache line, unavoidable without speculation), capacity (misses that would still occur in a fully associative cache of the same size with an optimal replacement policy, stemming purely from the cache being too small), and conflict (misses caused by limited associativity forcing an eviction that a more associative cache would have avoided). Each category suggests a different fix: prefetching for compulsory misses, higher associativity or techniques like victim caches for conflict misses, and better program or replacement-policy design for capacity misses.

Cache-conscious programming techniques (23:07)

The lecture shows concrete ways programmers can reduce capacity and conflict misses without hardware changes. Loop interchange matches the loop traversal order to the array's memory layout (row-major vs. column-major) so inner-loop accesses stay sequential. Blocking (tiling) divides a computation, such as matrix multiplication or image processing, into chunks that fit inside the cache, so each chunk is fully reused before moving on. Splitting a data structure's frequently accessed fields (like a linked-list key and next pointer) from its rarely accessed fields (like long text) into two separate structures keeps the hot path compact and cache-friendly.

Memory-level parallelism and MLP-aware replacement (38:13)

The lecture challenges the assumption that reducing miss count always improves performance. If two misses overlap in time, saving only one of them does not reduce processor stall time, because the processor is still stalled waiting for the other; only an isolated, non-overlapping miss is fully "on the critical path." Using a worked example comparing Belady's optimal replacement policy against an MLP-aware policy, the lecture shows that a policy with a higher miss count can still produce fewer stalls if it keeps memory-level-parallel misses grouped together, because those misses overlap. A related technique is speculatively starting an off-chip DRAM access in parallel with checking lower cache levels, rather than waiting for each level to miss in sequence.

Prefetching fundamentals: what, when, where, how (1:04:37)

Prefetching anticipates future memory accesses and fetches the data into faster storage before it is demanded, reducing both miss rate and miss latency; it can eliminate compulsory misses, which caching alone cannot avoid. Because a mispredicted prefetch does not break correctness (unlike branch misprediction), prefetchers can afford to be aggressive, at the cost of wasted bandwidth, energy, and possible cache pollution. Prefetcher accuracy is defined as useful prefetches divided by total prefetches issued. The lecture frames prefetcher design around four questions: what address to prefetch (pattern prediction, from simple streaming and strided patterns to more complex delta patterns), when to issue the request (too early wastes space, too late fails to hide latency, so timeliness is the goal), where to place the prefetched data (which cache level, and cache versus a separate prefetch buffer), and how the prefetch is generated (software instructions, transparent hardware, or execution-based prefetching using a lightweight helper thread that runs ahead of the program).

Hardware prefetchers: stream and stride/correlation prefetching (1:35:48)

The lecture walks through IBM Power4's stream prefetcher, which maintains a widening "fetch front" at each cache level, prefetching further ahead the farther a prefetcher sits from the core. It covers prefetch performance metrics: accuracy, coverage (share of misses eliminated), and timeliness. Stride prefetching tracks the address delta produced by a specific load instruction and, once a constant stride is detected with sufficient confidence, prefetches ahead by multiples of that stride to stay timely. For more irregular patterns, correlation-based prefetching learns sequences of deltas and can bootstrap predictions further ahead by feeding its own predicted deltas back into the history, with confidence dropping at each speculative step.

Before you watch

• Review the direct-mapped, set-associative, and fully associative cache designs, plus the replacement policies (LRU, random, Belady's OPT) from the previous lecture on caches.
• Be familiar with array memory layouts (row-major vs. column-major) and basic matrix multiplication.
• Recall branch prediction and out-of-order execution from earlier lectures, since prefetching and memory-level parallelism build on those speculation and parallelism concepts.

Check your understanding

1. Why can increasing cache associativity beyond a certain point hurt overall performance even though it improves hit rate?
2. How would you classify a miss as compulsory, capacity, or conflict, and why does that classification suggest a different fix for each?
3. Give an example of a loop or data-layout change that improves cache behavior, and explain why it works.
4. Why can a replacement policy with a higher total miss count still produce a faster program under memory-level parallelism?
5. Why doesn't a mispredicted prefetch require the same kind of recovery as a mispredicted branch, and what does it cost instead?