Cache simulator
A CPU cache simulator in C that replays memory traces and counts hits, misses and evictions.
A cache is set up from three numbers: s bits pick the set (2^s sets), E lines live in each set, and b bits pick the byte inside a block (2^b bytes per block). Every address is cut into those parts: the lowest b bits are the offset, the next s bits choose the set, and everything above is the tag that says which block is stored there.
The simulator replays a trace of loads (L), stores (S) and modifies (M, a load then a store). For each access it checks the chosen set for a line with a matching tag: that's a hit. If none matches it's a miss, and if the set is full the least recently used line is evicted to make room.
For the second part we designed our own replacement policy: a hybrid that keeps lines until space runs out, then evicts based on how often each line is used.
Memory trace
Loads, stores, modifies
Cache simulator
Tag, set, offset; LRU eviction
Results
Hits, misses, evictions
- Memory trace to Cache simulator
- Cache simulator to Results
See it work
One trace, address by address
| Access | Tag | Set | Offset | Result |
|---|---|---|---|---|
| L 10 | 0 | 1 | 0 | miss |
| M 20 | 0 | 2 | 0 | miss, then hit |
| L 22 | 0 | 2 | 2 | hit |
| S 18 | 0 | 1 | 8 | hit |
| L 110 | 1 | 1 | 0 | miss, eviction |
| L 210 | 2 | 1 | 0 | miss, eviction |
| M 12 | 0 | 1 | 2 | miss, eviction, then hit |
16 sets of 1 line, 16-byte blocks (s = 4, E = 1, b = 4). Addresses are hexadecimal. Three different blocks all map to set 1, so they keep evicting each other.
The same trace, run for real
$ ./csim -v -s 4 -E 1 -b 4 -t traces/yi.traceL 10,1 missM 20,1 miss hitL 22,1 hitS 18,1 hitL 110,1 miss evictionL 210,1 miss evictionM 12,1 miss eviction hithits:4 misses:5 evictions:3$ ./csim -s 4 -E 2 -b 4 -t traces/yi.tracehits:4 misses:5 evictions:2
With two lines per set (E = 2), the set 1 blocks have room to share, and one eviction goes away.