Architecture
LRU (Least Recently Used)
A cache replacement policy that evicts the cache line accessed longest ago.
Detailed Explanation
LRU exploits temporal locality—recently accessed data is likely to be accessed again. When a cache set is full and a new line must be loaded, LRU evicts the line with the oldest access timestamp.
True LRU requires tracking access order among all ways—for N ways, this needs log2(N!) bits per set, impractical for high associativity. Pseudo-LRU approximations (tree-based, MRU bits) reduce overhead while maintaining most LRU benefit.
Code Example
systemverilog
// LRU age matrix update - when way i is accessed
// Set row i to all 1s (younger than everyone)
// Set column i to all 0s (everyone else older than i)
always_ff @(posedge clk) begin
if (access_valid) begin
for (int j = 0; j < N_WAYS; j++) begin
age_matrix[access_way][j] <= (j != access_way);
age_matrix[j][access_way] <= 1'b0;
end
end
end
// LRU way is the one with all zeros in its row
assign lru_way = /* way where age_matrix[way] == 0 */;