LC

Implement LRU Eviction Policy for Cache Replacement

hard4/9

Implement Set-Associative Cache (2-way, 4-way)Demonstrate False Sharing and Cache Coherency Overhead

Language

Compiler

2.0s Limit 256MB

Implementation

Implement LRU eviction policy for set-associative cache.

Requirements:

Implement true LRU with counter-based approach
Track access order per set
Update LRU on hits and misses
Evict least recently used on miss
Compare LRU vs FIFO vs Random
Show hit rate differences
Demonstrate LRU state after each access

Why This Matters

True LRU, pseudo-LRU trees, and simpler bit-based approximations are exactly the design space real cache controllers navigate: Intel L1 caches use true LRU because 8-way tracking is cheap, while ARM and AMD L2/L3 caches use tree-based pseudo-LRU because tracking exact order across 16+ ways would be too costly in hardware. The 10-15% hit-rate gap between LRU and random eviction you measure here is a real, measurable performance difference in production CPUs.

Hints

0 / 3 revealed

Validation Suite

main.c

Workspace 1.0