Cache Operations

Read Path

When the CPU reads address $A$:

1. Compute the index and tag from $A$
2. Look up the set at that index
3. Compare the tag against all ways in the set
4. Hit: return the data from the matching way
5. Miss: fetch the line from the next cache level, place it in the set, return data

On a miss, if the set is full, one existing line must be evicted to make room.

Write Policies

Write-Through

Every write updates both the cache and the next level immediately.

• Pro: Memory is always up-to-date; simpler coherence
• Con: Every write generates memory traffic; slow

Write-Back

Writes only update the cache. The line is marked dirty. The dirty line is written to memory only when it’s evicted.

• Pro: Reduces memory traffic dramatically (multiple writes to the same line are absorbed)
• Con: Memory may contain stale data; evictions are more expensive

In Practice

Almost all modern processors use write-back caches. The reduced memory bandwidth pressure is critical for performance, especially with multiple cores sharing a memory bus.

Write-Allocate vs No-Write-Allocate

On a write miss (the address isn’t in the cache):

• Write-allocate: fetch the line into the cache, then write to it. Pairs naturally with write-back.
• No-write-allocate: write directly to the next level without caching. Pairs with write-through.

Eviction Policies

When a set is full and a new line must be loaded, which existing line do we evict?

Policy	Description	Used in
LRU	Evict the Least Recently Used line	Conceptually ideal, expensive for high associativity
Pseudo-LRU	Tree-based approximation of LRU	Most real L1/L2 caches
Random	Evict a random line	Some L3 caches; surprisingly competitive

True LRU requires tracking the access order of all $W$ ways — for 16-way, that’s $\log_2(16!) \approx 44$ bits per set. Pseudo-LRU uses a binary tree with $W - 1$ bits, which is much cheaper.

The Three C’s of Cache Misses

Miss Type	Cause	Mitigation
Compulsory	First access to a block (cold start)	Prefetching
Capacity	Working set exceeds cache size	Larger cache, better algorithms
Conflict	Multiple blocks compete for the same set	Higher associativity

Understanding these categories helps diagnose performance problems: if increasing cache size doesn’t help, you likely have conflict misses (try higher associativity) or the working set fundamentally doesn’t fit.

Interactive: Cache Simulator

Configure a small cache, pick an access pattern, and watch each access classify as a hit or as a compulsory / capacity / conflict miss. The classification follows the standard “three Cs” definition: a miss is a conflict miss iff a fully-associative cache of the same total capacity would have hit on the same access.

Common misconception: “If accesses go in cache and out, it’s just a miss — the kind doesn’t matter.”

The miss type tells you which lever to pull. Compulsory misses come down only with prefetching or larger lines (spatial locality). Capacity misses say your working set is too big for this cache level — only a larger cache or a smaller working set helps. Conflict misses, however, can vanish without changing capacity at all: just adding associativity. Try the Strided (i*4096) pattern: every block lands in set 0, so a 32 KB direct-mapped cache misses constantly even though it could fit the data 100× over. Switching to 8-way (same total bytes) fixes it.

Prefetching

Modern CPUs detect access patterns and prefetch cache lines before they’re needed:

• Stride prefetcher: detects sequential or strided access (e.g., array traversal)
• Stream prefetcher: tracks multiple concurrent access streams
• Software prefetch: explicit __builtin_prefetch() hints from the programmer

Prefetching converts compulsory misses into hits by loading data before the CPU asks for it.