Ever wondered about designing hardware for an LRU replacement policy for an N-way set associative cache? 🤔
Modern-day processors employ multiple levels of caches, with many of these caches being N-way set associative. Since the number of ways in the cache set is limited, it becomes critical to determine the way selected for replacement within the set. One common replacement policy is to choose the Least Recently Used (LRU) way. The LRU scheme keeps track of the relative age order of the ways in the set and selects the oldest (or the last accessed) way for replacement.
While the LRU approach may sound appealing, its hardware implementation can be quite expensive in terms of the necessary components required to accurately track the relative age order. In my hands-on RTL Design course I dive deep into the hardware intricacies of implementing an LRU replacement policy using an age-matrix.
Age Matrix - LRU Replacement Policy
The problem explores the complexities involved in implementing the LRU scheme for an N-way set associative cache, providing you with a deeper understanding of the replacement policy. It presents you with the following interface to implement the LRU policy for an N-way set associative cache:
INPUTS: ls_valid_i → Indicates a valid operation ls_op_i → Operation type: can be either read, write or an invalidation operation ls_way_i → Gives the way information for read and invalidation operation ----------------------------------------------------
OUTPUTS: lru_valid_o → The output way information is valid on this cycle lru_way_o[N-1:0] → The one-hot decoded way for the current operation​ ​ As from the interface above the policy needs to support three operations: read, write and invalidation. This is a fairly challenging problem part of the course and in my opinion it does a great job at the hardware implementation for the LRU scheme. I am confident that after completing the problem, you will appreciate the benefits of using the Pseudo LRU scheme over the traditional LRU scheme!
Well, that's it for this edition of the SiliconNotes.