Implement LRU Eviction Policy for Cache Replacement

Topic Overview

Replacement Policies

When a cache set is full and a new tag arrives, a replacement policy picks the victim line. LRU (Least Recently Used) evicts the line untouched longest. It approximates temporal locality well though real hardware often uses pseudo-LRU trees for speed.

cCopy
Loading…

Implementing LRU

• Counter LRU: stamp each way with access time
• Stack LRU: linked list per set (true order, more logic)
• Clock: single bit per line, good enough for many L2 caches

For example, accessing ways A, B, A in a 2-way set leaves B as LRU; the next conflicting miss evicts B.

For this exercise, you will add LRU tracking to your set-associative simulator. This task asks you to log victim way indices and verify LRU order on a scripted access sequence before benchmarking realistic traces.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.

Your Task

Compare three cache replacement policies on the same trace of block numbers. LRU evicts the block unused for the longest time, tracked with per-way counters. FIFO evicts the block that was brought in first, whether or not it has been used since. Random evicts a pseudo-random way. Print the LRU recency order after every access, then the hit/miss pattern of each policy.

Input

cCopy
Loading…

Block B maps to set B mod S. The cache starts empty, and each policy runs the trace on its own fresh cache.

Policies

On a hit, nothing is evicted. On a miss, the block goes into the lowest-numbered empty way if the set has one. Otherwise a victim is chosen:

• LRU: every access sets the accessed way's counter to the current access number (1, 2, 3, …). The victim is the way with the smallest counter.
• FIFO: each way records the access number at which its block was inserted. Hits don't change it. The victim is the smallest insertion number.
• Random: x = (x · 1103515245 + 12345) mod 2^31, starting from x = seed. The victim is way (x >> 16) mod W. The generator advances only when a victim is needed.

Output

cCopy
Loading…

• The trace has one line per access. order lists the set's blocks from most to least recently used, after the access.
• The pattern string has one H or M per access.
• best names the policy with the most hits. On a tie, the earlier in the order LRU, FIFO, Random wins.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. One cache simulator parameterised by policy; the policy only decides the victim and what to update on a hit.
2. Implement the random generator exactly as specified so results are reproducible.

Hidden tests cover a looping trace one block larger than a set (where LRU gets zero hits and Random does better), and a trace with a hot block that FIFO keeps evicting.