We can measure cache performance by "simulating" cache access using "trace of address" of executing programs.
Assuming the line size is 1 and direct map cache. To simulate a cache access we prepare two arrays: empty, tag, the size is equal to cache size. Initially empty[] is all zeros.
Given an address in the trace, we compute cache index by modulo address by cache size, let call it cache index (idx).
An access is done by checking the cache slot is empty or not, if it is empty then mark it as full and store the upper address, computed by address integer divide by cache size, in tag[idx].
If cache slot is full then check the tag in tag[idx] whether it is equal to upper address, if it is then this access is a hit.
If cache slot is full but it is not the same address, then write the new tag to this slot.
We run through all addresses in the trace, keep counting the number of hit.
hit rate = hit / total access
To simulate multi-way cache is similar (assume two-way), but we need two sets of empty[] and tag[]. Checking hit/miss has to be done to each set.
You can find the Python code for this simple cache simulation here.
Here is a trace you can use to experiment with.
This is a trace of a compiler, Som v. 4.1, compiles itself. See this page
for the detail about the compiler
http://www.cp.eng.chula.ac.th/~piak/project/som/index.htm
The trace file is trx.zip (5 Mbytes). When unzip it is ~100Mbytes. Each line contains an address xxx {r,w} r is read w is write. Data is at address 0..371192 and instruction is at address 400000..410873. Total number of instruction executed is 4,520,058. Total number of data access is 1,044,647.
Files trx.zip cache-py.txt
last update 28 March 2022