Introduction
Cache Basics Direct Mapped Cache Direct Mapped Example 1 Direct Mapped Example 2 Direct Mapped Problem 1 Direct Mapped Problem 2 Direct Mapped Problem 3 Direct Mapped Problem 4 Direct Mapped Comparators Direct Mapped Disadvantages Direct Mapped Locality Direct Mapped UVM Example Associative Mapped Cache Associative Mapped Problem 1 Associative Mapped Problem 2 Associative Mapped Problem 3 Associative Mapped Problem 4 Set Associative Mapped Cache Set Associative Mapped Comparators Set Associative Mapped Problem 1 Set Associative Mapped Problem 2 Set Associative Mapped Problem 3 Set Associative Mapped Problem 4 Set Associative Mapped Problem 5 Other Mapping Problem - Example 1 Cache Replacement Algorithms LRU Cache Replacement Algorithm FIFO Cache Replacement Algorithm MRU Cache Replacement Algorithm PLRU Cache Replacement Algorithm Round Robin Cache Replacement Algorithm
UVMArena

Cache Memory Replacement Algorithm – Round Robin

The Round Robin cache replacement algorithm replaces cache blocks in a fixed cyclic order. Each cache line is selected sequentially for replacement, regardless of how recently it was accessed.

A pointer is maintained that indicates which cache line should be replaced next. Whenever a replacement occurs, the pointer moves to the next cache line in the cycle.

Key Idea

  • A replacement pointer cycles through cache lines.
  • When a cache miss occurs and the cache is full, the line pointed to by the pointer is replaced.
  • After replacement, the pointer moves to the next cache line.
  • When the last line is reached, the pointer wraps around to the first line.

Example

Assume a cache with 4 cache lines: 


Cache Lines: L0  L1  L2  L3
Pointer:     ^

If a cache miss occurs:

  • The block in L0 is replaced.
  • The pointer moves to L1.

Next Replacement Order:
L0 → L1 → L2 → L3 → L0 → ...

This replacement order continues cyclically.

Hardware Implementation

Round Robin is simple to implement in hardware. It only requires a small counter or pointer register that increments after each replacement. 


// Example pointer update
pointer = (pointer + 1) % NUM_CACHE_LINES;

This makes Round Robin very efficient for hardware implementations.

Advantages

  • Very simple hardware implementation
  • Low power consumption
  • No need to track access history
  • Predictable replacement behavior

Limitations

  • Does not consider how frequently a block is accessed
  • May replace frequently used data
  • Usually less efficient than LRU-based algorithms

Where Round Robin is Used

Round Robin replacement is commonly used in:

  • Simple cache controllers
  • Some TLB implementations
  • Hardware designs where low complexity is preferred

Comparison with Other Algorithms

  • FIFO replaces the oldest inserted block.
  • LRU replaces the least recently used block.
  • MRU replaces the most recently used block.
  • PLRU approximates LRU using fewer hardware resources.
  • Round Robin replaces blocks sequentially using a pointer.

Key Takeaway

Round Robin is one of the simplest cache replacement algorithms. Although it does not consider memory access patterns, its low hardware cost makes it attractive for systems where simplicity and speed are more important than optimal cache performance.