Cache Replacement Policies

A cache is organized into sets, each holding a fixed number of ways (blocks) — this is exactly the associativity discussed for Set-Associative Caches. On a miss, the requested block must be loaded into some way of its set. If every way in that set already holds valid data, one resident block must be evicted to make room. The rule that chooses the victim is the replacement policy. The theoretical ideal is Belady's optimal algorithm (MIN): evict the block whose next reference lies furthest in the future, or is never referenced again. Belady's algorithm provably minimizes the number of misses for a given cache size and associativity, but it requires knowing the future reference stream — impossible in real hardware operating on a running program. Every practical policy is therefore a heuristic that tries to approximate MIN using only information about the past: recency of use, order of insertion, or nothing at all. The three canonical heuristics differ in what past information they track and how much it costs to maintain:

• LRU (Least Recently Used) assumes that a block not accessed in a long time is unlikely to be accessed again soon — an appeal to temporal locality. It requires ordering all ways in a set by time-of-last-use.
• FIFO (First-In-First-Out) assumes only that older residents are more expendable than newer ones, ignoring whether a block was used after being installed. It requires only an insertion timestamp or a rotating pointer.
• Random makes no assumption at all; it picks a way uniformly (or pseudo-uniformly) at random. It requires essentially no per-set state beyond a global pseudo-random number source.

The key design tension is this: the more information a policy uses about access history, the better it can approximate MIN — but the more state and update logic it requires per set, on every access, not just every miss. LRU must be updated on every hit (to keep recency order current), which is what makes it expensive; FIFO and Random only need bookkeeping on eviction, which is much cheaper.

True LRU conceptually keeps, for each set, a full ordering of the n ways from most-recently-used to least-recently-used. On every access (hit or fill) to way w, w moves to the "most recently used" end; on a miss requiring eviction, the way at the "least recently used" end is chosen. There are two standard hardware realizations: 1. Counter-based LRU. Each way has a $\lceil \log_2 n \rceil$-bit counter recording its rank. On an access to way $w$ with old counter value $c_w$: every way whose counter is less than $c_w$ is incremented by 1, and $w$'s counter is set to 0 (most recent). The way with counter value $n-1$ is the LRU victim. 2. Matrix (pairwise) LRU. Maintain an $n \times n$ bit matrix $M$ where $M[i][j] = 1$ means "way $i$ was used more recently than way $j$." On an access to way $i$: set row $i$ to all 1s and column $i$ to all 0s. The LRU way is the one whose row is all 0s (never more recent than anything still valid). Both realizations are exact LRU but scale as $O(n^2)$ bits or $O(n)$ comparator work per access, which is why true LRU is common only for 2-way to 8-way caches. Beyond that, hardware uses approximations:

• Pseudo-LRU (PLRU), tree-based. Use a binary tree of $n-1$ bits over $n$ ways. Each bit indicates which half of the subtree was not most recently used. On access, flip the bits along the path to point away from the accessed way. On eviction, walk the tree following the "not recently used" bits to a leaf. This costs only $n - 1$ bits and $O(\log n)$ update work — dramatically cheaper than exact LRU's $O(n^2)$, at the cost of occasionally evicting a not-quite-LRU block.
• NRU / Clock (1-bit approximation). Each way has one "referenced" bit, set on access. On eviction, scan (or use a rotating pointer) for a way with bit = 0, clearing bits to 0 as you pass over ways with bit = 1 (like the OS clock/second-chance page algorithm). This is the cheapest useful approximation: 1 bit per way.

FIFO needs only a small per-set pointer (or per-way insertion-order field) recording which way was filled longest ago; it advances on fills only, never on hits, so it is far cheaper to update than LRU.

Random needs a pseudo-random number generator (often a small linear-feedback shift register, LFSR, shared across many sets) to pick a way index modulo the associativity; no per-set state at all is required. ``` // Generic replacement-policy interface, invoked on every memory access function ACCESS(set, tag): way = FIND_WAY(set, tag) // -1 if miss if way != -1: HIT_UPDATE(set, way) // policy-specific bookkeeping on a hit return HIT else: victim = CHOOSE_VICTIM(set) // policy-specific victim selection INSTALL(set, victim, tag) // evict victim, load new block FILL_UPDATE(set, victim) // policy-specific bookkeeping on a fill return MISS // --- LRU (counter-based), n ways per set --- function HIT_UPDATE_LRU(set, way): old = counter[set][way] for w in 0..n-1: if counter[set][w] < old: counter[set][w] += 1 counter[set][way] = 0 // mark most recently used function CHOOSE_VICTIM_LRU(set): return argmax_w counter[set][w] // counter == n-1 identifies LRU way function FILL_UPDATE_LRU(set, way): HIT_UPDATE_LRU(set, way) // installing counts as "just used" // --- FIFO --- function CHOOSE_VICTIM_FIFO(set): return ptr[set] // pointer marks oldest-filled way function FILL_UPDATE_FIFO(set, way): ptr[set] = (ptr[set] + 1) mod n // advance only on a fill, never on a hit function HIT_UPDATE_FIFO(set, way): return // no-op: FIFO ignores hits entirely // --- Random --- function CHOOSE_VICTIM_RANDOM(set): return LFSR_NEXT() mod n // cheap pseudo-random index function HIT_UPDATE_RANDOM(set, way): return // no state to maintain at all // --- Pseudo-LRU (binary-tree approximation), n = 2^k ways --- function HIT_UPDATE_PLRU(set, way): node = root(set) for bit in path_bits(way, k): // bits of way's index, MSB first setDirection(node, bit) // point tree bit AWAY from this half node = child(node, bit) function CHOOSE_VICTIM_PLRU(set): node = root(set) for level in 1..k: bit = treeBit(node) // follow "not recently used" direction node = child(node, bit) return leafToWay(node) ``` The figure below shows a 4-way set under LRU, FIFO, and Random side by side, so the different bookkeeping each policy needs is visible directly.

State cost per set (associativity $n$):

• Exact LRU (counter form): $n \cdot \lceil \log_2 n \rceil$ bits, e.g. 8 bits for 4 ways, 24 bits for 8 ways.
• Exact LRU (matrix form): $\binom{n}{2}$ bits, e.g. 6 bits for 4 ways, 28 bits for 8 ways — grows as $O(n^2)$.
• Pseudo-LRU (tree): $n-1$ bits, e.g. 3 bits for 4 ways, 7 bits for 8 ways — linear in $n$.
• FIFO: $\lceil \log_2 n \rceil$ bits per set (one pointer), independent of how many bits track which way beyond identifying the oldest.
• Random: effectively 0 bits per set; a global LFSR is amortized across the whole cache.

Update time per access:

• Exact LRU (counter form) must compare and possibly increment all $n$ counters on every hit and every fill: $O(n)$ work per access, all of it on the critical path if the update must complete before the next access to that set.
• Exact LRU (matrix form) touches a row and column: $O(n)$ bit writes, but can be done with wide combinational logic in parallel, effectively $O(1)$ latency for small $n$ at the cost of $O(n^2)$ area.
• Pseudo-LRU touches $\log_2 n$ tree bits per access: $O(\log n)$ time and space, which is why it dominates practical designs above 4–8 ways (e.g., many 8-way and 16-way last-level caches use tree-PLRU).
• FIFO and Random touch $O(1)$ state per access (FIFO only on fills; Random needs no update at all beyond advancing the shared LFSR).

Why LRU tends to work well. LRU is a direct hardware embodiment of the stack property: for a sequence of accesses, if you sort the working set by recency, the probability that the next access falls within the $k$ most-recently-used items is high whenever the program exhibits temporal locality (loops, repeated calls, hot data structures). Formally, LRU is optimal within the class of "stack" replacement algorithms under Belady's stack-property framework, meaning that a cache of size $k$ under LRU is guaranteed to contain a superset of the blocks a cache of size $k' < k$ would contain, for the same reference string. This guarantees LRU is free of Belady's anomaly — increasing cache size can never increase the miss count under LRU, unlike under FIFO, where it famously can.

Why LRU can still lose to Random or FIFO. LRU's guarantee applies to reference strings whose future resembles their past. Certain access patterns are adversarial to recency-based reasoning: a sequential scan larger than the cache (e.g., iterating over an array bigger than the whole cache) causes LRU to evict exactly the block that will be needed next, achieving essentially a 0% hit rate, while Random, by chance, retains some useful blocks. This is the classic weakness exploited by scan-resistant designs. More subtly, at high associativity (e.g., 16-way) the marginal benefit of exact recency tracking over a good pseudo-random or pseudo-LRU choice shrinks, because with many ways the "wrong" eviction rarely removes a block about to be reused — empirically, Random and PLRU trail true LRU by well under 1% miss rate at 8-way and above, while costing a small fraction of the hardware.

FIFO's correctness caveat — Belady's anomaly. Unlike LRU, FIFO does not obey the stack property. There exist reference strings for which a larger FIFO cache produces more misses than a smaller one — Belady's original counterexample used exactly this policy. This means FIFO's behavior is not monotünically well-behaved as capacity grows, a real theoretical wart, even though in practice its average-case behavior on typical workloads is only modestly worse than LRU.

Random's correctness argument. Random offers no worst-case guarantee at all — it can, with vanishingly small probability, evict the most-reused block repeatedly — but its expected behavior can be analyzed: for a uniformly random victim among $n$ ways, each resident block survives an eviction round with probability $1 - 1/n$, giving an expected residency (in rounds) of $n$, independent of access history. This history-independence is exactly what makes Random immune to adversarial and scan-heavy patterns that defeat LRU, at the price of giving up the ability to exploit genuine temporal locality when it is present.

Bottom line trade-off table (informal):

Consider a 2-way set-associative cache set with capacity for 2 blocks, and the reference stream of block addresses:

We trace LRU, FIFO, and Random (assume Random happens to always evict the way holding the block that was installed first, to make the trace concrete and comparable — call this "Random-instance").

Reading the table carefully: all three policies produce the same eviction sequence on this particular short trace, and all get exactly one hit (step 3) out of seven references. This is intentional — it shows that for short or simple traces the policies frequently agree, and differences only emerge over longer traces or working sets that exceed capacity. Let's extend the trace to expose a real divergence, appending a repeating loop over three blocks in a 2-way set — a classic case where LRU is worse than Random:

With only 2 ways and 3 distinct blocks accessed cyclically, LRU evicts exactly the block needed next on every single reference after the set fills — a 0% steady-state hit rate, because whichever block was used least recently is, by the cyclic pattern, the very next one requested. FIFO behaves identically here (it also evicts in a fixed rotating order). Random, however, occasionally happens to keep the right block by chance, giving a small but nonzero expected hit rate above 0% — a concrete demonstration that recency-based reasoning is not universally superior, and that Random's history-independence has a genuine, provable use case (the classic "cyclic reference string longer than cache" pathology).

Every processor with a set-associative cache — L1, L2, and last-level caches in essentially all commercial CPUs and many GPUs — implements some version of these policies at every level of the Set-Associative Caches hierarchy. Real designs almost always choose an approximation: many commercial 8-way and 16-way last-level caches use tree-based pseudo-LRU or NRU-style bits rather than exact LRU, because exact LRU's $O(n^2)$ state and update logic become prohibitive at high associativity. Translation Lookaside Buffers (TLBs), themselves small associative caches for address translations, use the same family of policies at a much smaller scale. Operating-system page replacement for virtual memory is the software-side twin of this problem, using clock/NRU algorithms directly descended from the hardware ideas discussed here. Beyond CPUs, content delivery networks, database buffer pools, and key-value stores such as web caches all implement software analogs of LRU, FIFO, or randomized eviction, facing exactly the same state-versus-accuracy tradeoff at a much coarser granularity. Understanding replacement policy behavior is also the natural bridge to Cache Misses: The Three Cs, since a poor replacement policy manifests specifically as extra conflict misses, and to Cache Write Policies, where the choice of victim interacts with whether dirty data must be written back before eviction.

Ask the tutor: How would the choice of replacement policy change if the cache were fully associative instead of set-associative?