Advanced Caches

Prerequisites: 01-Introduction-and-Metrics Learning Goals: Understand the AMAT equation and the three levers to improve it: hit time, miss rate, and miss penalty. Learn specific hardware and compiler techniques for each lever.

The AMAT Framework

$\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$

Three ways to improve AMAT:

Reducing Hit Time

1. Pipelined Caches

Pipelining the cache = overlapping one cache hit with the next.

$\text{Hit Time} = \text{Actual Hit} + \text{Wait Time}$

Three pipeline stages for a cache:

1. Read the index → find the set
2. Determine hit/miss; begin data read
3. Finish data read

2. Overlap Cache Hit with TLB Hit (VIPT Cache)

A PIPT cache (Physically Indexed, Physically Tagged) uses the physical address → must wait for TLB translation before looking up the cache.

A VIPT cache (Virtually Indexed, Physically Tagged) uses the virtual address for indexing but physical address for tag comparison → TLB translation and cache lookup happen in parallel.

VIPT Design:

• VA page offset bits → used as cache index (no translation needed for index)
• Physical frame number from TLB → used as tag for verification

Constraint for no aliasing: $\text{Cache Size} \leq \text{Associativity} \times \text{Page Size}$

If all index bits come from the page offset portion of the address (bits below the page boundary), there is no aliasing.

Virtually Addressed (VIVT) Cache — full virtual address used:

• TLB and cache can work in parallel
• Problem 1: Must flush cache on every context switch (virtual addresses are process-specific)
• Problem 2: Aliasing — two virtual addresses can map to the same physical location, causing incorrect execution

3. Way Prediction

The processor predicts which way of a set-associative cache will be a hit.

• Correct prediction → fast (like direct-mapped)
• Incorrect prediction → fall back to normal set-associative lookup

Way Prediction Performance:

4. Replacement Policy and Hit Time

NMRU: Only track the most recently used block; replace any other block.

PLRU: Set LRU bit to 1 on access; evict block with LRU bit = 0. When all bits are 1, reset all to 0 and set the evicted block to 1.

Reducing Miss Rate

The 3 Cs of Cache Misses

• Larger cache → reduces capacity misses
• Higher associativity → reduces conflict misses (and some capacity misses)

Larger Cache Blocks

Larger blocks bring in more data per miss (exploits spatial locality):

• Good spatial locality → miss rate improves
• Poor spatial locality → miss rate degrades (wasted bandwidth)
• Larger blocks can reduce compulsory, capacity, and conflict misses

Prefetching

Prefetching = loading a block into cache before it is needed.

• Good guess → eliminates a future miss
• Bad guess → wastes bandwidth, pollutes cache

Compiler prefetching: Insert prefetch instructions; difficult to determine optimal prefetch distance.

Hardware prefetching: Hardware guesses what will be needed soon:

Loop Interchange

Loop interchange: swap inner and outer loops to access arrays in row-major (sequential) order rather than column-major.

• Improves spatial locality → reduces miss rate

Reducing Miss Penalty

Non-Blocking Cache

Blocking cache: Only one outstanding miss at a time — no progress while waiting.

Non-blocking cache allows:

• Hit-under-miss: execute cache hits while waiting for a miss
• Miss-under-miss: issue additional memory requests while waiting for a miss

Non-blocking caches can reduce the effective miss penalty by ~50% (memory-level parallelism).

Miss Status Handling Registers (MSHR)

MSHRs track outstanding misses:

Typical MSHR count: 16–32 registers.

Cache Hierarchies

Multiple cache levels reduce AMAT by catching misses at a closer level:

$\text{AMAT} = T_{L1} + m_{L1} \cdot (T_{L2} + m_{L2} \cdot (T_{L3} + m_{L3} \cdot T_{mem}))$

The final level before main memory is the Last Level Cache (LLC).

Local vs. Global Hit Rate

Inclusion Property

Three possibilities for the same block in L1 and L2:

Enforcing inclusion: requires an inclusion bit per block to track whether the block is in another cache level.

Summary

Key Takeaways:

• AMAT = Hit Time + Miss Rate × Miss Penalty — optimize all three
• VIPT caches: index with virtual, tag with physical → parallel TLB + cache; no flush needed if size ≤ associativity × page size
• Way prediction: direct-mapped speed with set-associative miss rate
• 3 Cs: compulsory (prefetch), capacity (larger cache), conflict (higher associativity)
• Prefetching: hardware stream buffers and stride prefetchers are common
• Non-blocking + MSHR: overlap multiple outstanding misses
• Cache hierarchy: AMAT is recursive through all levels to main memory

Common Exam Topics:

• Compute AMAT for a multi-level hierarchy
• Determine if VIPT cache has aliasing given sizes
• Compare replacement policies

See Also: 01-Introduction-and-Metrics, 09-Cache-Coherence Next: 09-Cache-Coherence