Replacement policies (LRU, FIFO, random)

Overview

When a cache is full and a new block needs to be loaded, the cache controller must decide which existing block to evict. This decision is made by the replacement policy. The three fundamental strategies are Least Recently Used (LRU), First-In First-Out (FIFO), and Random.

Why Replacement Policies Matter

The Problem: Cache capacity < Memory size. Temporal locality means recently-used data is likely to be used again. Spatial locality means nearby data is likely to be used soon. A replacement policy exploits these patterns to minimize miss rate.

Performance Impact:

• Miss rate directly affects average memory access time (AMAT): $\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$
• A 1% difference in miss rate can mean 10-20% performance difference in memory-bound applications
• Replacement policy affects miss rate but also has hardware cost

LRU (Least Recently Used)

How LRU Works

Mechanism:

1. Every cache access updates a timestamp or reorders a recency list
2. On eviction, choose the block with the oldest timestamp / at the tail of the list
3. On hit or miss (after loading), mark that block as most recently used

Why this approach? Temporal locality: recently-accessed data is likely to be accessed again soon. The block that hasn't been touched longest has the lowest probability of being needed next.

Derivation of LRU Behavior

Consider a 2-way set-associative cache with blocks A and B in set.

Access sequence: A, B, A, C

Key insight: Each access reorders the recency structure. The block that hasn't been touched longest is always at the "cold" end.

LRU Implementation

Challenge: Tracking recency has hardware cost.

Exact LRU (for small n):

• Counter method: Each block has a timestamp counter. On access, set counter to global time; increment global time. Evict block with smallest counter.
  • Cost: n counters of $\log_2(\text{time})$ bits each
• Pseudo-LRU (tree-based): Use $n-1$ bits to build a binary tree. Each bit indicates which subtree was accessed more recently. On access, flip bits along path from root to block.
  • Cost: Only $n-1$ bits for n-way set
  • Approximation: doesn't track exact LRU, but close enough

For 4-way set: Exact LRU needs 4 × 2 = 8 bits (2-bit counters). Pseudo-LRU needs 3 bits.

FIFO (First-In First-Out)

How FIFO Works

Mechanism:

1. Maintain a queue pointer or timestamp indicating insertion order
2. On eviction, choose the block that entered the cache first
3. On hit, do nothing to the order (this is key difference from LRU)

Why FIFO? Simplicity. No need to track accesses, only insertion order.

Derivation of FIFO Behavior

Consider the same 2-way set, access sequence: A, B, A, C

Critical difference from LRU: The hit on A doesn't move A to the back of the queue. FIFO is oblivious to access patterns after insertion.

FIFO Implementation

Hardware: Single $\lceil \log_2 n \rceil$-bit counter per set. Incredibly cheap.

For 4-way set: 2-bit counter. For 16-way: 4-bit counter.

Belady's Anomaly

Random Replacement

How Random Works

Mechanism:

1. Use a pseudorandom number generator (PRNG) or linear feedback shift register (LFSR)
2. On eviction, generate random index $i \in [0, n-1]$
3. Evict block at way $i$

Why random? When workload is unpredictable or adversarial, any deterministic policy can be exploited. Random avoids worst-case patterns.

Derivation of Random Behavior

For an n-way set, each block has eviction probability:

$P(\text{evict block } i) = \frac{1}{n}$

Expected number of accesses before evicting a specific block (if it's not accessed again):

$E[\text{lifetime}] = n \text{ evictions}$

Why this formula? Each eviction is an independent trial with success probability $\frac{1}{n}$. This is a geometric distribution: expected number of trials = $\frac{1}{p} = n$.

Random Implementation

Hardware: SmallLFSR (e.g., 4-bit for 16-way set) or use low bits of cycle counter. Extremely cheap: ~10 gates.

Comparison: LRU vs FIFO vs Random

| Policy | Miss Rate | Hardware Cost | Anomalies | Best For | |--------|---------------|-----------|----------| | LRU | Lowest for most workloads | Highest (counters/trees) | None (stack algorithm) | Temporal locality | | FIFO | Medium | Lowest (single counter) | Belady's Anomaly | Streaming / sequential access | | Random | Medium-high | Very low (LFSR) | None (probabilistic) | Adversarial / unpredictable workloads |

Why These Differences?

LRU exploits temporal locality:

• Recent accesses predict future accesses
• Best when working set fits in cache and exhibits reuse
• Cost: Must update state on every access

FIFO ignores access patterns:

• Only tracks insertion order
• Works okay for sequential scans (streaming data)
• Fails when blocks are reused after initial load
• Cost: Update only on evictions

Random avoids worst-case:

• No pathological access patterns can cause100% miss rate
• Performance is average across all patterns
• Cost: Minimal hardware, no state updates

Worked Example: Detailed Trace Comparison

Setup: 4-way set-associative cache, access sequence:

A, B, C, D, E, B, A, B, F, G

Let's trace all three policies:

LRU Trace

Total: 8 misses, 2 hits

FIFO Trace

Total: 9 misses, 1 hit

Note: FIFO evicts B at step 7even though B was just accessed (hit). This is why FIFO mises on the second B access.

Random Trace

Assume PRNG outputs: [-, -, -, 1, -, 0, 3, 2, 1]

| Access | Cache State | Random Way | Hit/Miss | Why this step? | |--------|-------------|------------|----------------| | A | [A, -, -, -] | - | Miss | Load A to way 0 | | B | [A, B, -, -] | - | Miss | Load B to way 1 | | C | [A, B, C, -] | - | Miss | Load C to way 2 | | D | [A, B, C, D] | - | Miss | Load D to way 3 | | E | [A, E, C, D] | 1 (B) | Miss | Evict B (random), load E | | B | [A, E, C, D] | - | Miss | Load B to way 1 (just evicted!) | | A | [A, E, C, D] | - | Hit | A still in cache | | B | [A, E, C, B] | 3 (D) | Miss | Evict D (random), load B | | F | [A, E, F, B] | 2 (C) | Miss | Evict C (random), load F | | G | [A, G, F, B] | 1 (E) | Miss | Evict E (random), load G |

Total: 9 misses, 1 hit

Random happened to evict B right before it was needed again (unlucky), but avoided some of LRU's smart evictions by chance.

Summary

Miss rates:

• LRU: 80% (8/10 misses) — best performance
• FIFO: 90% (9/10 misses) — worst here due to evicting recently-hit B
• Random: 90% (9/10 misses) — comparable to FIFO

Key observation: LRU's advantage comes from the two hits on B. By keeping recently-accessed blocks, LRU avoids re-fetching B after the first hit. FIFO and Random don't track recent access, so they evict B and suffer mises.

Advanced: Practical Hybrid Policies

Real processors often use approximations:

Pseudo-LRU (PLRU)

• Tree-based bits to approximate LRU ordering
• Intel Core, AMD Ryzen use PLRU for L2/L3 caches
• Cost: $n-1$ bits for n-way, vs. $n \log n$ for true LRU

Not Recently Used (NRU)

• Single reference bit per block, cleared periodically
• Evict any block with ref bit = 0
• Used in some TLBs and page tables

Clock Algorithm

• Circular buffer with a hand pointer
• On eviction, scan clockwise, clear ref bits, evict first block with ref=0
• Used in OS page replacement (approximates LRU)

Connections

• 5.4.01-Cache-organizationand-addressing — Replacement policy operates within a set
• 5.4.03-Write-policies-(write-through,-write-back) — Eviction must handle dirty blocks
• 5.4.06-Cache-coherence-protocols — Replacement interacts with coherence state
• 5.5.02-Virtual-memory-and-TLBs — Same replacement concepts apply to TLBs and page tables
• Temporal-and-spatial-locality — LRU exploits temporal locality; FIFO mises it
• Working-set-model — Optimal cache size depends on working set; LRU adapts better
• Cache-conscious-programming — Programmers can optimize for LRU by reusing data inner loops

#flashcards/hardware

What is a cache replacement policy and why is it needed? :: A policy that decides which block to evict when the cache is full and a new block must be loaded. Needed because cache capacity is limited and we must choose which blocks to keep to minimize miss rate.

What is the hardware cost trade-off for LRU? :: LRU requires tracking recency for every access (counters or trees), making it the most expensive policy in terms of hardware complexity.

Concept Map

Hinglish (regional understanding)