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 – PLRU (Pseudo Least Recently Used)

The Pseudo Least Recently Used (PLRU) algorithm is a hardware-efficient approximation of the Least Recently Used (LRU) cache replacement policy.

Implementing true LRU in hardware becomes expensive when the cache has many ways, because the system must track the exact usage order of every cache line. PLRU reduces this complexity while still providing behavior similar to LRU.

Why PLRU is Used

  • True LRU requires tracking exact access order.
  • Hardware complexity increases quickly as cache associativity grows.
  • PLRU approximates LRU with much fewer bits.
  • Widely used in modern CPUs for set-associative caches.

Basic Idea

PLRU uses a small number of direction bits arranged in a binary tree structure. These bits help determine which cache line was likely used least recently.

For a 4-way set associative cache, the PLRU tree looks like this: 


        b0
       /  \
     b1    b2
    / \   / \
   L0 L1 L2 L3
  • L0–L3 represent cache lines.
  • b0, b1, b2 are PLRU control bits.
  • Each bit indicates which subtree was used more recently.

How Replacement Works

When a cache miss occurs and replacement is required:

  1. Start from the root of the PLRU tree.
  2. Follow the direction indicated by the bits.
  3. Traverse the tree until reaching a leaf node.
  4. The leaf node corresponds to the cache line that will be replaced.

Example traversal:

b0 = 0 → go left
b1 = 1 → go right

Victim = L1

Updating the PLRU Bits

Whenever a cache line is accessed:

  • The PLRU bits along the path to that cache line are updated.
  • The bits indicate that this path was recently used.
  • This makes other paths more likely candidates for replacement.

Access L2

Update path bits:
b0 = 1
b2 = 0

Advantages of PLRU

  • Much simpler hardware than true LRU
  • Requires fewer tracking bits
  • Fast decision making for replacement
  • Works well for high-associativity caches

Limitations

  • PLRU is only an approximation of LRU.
  • It may not always select the true least recently used block.
  • Performance depends on the memory access pattern.

Where PLRU is Used

PLRU is commonly used in:

  • CPU L1 and L2 caches
  • Set-associative cache designs
  • Modern processor cache controllers

Because it offers a good balance between performance and hardware complexity, PLRU is one of the most widely used replacement policies in real processor implementations.