A set-associative cache simulator written in C that implements and benchmarks four replacement policies: LRU, LFU, Bélády's OPT, and an online perceptron-based learned policy. Benchmarked on real SPEC CPU 2006 memory traces from the 2nd Cache Replacement Championship (CRC-2).
Every cache replacement policy is solving the same problem: predict which cache line will be reused furthest in the future and evict it. LRU approximates this with recency, LFU with frequency, and Bélády's OPT solves it exactly but requires knowing the future. This project explores whether a machine learning model can approximate OPT at runtime using only information available to the cache controller, with no offline training and no external dependencies.
The same problem appears in LLM inference. Systems like vLLM must decide which KV cache blocks to evict under GPU memory pressure, making this a directly relevant systems ML problem.
| Policy | Type | Eviction Strategy |
|---|---|---|
| LRU | Online | Evict the line accessed longest ago |
| LFU | Online | Evict the line accessed least frequently (LRU tiebreak) |
| OPT | Offline | Evict the line whose next use is furthest in the future |
| ML (Perceptron) | Online | Evict the line with the lowest predicted reuse score |
The cache is configured as 256 sets, 8-way set associative, with 64-byte cache lines, mirroring a realistic last-level cache. A 64-bit address is decomposed into a 6-bit block offset, 8-bit set index, and 50-bit tag via bitmasking.
The perceptron policy scores each candidate line at eviction time using three features: recency, frequency, and a per-PC weight looked up by hashing the instruction pointer that loaded the line. Weights update online after each eviction using a feedback signal from a 64-entry circular eviction history. All weights are clamped to [-128, 127] to simulate saturating hardware counters.
OPT precomputes a next-use array via a backward scan through the full trace using an open-addressing hash table, giving each access the exact future index of its next occurrence.
| Policy | Hit Rate |
|---|---|
| OPT | 80.98% |
| LFU | 69.18% |
| ML | 61.92% |
| LRU | 59.59% |
The perceptron beats LRU by 2.33 points by learning that lines loaded by the scan instruction have low reuse value and should be evicted preferentially.
| Policy | Hit Rate |
|---|---|
| OPT | 93.97% |
| LRU | 91.83% |
| ML | 90.53% |
| LFU | 87.50% |
| Policy | Hit Rate |
|---|---|
| OPT | 79.97% |
| LRU | 75.81% |
| LFU | 74.34% |
| ML | 73.19% |
LFU performs worst on both real traces because graph search and pointer-chasing workloads access data once or twice before moving on, making historical frequency a misleading signal. The ML policy falls below LRU on real traces due to the cold start problem and the irregularity of real program access patterns, a known limitation of simple linear models without richer feature sets.
Requires gcc and Python 3.
# Compile
gcc -Wall -Wextra -O2 -g -o sim src/main.c src/cache.c src/policies.c -lm
# Generate synthetic test trace
python scripts/gen_test_trace.py
# Run
./sim <policy> <trace_file>
./sim lru traces/test.txt
./sim lfu traces/test.txt
./sim opt traces/test.txt
./sim ml traces/test.txtPlaintext, one memory access per line:
<pc_hex> <address_hex> <type>
Where type is 0 for load and 1 for store. Real SPEC CPU traces in ChampSim binary format can be converted using the included script:
python scripts/convert_trace.py <input.trace> <output.txt> <num_accesses>CRC-2 traces: http://bit.ly/2t2nkUj
- Hawkeye (ISCA 2016) Dr. Lin mentioned... https://www.cs.utexas.edu/~lin/papers/isca16.pdf
- RLR (HPCA 2021): http://www.ece.umn.edu/users/jsartori/papers/hpca21.pdf
- PARROT (ICML 2020): http://proceedings.mlr.press/v119/liu20f/liu20f.pdf
- LeCaR (HotStorage 2018): https://www.usenix.org/system/files/conference/hotstorage18/hotstorage18-paper-vietri.pdf
- vLLM PagedAttention (2023): https://arxiv.org/abs/2309.06180