Prefetching and replacement
Four levers
Every cache optimization pulls one of four levers: reduce the hit time, reduce the miss rate, reduce the miss penalty, or increase bandwidth so several accesses proceed at once. Prefetching attacks misses before they happen. Replacement policy decides which blocks stay, which sets the miss rate for a given size. Multilevel caches shrink the miss penalty. Part C scores each technique on speed, cost and power together.
Prefetching
A prefetcher fetches blocks into the cache before the program asks for them, turning would-be misses into hits. It works only if it guesses which blocks will be needed and fetches them early enough, without evicting anything more useful.
| Prefetcher | Predicts | Good at | Origin |
|---|---|---|---|
| Next-line (tagged) | The block after one that missed or was just prefetched | Sequential code and data | Smith (1982) survey |
| Stream buffer | Several sequential blocks, held in a small buffer beside the cache | Streams, without polluting the cache | Jouppi (1990) |
| Stride (reference prediction table) | The next address in a constant-stride pattern, tracked per load instruction | Array walks with any fixed stride | Chen and Baer (1995) |
| Correlation / global history buffer | Addresses that followed this one in the past | Repeating irregular patterns | Nesbit and Smith (2004) |
| Software prefetch | Whatever the compiler or programmer requests | Known patterns hardware cannot see, such as indirect access | Mowry, Lam and Gupta (1992) |
Software prefetching uses instructions that load a block into the cache without stalling, for example GCC's __builtin_prefetch:
for (int i = 0; i < n; i++) {
__builtin_prefetch(&a[i + 16]);
sum += a[i];
}
Three metrics judge a prefetcher. Coverage is the fraction of baseline misses it eliminates. Accuracy is the fraction of prefetched blocks that are actually used. Timeliness asks whether blocks arrive before they are needed but not so early that they are evicted first. Inaccurate prefetching wastes memory bandwidth and energy and pushes useful data out of the cache, so modern prefetchers throttle themselves when accuracy drops (Srinath and colleagues).
Prefetch simulator
Choose an access pattern and a prefetcher. The cache is fully associative with LRU replacement and 64-byte blocks; each pattern makes 256 accesses.
Things to try. On the sequential array, both prefetchers remove nearly every miss. Switch to "Stride of 256 bytes": next-line now fetches only blocks that are never used, doubling memory traffic for no gain, while the stride prefetcher removes almost every miss. On random accesses no simple prefetcher helps; the stride prefetcher at least stays quiet, while next-line wastes bandwidth. Raising the degree makes a wrong prefetcher more wasteful.
Replacement policies
On a miss in a full set, the cache must evict one block. The ideal choice, proved optimal by Belady in 1966, evicts the block that will be used furthest in the future. That requires knowing the future, so it serves as a yardstick, often written OPT or MIN. Real policies approximate it from the past.
| Policy | Evicts | State per set (n ways) | Notes |
|---|---|---|---|
| OPT (Belady) | Block used furthest in the future | Not implementable | Lower bound for comparison |
| LRU | Least recently used block | Full ordering, about n log₂ n bits | Good for recency-friendly code; thrashes on loops larger than the cache |
| FIFO | Oldest block, regardless of use | log₂ n bits | Simple; ignores reuse |
| Random | A random block | None | Surprisingly competitive at high associativity; avoids LRU's pathological cases |
| Tree pseudo-LRU | A block in the least recently used half, recursively | n − 1 bits | The usual hardware approximation of LRU in L1 and L2 caches |
| SRRIP | A block predicted to be re-referenced in the distant future | 2 bits per block | New blocks start with low priority, so one-time scans cannot flush reused data (Jaleel and colleagues) |
| Adaptive and learned | Varies | Small tables | Set dueling picks a policy at run time (Qureshi and colleagues); Hawkeye trains on what OPT would have done (Jain and Lin) |
Replacement simulator
Enter a sequence of block names and the number of blocks the cache (or one set) can hold. Each row shows one policy: filled cells are hits, outlined cells are misses.
Tree pseudo-LRU needs a power-of-two number of blocks. Random uses a fixed seed so results repeat.
Things to try. The textbook string with 3 blocks gives the classic result: OPT 9 misses, LRU 12, FIFO 15. "Loop one larger than cache" makes LRU, FIFO and SRRIP miss on every access, while random replacement keeps some blocks by luck. "Reuse plus scans" shows SRRIP matching OPT: blocks A and B survive the one-time scans that flush them out of an LRU cache.
Multilevel caches
Why several levels
One cache cannot be both fast and large. A multilevel design lets the L1 stay small enough to keep up with the core, while each lower level is larger and slower and catches most of the misses from the level above. With a 1-cycle L1 that misses 4% of the time, a 12-cycle L2 that misses on 25% of the accesses it sees, and 200-cycle DRAM:
AMAT = 1 + 0.04 × (12 + 0.25 × 200) = 3.48 cycles. Without the L2 it would be 1 + 0.04 × 200 = 9 cycles.
The L2's local miss rate (25%) looks poor, because the L1 has already filtered out the easy accesses. Its global miss rate, the fraction of all processor accesses that go on to DRAM, is 0.04 × 0.25 = 1%. Judge lower levels by global miss rate and by their effect on AMAT.
Design considerations
| Level | Priority | Typical choices |
|---|---|---|
| L1 | Hit time and bandwidth | Split instruction and data caches; 32–128 KB; 8–12 ways; several loads per cycle; virtually indexed, physically tagged so translation overlaps the lookup |
| L2 | Catch L1 misses quickly | Unified; private to a core; 0.5–2 MB; non-blocking with many outstanding misses; aggressive prefetchers |
| Last level (L3) | Capacity; keep traffic off DRAM | Shared by all cores; many MB in slices on an on-chip network, so latency depends on which slice holds the block (a non-uniform cache, as in Kim, Burger and Keckler); 12–16 ways; adaptive replacement |
Other choices span levels. The block size is usually the same at every level (64 bytes) to keep transfers simple. Lower levels are write-back to save bandwidth. Each level must track many outstanding misses at once, or the core stalls even when there is parallelism to exploit.
Inclusion
| Policy | Rule | Advantage | Drawback |
|---|---|---|---|
| Inclusive | Every block in L1 or L2 is also in the last level | The last level can answer coherence checks for the whole chip | Duplicated capacity; evicting a block from the last level must also remove it above, which can hurt hot blocks |
| Exclusive | A block lives in only one level; the last level holds blocks evicted from above | Total capacity is the sum of all levels | More data movement between levels; coherence needs separate tracking |
| Non-inclusive | No guarantee either way | Flexible; avoids forced back-invalidations | Needs a snoop filter or directory to track private caches |
Baer and Wang worked out the conditions under which a hierarchy can maintain inclusion. Later work, such as temporal-locality-aware management (Jaleel and colleagues), recovers most of the performance of non-inclusive caches while keeping inclusion's simpler coherence.
Real hierarchies
| Processor core | L1 data | L2 | Last level |
|---|---|---|---|
| AMD Zen 4 | 32 KB, 8-way | 1 MB, private | 32 MB L3 per 8-core chiplet; 96 MB with stacked 3D V-Cache |
| Intel Raptor Lake performance core | 48 KB, 12-way | 2 MB, private | Up to 36 MB L3, shared |
| Apple M1 performance core | 128 KB | 12 MB, shared by the performance cluster | System-level cache shared with the GPU |
Figures as published by the vendors or measured by independent reviewers; configurations vary by product.
Hierarchy calculator
Set each level's latency, local miss rate, energy per access and capacity. The calculator reports average access time, average energy and total SRAM, and compares the same design without its L3.
| Level | Hit time (cycles) | Local miss rate (%) | Energy per access (pJ) | Capacity (KB) |
|---|---|---|---|---|
| L1 | ||||
| L2 | ||||
| DRAM | – | – |
Model assumptions
Each access starts at L1; an access that misses at one level continues to the next. Energy per access is charged at every level the access reaches, and includes moving the block from that level. Turning the L3 off sends L2 misses straight to DRAM and assumes the L1 and L2 behave the same. Default energies are illustrative orders of magnitude for a recent process; replace them with figures for your own technology, for example from CACTI.
Things to try. With the defaults, the 32 MB L3 cuts average access time by about a fifth and average energy by almost half, because it keeps most L2 misses away from DRAM, whose energy per access dwarfs everything else. Raise the L3 miss rate to see when a big L3 stops paying for its silicon, or halve the L1 miss rate to see how much more the first level matters than the last.
Evaluating optimizations
Speed, cost and power
| Technique | Hit time | Miss rate | Miss penalty | Bandwidth | Power | Cost |
|---|---|---|---|---|---|---|
| Small, simple L1 | better | worse | better | better | ||
| Larger cache | worse | better | worse | worse | ||
| Higher associativity | worse | better | worse | worse | ||
| Larger blocks | better | worse | worse | |||
| Way prediction | better | better | worse | |||
| Pipelined, banked caches | worse | better | worse | |||
| Non-blocking caches | better | better | worse | |||
| Critical word first | better | worse | ||||
| Merging write buffer | better | better | worse | |||
| Victim cache | better | worse | ||||
| Hardware prefetching | better | better | worse | worse | worse | |
| Compiler optimizations | better | better | better | |||
| Adaptive replacement | better | better | worse | |||
| Adding a cache level | better | better | worse |
"Power" counts the net effect on energy per useful access: avoiding a DRAM access usually saves far more than the extra on-chip work costs. "Cost" means silicon area and design complexity. A blank cell means little or no effect.
The cost of SRAM
Each SRAM bit uses six transistors, and caches routinely take a large share of a processor die. SRAM has also stopped shrinking as fast as logic at recent process nodes, so every extra megabyte grows more expensive relative to the cores around it. Designers have responded by moving cache into cheaper silicon: AMD stacks an extra 64 MB SRAM die on top of a CPU chiplet (3D V-Cache), and IBM has used embedded DRAM for large on-chip caches in its POWER processors.
Cost is not only area. Higher associativity, many outstanding misses, adaptive replacement and coherence tracking all add design and verification effort, and a cache bug is as serious as a core bug.
Saving power
| Source | Technique | Idea |
|---|---|---|
| Dynamic (switching) energy | Way prediction | Read only the way most likely to hit, instead of all ways in parallel (Powell and colleagues) |
| Phased access | Read tags first, then only the matching data way; slower but lower energy, common in large L2 and L3 caches | |
| Filter cache | A tiny cache in front of L1 serves most accesses at very low energy (Kin, Gupta and Mangione-Smith) | |
| Static (leakage) energy | Drowsy caches | Hold idle lines at a low voltage that preserves data but leaks less (Flautner and colleagues) |
| Cache decay | Switch off lines that have not been used for a while; they are probably dead (Kaxiras, Hu and Martonosi) | |
| Way and slice gating | Power down whole ways or cache slices when the workload does not need the capacity | |
| Data movement | Fewer, more accurate DRAM accesses | Better replacement and accurate prefetching save the most energy of all, because off-chip transfers cost far more than on-chip ones |
Judging an optimization
- Measure the right thing. Use AMAT or, better, total execution time on representative workloads. A lower miss rate means little if hit time or cycle time grows.
- Count every term. Ask which of hit time, miss rate, miss penalty and bandwidth the technique changes, and in which direction.
- Include energy. Compare energy per task, or the energy-delay product when both speed and battery life matter.
- Include cost. Weigh the area and complexity against spending the same silicon on something else, such as another core or a larger cache.
- Check the corner cases. Streaming, random and multi-program workloads expose the patterns where a technique backfires, as the simulators on this page show.
Resources
Interactive tools and references
Peer-reviewed reading
- Belady, L. A. (1966). A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2), 78–101.The optimal policy every replacement scheme is measured against.doi.org/10.1147/sj.52.0078
- Jouppi, N. P. (1990). Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. Proc. ISCA, 364–373.Victim caches and stream buffers.doi.org/10.1109/ISCA.1990.134547
- Chen, T.-F., & Baer, J.-L. (1995). Effective hardware-based data prefetching for high-performance processors. IEEE Transactions on Computers, 44(5), 609–623.The per-instruction stride prefetcher in the simulator.doi.org/10.1109/12.381947
- Mowry, T. C., Lam, M. S., & Gupta, A. (1992). Design and evaluation of a compiler algorithm for prefetching. Proc. ASPLOS V, 62–73.Software prefetching placed by the compiler.doi.org/10.1145/143365.143488
- Nesbit, K. J., & Smith, J. E. (2005). Data cache prefetching using a global history buffer. IEEE Micro, 25(1), 90–97.Prefetching irregular but repeating patterns.doi.org/10.1109/MM.2005.6
- Srinath, S., Mutlu, O., Kim, H., & Patt, Y. N. (2007). Feedback directed prefetching. Proc. IEEE HPCA, 63–74.Throttling prefetchers by measured accuracy and timeliness.doi.org/10.1109/HPCA.2007.346185
- Qureshi, M. K., et al. (2007). Adaptive insertion policies for high performance caching. Proc. ISCA, 381–391.Set dueling and thrash-resistant insertion.doi.org/10.1145/1250662.1250709
- Jaleel, A., et al. (2010). High performance cache replacement using re-reference interval prediction (RRIP). Proc. ISCA, 60–71.The SRRIP policy in the simulator.doi.org/10.1145/1815961.1815971
- Jain, A., & Lin, C. (2016). Back to the future: Leveraging Belady's algorithm for improved cache replacement. Proc. ISCA, 78–89.Learning replacement decisions from what OPT would do.doi.org/10.1109/ISCA.2016.17
- Baer, J.-L., & Wang, W.-H. (1988). On the inclusion properties for multi-level cache hierarchies. Proc. ISCA, 73–80.When and how a hierarchy can stay inclusive.doi.org/10.1109/ISCA.1988.5212
- Jaleel, A., et al. (2010). Achieving non-inclusive cache performance with inclusive caches: Temporal locality aware (TLA) cache management policies. Proc. MICRO-43, 151–162.Recovering performance lost to inclusion.doi.org/10.1109/MICRO.2010.52
- Kim, C., Burger, D., & Keckler, S. W. (2002). An adaptive, non-uniform cache structure for wire-delay-dominated on-chip caches. Proc. ASPLOS X, 211–222.Why large last-level caches have non-uniform latency.doi.org/10.1145/605397.605420
- Kin, J., Gupta, M., & Mangione-Smith, W. H. (1997). The filter cache: An energy efficient memory structure. Proc. MICRO-30, 184–193.Trading a little speed for a lot of energy.doi.org/10.1109/MICRO.1997.645809
- Powell, M. D., et al. (2001). Reducing set-associative cache energy via way-prediction and selective direct-mapping. Proc. MICRO-34, 54–65.Reading one way instead of all of them.doi.org/10.1109/MICRO.2001.991105
- Kaxiras, S., Hu, Z., & Martonosi, M. (2001). Cache decay: Exploiting generational behavior to reduce cache leakage power. Proc. ISCA, 240–251.Turning off lines that are probably dead.doi.org/10.1145/379240.379268
- Flautner, K., et al. (2002). Drowsy caches: Simple techniques for reducing leakage power. Proc. ISCA, 148–157.Low-voltage standby that keeps data.doi.org/10.1109/ISCA.2002.1003572