Cache Memory Replacement Algorithms

Why Replacement Algorithms Are Needed

Cache memory is much smaller than main memory, so it can only store a limited number of memory blocks.

When the CPU requests data that is not present in the cache (a cache miss), the block must be fetched from RAM. If the cache still has empty lines available, the new block can simply be placed there.

However, when all cache lines are already occupied, the cache must remove an existing block to make room for the new one. The rule used to determine which block should be removed is called a cache replacement algorithm.

Example Scenario

Assume a cache with 8 lines and a much larger RAM.

• The CPU requests a memory block.
• The block is not present in cache (cache miss).
• All cache lines are already occupied.

The cache must choose one line to evict so that the new block can be inserted.

Common Cache Replacement Algorithms

• First-In First-Out (FIFO)
• Least Recently Used (LRU)
• Most Recently Used (MRU)
• Pseudo Least Recently Used (PLRU)
• Round Robin

1. First-In First-Out (FIFO)

FIFO replaces the block that entered the cache first.

Replace the cache block that was inserted first.

Although simple, FIFO can remove blocks that are still heavily used.

2. Most Recently Used (MRU)

MRU replaces the block that was accessed most recently.

Access order:

Line0 → Line2 → Line5 → Line6 → Line7 → Line3 → Line4

In this case, Line4 is the most recently used, so MRU would replace it.

3. Least Recently Used (LRU)

LRU replaces the block that has not been used for the longest time.

Access order:

Line0 → Line2 → Line5 → Line6 → Line7 → Line3 → Line4

The least recently used line is Line0, so it would be replaced.

LRU usually gives excellent cache performance but requires more hardware to track the access order of each line.

4. Pseudo Least Recently Used (PLRU)

PLRU approximates LRU while being much easier to implement in hardware.

Instead of tracking exact access order, PLRU uses a small number of bits to estimate which cache line is least recently used.

Example: Tree-based PLRU for 4-way cache

        b0
       /  \
     b1    b2
    / \   / \
   L0 L1 L2 L3

• Each bit indicates which subtree was less recently used.
• When a line is accessed, bits along the path are updated.
• When replacement is needed, the tree is traversed to select the victim.

PLRU is widely used in modern processors because it balances performance and hardware complexity.

5. Round Robin Replacement

Round Robin replaces cache lines in a fixed cyclic order.

The cache maintains a pointer that moves sequentially through the ways of a set.

Example for a 4-way set associative cache:

Way0 → Way1 → Way2 → Way3 → Way0 → Way1 → ...

Each time a replacement is required, the pointer selects the next cache line.

Hardware Implementation

Round Robin is extremely simple to implement in hardware. It only requires a small counter.

logic [1:0] rr_pointer;

always_ff @(posedge clk) begin
    if(replace_event)
        rr_pointer <= rr_pointer + 1;
end

The pointer indicates which way should be replaced next.

Round Robin is commonly used in:

• TLBs
• Small associative buffers
• Simple hardware structures where low complexity is important

Replacement Algorithms and Cache Mapping