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?
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.