How to find number of conflict misses in a cache simulator

Question

I am trying to design a cache simulator. To find there is a cache hit/miss for a block, I compare its index and offset with the blocks already present in the cache. In case of n-associative cache, I check only those entries of cache where that block can go.

Finding the number of hits and cold misses is then trivial. If the cache is full (or all the entries where the block can go are occupied), then we have a capacity miss.

Could someone please tell me how can I find the number of conflict misses? Definition of conflict miss says:

Conflict misses are those misses that could have been avoided, 
had the cache not evicted an entry earlier

How can I determine if an entry, removed from the cache earlier, should or should not have been removed?

Answer 1

Conceptually this is how you can measure the types of misses:

measure the number of misses (M) for the same code for the following caches:

1. Infinite capacity, fully associative cache
2. Fully associative cache of a finite capacity
3. N-way associative cache of a finite capacity

then

• number of compulsory misses = M1
• number of capacity misses = M2-M1
• number of conflict misses = M3- num capacity misses - num compulsory misses = M3 - M2

When actually implementing these measurements in your simulator, you need not run three different simulations. The misses to a hash map as described by Leeor gives you M1. Now if you implement your hash map as a list(or some more efficient data structure) such that you never delete an entry, but whenever an access is made to address 'x' put 'x' in the front of the list. Whenever a reference is made and it hits in the first 'S' locations in your list(where S is the size of your cache), it can be counted as a HIT for cache number 1 and 2. The actual cache simulation (modeling N-way cache) gives you M3. So the actual cache model plus this list data structure gives you M1, M2, M3 in a single simulation run.

Answer 2

You can store all historical addresses in a hashmap and do lookups whenever you miss - if you miss the cache but hit in the hash - you evicted that line at some point.

This however can grow in size quite rapidly. In most cases though, it's more interesting to ask "could i have kept the line cached just a little while longer and avoid this miss?". For that, you could extend your cache simulation to have more ways (up to the history depth you determine is still realistic to keep lines at). You lookup your cache like before, and maintain the same LRU method you would have used, but if the way being hit is beyond the "real" way count in terms of LRU age - it's a conflict miss (i.e. - the line was there, but pushed back the LRU chain beyond a point it should have been evicted). Make sure your LRU mechanism can work this way - a true LRU should be ok as it keeps a strict order, age-value based ones are also fine, but other types like pseudo LRU trees might get tricky.