Cache Replacement Policies
LRU, FIFO, and Random: how caches decide which line to evict.
Problem
When a cache set is full and a new block must be loaded, one existing line must be evicted. Which one? The choice directly affects hit rate, and the hardware cost varies dramatically between policies.
How it works
LRU (Least Recently Used): evicts the line that hasn't been accessed the longest. Bets on temporal locality: recently used data is likely to be used again soon. For 2-way caches, LRU is trivial: a single bit per set tracks which way was accessed last. For 4-way, you need to track a full ordering of 4 items (4! = 24 states, 5 bits). For 8-way, exact LRU requires tracking 8! orderings: prohibitively expensive. Real 8+ way caches use pseudo-LRU (tree-based approximation with 7 bits for 8 ways).
FIFO (First In, First Out): evicts the line that was loaded earliest, regardless of whether it was accessed recently. Simpler hardware: just a counter per set pointing to the next victim. Downside: FIFO can evict hot data that was loaded long ago but is still being used frequently. This causes Belady's anomaly: more cache ways can actually increase misses for some access patterns (unlike LRU, which is immune to this).
Random: picks a victim at random. Essentially free hardware (just an LFSR or counter). No tracking state per set at all. Surprisingly competitive: for high-associativity caches (8+ ways), random is within 1–2% of LRU's hit rate on most workloads. This is why some real designs (ARM Cortex-A series L2) use random replacement.
Practical considerations:
• LRU is optimal for caches with 2–4 ways where the tracking cost is low.
• Random is preferred when associativity is high and the silicon budget for tracking is better spent elsewhere.
• FIFO is rare in caches but common in TLBs and write buffers where simplicity matters.
FIFO (First In, First Out): evicts the line that was loaded earliest, regardless of whether it was accessed recently. Simpler hardware: just a counter per set pointing to the next victim. Downside: FIFO can evict hot data that was loaded long ago but is still being used frequently. This causes Belady's anomaly: more cache ways can actually increase misses for some access patterns (unlike LRU, which is immune to this).
Random: picks a victim at random. Essentially free hardware (just an LFSR or counter). No tracking state per set at all. Surprisingly competitive: for high-associativity caches (8+ ways), random is within 1–2% of LRU's hit rate on most workloads. This is why some real designs (ARM Cortex-A series L2) use random replacement.
Practical considerations:
• LRU is optimal for caches with 2–4 ways where the tracking cost is low.
• Random is preferred when associativity is high and the silicon budget for tracking is better spent elsewhere.
• FIFO is rare in caches but common in TLBs and write buffers where simplicity matters.
Key insightLRU's advantage shrinks as associativity grows. At 2-way, LRU clearly wins because every eviction decision is binary. At 16-way, tracking exact recency of 16 items costs more hardware than it saves in hit rate: random gets within a few percent for essentially zero cost. The right policy depends on the associativity budget.