Cache Replacement Algorithms

When a cache miss occurs in associative / set-associative cache and set is full, one line must be evicted. Direct-mapped needs no choice. Algorithm balances hit rate vs hardware cost.

1. Least Recently Used (LRU)

Evict the line not used for longest time (least recent). Exploits temporal locality.
Implementation: Per set maintain recency stack / counters. For 2-way, single bit per set; for $k$-way, $\log_2 k!$ states or $k$ counters, or pseudo-LRU tree.
Pros: Best hit rate, approximates optimal. Cons: $O(k)$ bits, complex for large $k$ (e.g. 8-way needs 3 bits per line).

2. First-In First-Out (FIFO) / Round-Robin

Evict oldest inserted line (first loaded). No regard to reuse.
Implementation: Circular pointer per set; increment on insertion.
Pros: Very simple, $\log_2 k$ bits per set. Cons: May evict hot line that was loaded early but still frequent (Belady anomaly in paging).

3. Least Frequently Used (LFU)

Evict line with fewest hits since insertion. Keeps hot lines.
Implementation: Counter per line, increment on hit; on replacement choose min counter.
Pros: Good for skewed access. Cons: Counters saturate, stale history; hot line pollutes after phase change; extra storage.

4. Random Replacement

Pick victim uniformly at random (LFSR).
Pros: Zero bookkeeping, no pathological worst case, surprisingly competitive; used in ARM Cortex, many LLCs.
Cons: Slightly lower hit rate than LRU (~2-5%) but saves power/area.

5. Optimal (Belady's / MIN) - Theoretical

Evict line whose next use is furthest in future (requires future knowledge). Gives minimum misses, used only as offline benchmark to evaluate others. Not implementable.

6. Others

• Not Most Recently Used (NMRU): Opposite of LRU, protect MRU; simpler than LRU.
• Not Recently Used (NRU) / Clock: One reference bit per line, clock hand clears bits; evict first with $R=0$.
• Pseudo-LRU (PLRU) Tree: Binary tree of bits per set, approximates LRU with $\approx k-1$ bits vs $k\log k$.

Algorithm	Hit rate	Hardware	Where used
LRU	High	High	L1/L2 small associativity
PLRU	Near LRU	Medium	Intel L2/L3
FIFO	Medium	Low	Simple caches
Random	Medium	Minimal	LLC, ARM
LFU	Workload dep	High	Not common in cache
Optimal	Max (bound)	N/A	Analysis

Example: 2-way set with lines A,B. Access sequence A B A C.
LRU: After A B A, LRU=B, so C replaces B.
FIFO: After A B A, FIFO=A (oldest), so C replaces A -> one extra miss vs LRU.
Random: 50% chance.

Modern caches: Pseudo-LRU or Tree-LRU for 4-16 way, Random for large LLC to save power; inclusion of dirty bit may bias to evict clean line first to avoid write-back.