6.2.9. Block Replacement Policy

As we did in the example as we saw in the example that when for example, in a 2 way set associative cache, I will just go back to this example once. In the 2 way set associative cache consider this 6 here. Before this 6 was accessed set 0, the 2 lines of set 0 contain memory block number 0 and block number 8.

In this introduction to block replacement policy, we focus on what happens when a new memory block needs to be stored in a cache. In the context of a 2-way set associative cache, when we want to access memory block number 6, we first check which lines in the designated set are available for this block. Initially, set 0 has memory blocks 0 and 8. Before adding block 6, a decision must be made about which existing block to replace, if both lines are occupied.

Think of a 2-way set associative cache like a closet with two shelves (lines). If you want to add one more shirt (memory block), but both shelves are already occupied, you have to decide which shirt to remove. Your closet represents the cache, and your shirts represent the memory blocks stored in it.

Now when 6 was brought in I replaced, this memory block number 8 in line one of set number 0 and put 6 in it. So, we at that time I said that I replaced this memory block number 8 arbitrarily. But what is the algorithm that I used? For replacing memory block number 6, memory block number 8 with memory block number 6.

The processes by which a cache decides which block to evict when a new block needs to be stored are governed by replacement algorithms. In our case, we chose to replace block 8, but which policy did we use? A common technique is the 'Least Recently Used' (LRU) policy, which replaces the block that has not been accessed for the longest time. Understanding how these algorithms work is crucial for optimizing cache efficiency.

Imagine you have a small refrigerator that can hold only two items. If you want to add a new item but both shelves are full, you would likely want to remove the food item that has been left untouched for the longest time. This represents the LRU algorithm in action—removing what hasn't been used recently.

In a direct mapped cache, I have no policy. I need there is no choice shown hence no policy.

In a direct mapped cache, each block of memory can only be placed in one specific location in the cache. This means that when a block is accessed and leads to a miss, it simply replaces whatever is currently stored in that one specific cache line, leading to a situation where there is no algorithm or choice involved in the replacement process. It’s more rigid and deterministic than other cache strategies.

Imagine a parking lot where only one car can park in each designated space. If that space is occupied when another car arrives, that car must replace the one currently parked there, regardless of how long the parked car has been there. This simplistic model illustrates the direct mapped cache.

In a set associative cache, we first prefer non-valid entries. So, if I have a non-valid entry, I will if I have a non-valid entry I will directly use that and replace that because, any way that cache location that cache line contains non-valid data, so I will replace it.

Set associative caches provide more flexibility by allowing multiple blocks to occupy a specific set of lines. When a new block is needed, if any of the lines in the set are non-valid (i.e., they have never stored a block), the cache will replace that entry instead of evicting an existing valid block. This greatly reduces the need for complex algorithms and minimizes misses.

Think of a shared workspace with several desks (lines) available for team members (memory blocks). If a desk is open (non-valid), a member can simply take that desk instead of having to push someone else out or find out who hasn’t been working there for a while. This promotes efficiency!

The policy that is typically used is least recently used. So, what is least recently used policy? Choose the line which was unused for the longest time.

Least Recently Used (LRU) is a well-known cache replacement policy where the line that has been unused for the longest time is selected for replacement when a new block must be added. This strategy is based on the assumption that if a block has not been used for a while, it is less likely to be used in the near future, thus making it a good candidate for eviction.

Consider a library where members can borrow books. If all the shelves are full and someone wants to borrow a new book, they might choose to return the book that hasn’t been checked out the longest. This ensures that the library retains books that are still in demand, similar to how LRU optimizes cache performance.

The other option is to choose randomly. Least recently used is typically mostly used random has some advantages we will look at later.

While the Least Recently Used (LRU) policy is widely favored, random replacement can also be employed. In this strategy, when a cache line needs to be replaced, a random valid block is chosen. This simplicity can sometimes outperform complex strategies, especially in certain access patterns, and avoids the overhead of keeping track of usage time for each cache line.

Imagine a game where you randomly pick which toy to give away to make room for a new one. Sometimes, randomness can lead to surprising decisions that keep playtime fresh. In cache management, this randomness can sometimes lead to unexpected but effective outcomes.

--