Managing Cache Replacement Algorithms

In this lesson, you will learn how to decide which data to discard from your cache when it gets full, comparing the precision of Least Recently Used (LRU) against the efficiency of Pseudo-LRU.

The Cache Eviction Dilemma

When your set-associative cache is full and you need to bring in new data, you must evict an existing block. Because we want to exploit temporal locality—the principle that data used recently is likely to be used again soon—we want to evict the block that hasn't been touched for the longest time.

Least Recently Used (LRU)

True LRU tracks the access history of every block in a set. If a set has $N$ ways (blocks), the hardware must maintain a "recency stack." Every time you access a block, you must update the stack to promote that block to "Most Recently Used" and demote others.

While accurate, true LRU is expensive. As the associativity ($N$) increases, the logic required to track the age of every block grows quadratically, consuming significant area and power in your silicon.

Pseudo-LRU (PLRU)

To solve the complexity problem, many systems use Pseudo-LRU. Instead of tracking the exact order of every access, PLRU uses a tree of "replacement bits" to track which half of the cache was accessed more recently.

Imagine a 4-way associative cache. Instead of a full ranking, you only need 3 bits to point to the "least recently used" quadrant:

• Bit 0: Points to the left or right side (the older half).
• Bits 1 & 2: Point to the older block within those halves.

// Simplified logic concept for 4-way PLRU
if (access_way_0) { tree_bits = 0b110; } // Update path to point away from way 0
else if (access_way_1) { tree_bits = 0b101; } 
// The hardware just follows the '0' bits to find the victim

Which to Select?

• Use LRU if your cache associativity is small (e.g., 2-way or 4-way) and precision is critical for your workload.
• Use PLRU if your associativity is high (e.g., 8-way or 16-way). PLRU is significantly more efficient because it requires fewer bits to store state and much simpler combinational logic to update, saving power without a catastrophic drop in hit rates.

Key Takeaway: While LRU offers the theoretically perfect eviction strategy, Pseudo-LRU is the industry standard for high-associativity caches due to its significantly lower hardware overhead and negligible impact on performance.