LRU (Least Recently Used) Cache

Qualcomm

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_addr is valid only when req_valid = 1

  • Output Behavior:

    • hit, evict_valid, and evicted_addr are 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:

  1. Check if the data is already in cache

    • βœ… YES β†’ HIT

    • ❌ NO β†’ MISS

  2. If it’s a HIT:

    • Update it as Most Recently Used

  3. 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

clk

Clock signal

rst

Reset (clears cache)

req_valid

Request is valid

req_addr

Requested data


πŸ“€ Outputs

Signal

Description

hit

1 β†’ data found (HIT), 0 β†’ not found (MISS)

evict_valid

1 β†’ eviction happened

evicted_addr

The data that was removed


πŸ”„ Behavior Summary

Condition

Action

Data found

hit = 1, update usage

Data not found

hit = 0, insert new

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 = A

Verilog

Code Editor Access

Log in to write, run and submit your solution to this interview question. It's free.

Output

Output goes here...