LRU (Least Recently Used) Cache

Problem Description
RU (Least Recently Used) is a method used when memory is limited.
What it does?
Remove the data that was used the longest time ago
π± Real-Life Example
Think of your phone apps:
Recently used apps stay active β‘
Apps not used for a long time get closed β
π Thatβs LRU behavior
To undertand in detail refer the following video
π― Step 2: What is This Problem About?
You are designing a hardware cache system (a small fast memory).
This cache:
Stores only a limited number of entries
Receives requests every clock cycle
βοΈ Design Specifications
Clock: All operations happen on posedge clk
Reset: Asynchronous, Active HIGH
Input:
req_addris valid only whenreq_valid = 1
Output Behavior:
hit,evict_valid, andevicted_addrare updated in the same clock cycle
Cache Policy:
Most Recently Used (MRU) at index 0
Least Recently Used (LRU) at last index
Initial Condition:
Cache is empty after reset
For every incoming request:
Check if the data is already in cache
β YES β HIT
β NO β MISS
If itβs a HIT:
Update it as Most Recently Used
If itβs a MISS:
Insert it into cache
If cache is full:
β Remove (evict) the Least Recently Used entry
π§© Step 3: What You Need to Implement
You must design a module that:
π₯ Inputs
Signal | Description |
|---|---|
| Clock signal |
| Reset (clears cache) |
| Request is valid |
| Requested data |
π€ Outputs
Signal | Description |
|---|---|
| 1 β data found (HIT), 0 β not found (MISS) |
| 1 β eviction happened |
| The data that was removed |
π Behavior Summary
Condition | Action |
|---|---|
Data found |
|
Data not found |
|
Cache full + new data | Evict LRU entry |
π§ͺ Step 4: Example (Easy to Understand)
Cache Size = 4
βΆοΈ Input Sequence
A β B β C β D β B β Eπ Step-by-Step
Step | Request | Hit/Miss | Evicted | Cache (MRU β LRU) |
|---|---|---|---|---|
1 | A | Miss | - | A |
2 | B | Miss | - | B, A |
3 | C | Miss | - | C, B, A |
4 | D | Miss | - | D, C, B, A |
5 | B | β Hit | - | B, D, C, A |
6 | E | β Miss | A | E, B, D, C |
π Final Step Output (for request = E)
hit = 0
evict_valid = 1
evicted_addr = AVerilog
Code Editor Access
Log in to write, run and submit your solution to this interview question. It's free.
