Cache Simulator

A CPU cache simulator written in C. It models a configurable N-way set-associative cache with LRU replacement, replays a memory access trace through it, and reports hit rate, miss rate, and eviction counts.

It's a from-scratch implementation of the memory-hierarchy model covered in a typical Computer Architecture course: splitting a memory address into tag/index/offset via bit manipulation, modeling cache lines and sets as structs, and implementing an LRU replacement policy.

Build

make

Produces two binaries: cachesim (the simulator) and gen_trace (a synthetic trace generator).

Generate a trace

make traces/demo.trace
# or directly:
./gen_trace -n 20000 -o traces/demo.trace [-s <seed>]

The generator mixes three access patterns to produce realistic locality: sequential runs over a few "array" base addresses, strided walks (weaker spatial locality, useful for showing block-size effects), and bursts that repeatedly hit a small pool of "hot" addresses (temporal locality). The default seed is fixed, so the demo trace is reproducible.

Run the simulator

./cachesim --size 32768 --block 64 --assoc 4 --trace traces/demo.trace

Cache Simulator
Config: size=32768B block=64B assoc=4 sets=128

Accesses:  20000
Hits:      19795
Misses:    205
Hit Rate:  98.97%
Evictions: 172

Pass --quiet to get a single CSV line instead (size,block,assoc,sets, accesses,hits,misses,hitrate,evictions) for scripting.

All four flags (--size, --block, --assoc, --trace) are required. --block and --assoc must be powers of two, and --size must be evenly divisible by block * assoc.

Compare configurations

make compare

Runs the simulator across a sweep of associativities and block sizes against the same trace and prints comparison tables — this is the "how much does cache design actually matter" result:

== Varying associativity (size=32768 block=64, trace=traces/demo.trace) ==
Assoc    Sets     Accesses   Hits     Misses   HitRate
1        512      20000      16347    3653     81.73  %
2        256      20000      18144    1856     90.72  %
4        128      20000      19795    205      98.97  %
8        64       20000      19795    205      98.97  %

== Varying block size (size=32768 assoc=4, trace=traces/demo.trace) ==
Block    Sets     Accesses   Hits     Misses   HitRate
16       512      20000      19328    672      96.64  %
32       256      20000      19619    381      98.09  %
64       128      20000      19795    205      98.97  %
128      64       20000      19894    106      99.47  %

Going from direct-mapped to 4-way set-associative (same total size, same block size) took hit rate from 81.73% to 98.97% on this trace — the associativity sweep here also doubles as a correctness check: hit rate is provably non-decreasing as associativity increases at fixed total size (a well-known property of LRU/stack-based replacement), so a decrease would indicate a bug in eviction logic.

Design notes

Address decomposition. Given size, block, and assoc:

num_lines   = size / block
num_sets    = num_lines / assoc
offset_bits = log2(block)
index_bits  = log2(num_sets)

offset = addr & ((1 << offset_bits) - 1)
index  = (addr >> offset_bits) & ((1 << index_bits) - 1)
tag    = addr >> (offset_bits + index_bits)

block and assoc must be powers of two, and log2 is computed with a manual shift loop rather than <math.h> to keep the bit math explicit.

LRU via timestamp. Each cache line stores a last_used value taken from a single global counter that increments on every access. A miss evicts the line in the target set with the smallest last_used. This is O(assoc) per access — for the small associativities modeled here (≤ 8), that's negligible, and it's much easier to hand-verify than an intrusive doubly-linked-list LRU (the O(1) approach a production simulator would use).

Direct-mapped is just N=1. There's a single generic set-associative cache model; direct-mapped and fully-associative are just associativity set to 1 or to the total line count, not separate code paths.

Out of scope (intentionally): write-allocate/write-back policy modeling (the trace's read/write tag is parsed but doesn't affect hit/miss behavior), replacement policies other than LRU, and multi-level cache hierarchies.

Correctness check

tests/tiny.trace is a hand-computed 5-access trace against --size 64 --block 16 --assoc 1 (4 sets, 16-byte offset):

r 0x00  -> index 0, tag 0 -> miss (cold)
r 0x10  -> index 1, tag 0 -> miss (cold)
r 0x00  -> index 0, tag 0 -> hit
r 0x40  -> index 0, tag 1 -> miss, evicts the tag-0 line at index 0
r 0x00  -> index 0, tag 0 -> miss, evicts the tag-1 line at index 0

By hand: 5 accesses, 1 hit, 4 misses, 2 evictions. Running ./cachesim --size 64 --block 16 --assoc 1 --trace tests/tiny.trace matches exactly.