In this lesson, you will learn how to decide which data to discard from a cache when it becomes full, ensuring your processor keeps the most useful information readily available.
When we use set-associative caches, multiple memory addresses might map to the same "set." If that set is full and we need to load a new piece of data, we must evict an existing entry to make room. The strategy we use to choose the "victim" to evict is called a Replacement Policy.
Two common strategies are:
First-In-First-Out (FIFO)
FIFO treats the cache set like a queue. The item that has been in the cache the longest is the first to be kicked out, regardless of how often it was accessed. While simple to implement with a small counter or pointer, it often performs poorly because it might evict a frequently used variable simply because it was loaded early.
Least Recently Used (LRU)
LRU is based on the principle of temporal locality: if you used an item recently, you are likely to use it again soon. LRU tracks the "age" of entries in a set. Every time a hit occurs, the accessed item is marked as the "most recently used." When we need to evict, we discard the item that has gone the longest without being accessed.
Consider a cache set with two slots (ways). We track them with a single bit:
// Simplified logic for a 2-way set associative cache
if (hit) {
update_usage_bit(accessed_slot); // Mark as most recent
} else {
victim = get_least_recently_used(); // Choose slot based on bits
load_data_into(victim);
update_usage_bit(victim);
}
While LRU is more efficient than FIFO, it requires extra hardware bits to track the access order of each entry in a set. For larger sets, "True LRU" becomes very expensive, leading architects to often use "Pseudo-LRU," which approximates the behavior with fewer bits to balance performance and complexity. By choosing the right policy, we minimize "misses" and prevent the processor from stalling while waiting for slow main memory.
Key Takeaway: Replacement policies like FIFO and LRU determine cache efficiency by deciding which data to discard, with LRU generally providing higher hit rates by prioritizing data that was accessed most recently.