A direct mapped cache simulator written in C, together with the scripts used to run it over a real memory trace and turn the results into figures. The project was built for a computer systems architecture module. It models how the shape of the cache, meaning the number of blocks and the words per block, and the write policy affect memory performance for an insertion sort workload.
The simulator reads a memory trace, replays every read and write against a direct mapped cache, and prints eight performance counters. Those counters are then swept across 144 configurations, turned into hit rate, average access time and speedup, and drawn as the four figures near the end of this file.
The cache is direct mapped, so every memory block maps to exactly one slot. Each slot holds a tag, a valid bit and a dirty bit. Addresses in the trace are word addresses and each word is 16 bits.
The address is split using the shape of the cache.
offset bits = log2(words in block)
index bits = log2(blocks in cache)
index = (address >> offset bits) & (blocks in cache - 1)
tag = address >> (offset bits + index bits)
There are two write policies and both are write allocate, which means a write miss first fetches the whole block into the cache.
- WAWB is write allocate write back. A write hit only updates the cached copy and sets the dirty bit. A dirty block is written back to main memory only when it is evicted. This keeps write traffic low.
- WAWT is write allocate write through. Every CPU write also sends one word straight to main memory, so main memory write traffic always equals the number of CPU writes.
- cachesim.c is the simulator. It reads a trace and prints the eight counters.
- trace_info.c is a helper that scans a trace and prints the totals and the address range. This is how the working set size was measured.
- WAWB_validation.txt is a small hand made trace that drives the WAWB policy through every case, with the expected counter values written in as comments.
- WAWT_validation.txt is the same idea for the WAWT policy.
- run_all_sims.sh runs cachesim over all 144 configurations and writes simulation_results.csv.
- simulation_results.csv holds the raw counters for every configuration and is the input to the figures.
- make_figures.py reads simulation_results.csv and draws the four figures into the figures folder.
- figures holds the four generated png images shown below.
- .gitignore lists the files that are not committed.
- README.md is this file.
The input trace insertion_sort_trace_109.txt is not included. It is 191 MB, which is bigger than the github 100 MB file limit, and it is data that was provided for the coursework rather than written here, so it is ignored by git. See the trace file section at the end.
gcc -O2 -std=c17 -o cachesim cachesim.c
gcc -O2 -o trace_info trace_info.c
The compiled programs are ignored by git, so rebuild them from source.
./cachesim <trace_file> <WAWB|WAWT> <blocks_in_cache> <words_in_block>
blocks_in_cache is a power of two from 2 to 512. words_in_block is a power of two from 2 to 256. Any invalid argument prints error and stops.
The output is one line of the eight counters followed by the run settings.
CPUR CPUW NRA NWA NCRH NCRM NCWH NCWM WIB BIC <filename> <WP>
Here is what each counter means.
- CPUR is CPU reads.
- CPUW is CPU writes.
- NRA is words read from main memory.
- NWA is words written to main memory.
- NCRH is cache read hits.
- NCRM is cache read misses.
- NCWH is cache write hits.
- NCWM is cache write misses.
Here is the best configuration, 512 blocks of 8 words.
$ ./cachesim insertion_sort_trace_109.txt WAWB 512 8
7517491 3724388 3880 0 7517006 485 3724388 0 8 512 insertion_sort_trace_109.txt WAWB
That is only 485 read misses out of 11.2 million accesses, and zero write backs.
$ ./trace_info insertion_sort_trace_109.txt
Trace file: insertion_sort_trace_109.txt
Total lines in file: 11241883
Total reads: 7517491
Total writes: 3724388
Total accesses: 11241879
Lowest address: 0x00247FEC
Highest address: 0x00248F0F
Address range: 3876 words (7752 bytes)
Estimated array length: 3876 elements
The sorted array spans 3876 words of 16 bits each. This working set size is the key to the results below.
bash run_all_sims.sh
python3 make_figures.py --outdir figures
The 144 configurations are the 2 write policies, by 9 values of blocks_in_cache from 2 to 512, by 8 values of words_in_block from 2 to 256. Both the block count and the word count double at each step. make_figures.py needs numpy, pandas and matplotlib.
The figures use a simple timing model.
- main memory takes 75 ns per word accessed.
- cache takes 5 ns per access.
The derived numbers come from these formulas.
Tcache = total_cpu_accesses * 5 + total_memory_words * 75
Tnocache = total_cpu_accesses * 75
AMAT = Tcache / total_cpu_accesses
Speedup = Tnocache / Tcache
No cache gives an average access time of exactly 75 ns and a speedup of 1.0, which is the baseline every configuration is measured against.
WAWB_validation.txt and WAWT_validation.txt are small hand made traces that drive the simulator through every path, that is read and write hit and miss, clean and dirty eviction, write back and write through. Each expected counter value is written into the file as a comment. The traces are built so that the final counters are all different, so a single run confirms every counter on its own.
$ ./cachesim WAWB_validation.txt WAWB 256 16
10 5 112 48 6 4 2 3 16 256 WAWB_validation.txt WAWB
$ ./cachesim WAWT_validation.txt WAWT 256 16
8 4 80 4 6 2 1 3 16 256 WAWT_validation.txt WAWT
The expected final counters are 10 5 112 48 6 4 2 3 for WAWB, and 8 4 80 4 6 2 1 3 for WAWT.
Speedup stays around 1.0, no better than having no cache, until the total cache size reaches about 4096 words, the point where the whole 3876 word array fits. Once it fits, the misses become only compulsory misses and speedup jumps to about 14.9 times. The best configuration is 512 blocks of 8 words with WAWB.
Hit rate looks fine almost everywhere, sitting near 100 percent for the larger block sizes, which makes the configurations look good. The average access time shows the real picture. With large blocks in a cache too small to hold the array, every miss drags a big block out of main memory and the average access time climbs above the 75 ns no cache baseline. The clearest case is 256 words per block in the smallest cache: the hit rate is still 99.7 percent, yet the average access time peaks at 102 ns, so the cache is actually making things worse. The average access time only drops to about 5 ns once the array fits.
At a fixed total size, more blocks of fewer words competes against fewer blocks of more words. Below the cliff, smaller blocks win because a miss wastes less memory bandwidth. Above the cliff, block size barely matters because misses are rare compulsory misses.
Write through writes one word to main memory for every CPU write, 3.72 million words, no matter the cache size. Write back defers writes and only pays on dirty evictions, so once the array fits its write traffic drops to almost zero. That difference in memory traffic is the whole reason WAWB pulls ahead.
The input trace insertion_sort_trace_109.txt is a 191 MB record of every memory access made during one run of an insertion sort, 11241879 accesses in total. It is not committed because it is far larger than the github 100 MB limit, and because it is data that was provided for the coursework rather than written here.
Each line is a read or write with a hex address. The simulator ignores the trailing data field and any comment lines that start with an exclamation mark.
R 00247FED 7147
W 0024892D 4E8E
To run the study, put a trace in this format in the project folder and pass its name to cachesim, run_all_sims.sh and trace_info.