Measuring Cache Performance

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

The trace file is (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    cache-py.txt

last update  28 March 2022