Introduction
When it comes to CPU performance, one of the key players behind the scenes is the cache replacement policy. These algorithms determine what data stays in the cache and what gets evicted, directly influencing system speed and responsiveness.
In this guide, we’ll break down the most common cache replacement algorithms, explain how they work, and compare them. Whether you're a computer science student, hardware enthusiast, or tech blogger, this article will help you better understand how cache memory replacement strategies work in modern systems.
What Is a Cache Replacement Policy?
A cache replacement policy is a strategy used to determine which data to remove from the cache when it becomes full. The decision process is essential in maintaining efficient CPU cache memory management and reducing cache miss rates.
Common Cache Replacement Algorithms
1. Least Recently Used (LRU)
Least Recently Used (LRU) is one of the most widely used and intuitive cache replacement policies. It operates on a simple idea: the data that hasn’t been accessed for the longest time is evicted first.
- Tracks the order of data access
- Evicts the “oldest” (least recently accessed) item
- Requires maintaining access order for each cache set
Modern CPUs often approximate full LRU due to hardware complexity. A full LRU in a 4-way set-associative cache requires 5 bits per set to track all 24 (4!) permutations.
2. Tree-Based Pseudo-LRU (pLRU)
Pseudo-LRU provides a lightweight approximation of LRU using a binary tree structure. It uses fewer bits and is faster to update, making it ideal for L1 caches.
- Each node in the tree is a bit indicating recent usage
- Number of bits needed = (ways - 1) per set
- Efficient and widely used in modern processors
3. Least Frequently Used (LFU)
The LFU algorithm evicts the data that has been used the least number of times.
- Tracks usage frequency with counters
- Evicts cache line with the lowest count
- Rarely used in hardware due to overhead
4. First-In-First-Out (FIFO)
FIFO cache algorithm removes the oldest data (the one loaded first), regardless of how often or recently it’s been used.
- Very simple to implement
- No consideration of usage patterns
- Can lead to suboptimal performance
5. Most Recently Used (MRU)
MRU is the opposite of LRU it evicts the most recently accessed data. This strategy can be effective in scenarios with repeated access to older data.
6. Random Replacement
The random replacement cache algorithm selects any cache line at random for eviction. It’s efficient and useful when access patterns are unpredictable.
- Minimal overhead
- Simple implementation
- Sometimes used in L2 or L3 caches for simplicity
7. Not Recently Used (NRU)
NRU Cache Algorithm uses a single bit per cache line to track whether it was used recently. It’s simpler than full LRU but still captures usage patterns.
- Bit = 0 → Recently used
- Bit = 1 → Not recently used
- On cache miss, evict a line with bit = 1
8. Quad-age LRU (QLRU)
Quad-age LRU is useful in high-associativity caches like L3, where each cache line is assigned a 2-bit age value from 0 to 3 to track how recently it was used.
- Age increases as data becomes older
- Evicts line with age = 3
- Efficient balance between precision and overhead
9. Adaptive Replacement Cache (ARC)
Adaptive replacement policies switch between strategies like LRU and LFU based on observed hit/miss rates.
- Monitors cache behavior dynamically
- Adjusts policy for each cache set
- Intel CPUs sometimes use adaptive variants in L3
Comparison Table of Cache Replacement Policies
| Algorithm | Tracks | Overhead | Used In | Ideal For | |
|---|---|---|---|---|---|
| 1 | LRU | Access order | High | L2, L3 | Recency-based patterns |
| 2 | Pseudo-LRU | Approx. access order | Low | L1 | Fast lookups |
| 3 | LFU | Access frequency | Very High | Rare in hardware | Stable access patterns |
| 4 | FIFO | Load order | Very Low | Simple systems | Predictable loads |
| 5 | MRU | Recent use | Low | Special workloads | Large repetitive files |
| 6 | Random | None | Minimal | L2, L3 | Unpredictable access |
| 7 | NRU | Recent usage bit | Low | Simple caches | Basic recency tracking |
| 8 | QLRU | Relative age | Moderate | L3 | High associativity |
| 9 | ARC | Recency + frequency | High | Advanced L3 caches | Dynamic behavior |
Suggested Diagram
To enhance this article visually, consider adding a diagram illustrating:
- The structure of a cache set
- Access tracking using LRU and pLRU trees
- Comparison of hit/miss scenarios for each policy
Final Thoughts
Understanding cache replacement policies is crucial for anyone looking to dive deeper into CPU cache architecture and performance tuning. Each algorithm offers trade-offs between accuracy, speed, and hardware cost.
From Least Recently Used to adaptive hybrid models, the right cache eviction strategy depends on workload patterns, system architecture, and performance goals.
Now that you know how these policies work under the hood, you’re better equipped to explore deeper into memory systems and processor design.