I am trying to understand the real difference between conflict and compulsory misses and found this example very confusing.
Consider a 2−way set associative cache with 256 blocks and uses LRU replacement. Initially, the cache is empty. Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of access to memory blocks :
{0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129}
is repeated 10 times. The number of conflict misses experienced by the cache is _________ .
If we go by the definition of respective kinds of misses we get total conflict misses as 78. But the official answer says 76 as it assumes that the first access is always compulsory even if it is conflicting with some cache block.
Please, explain this concept with the help of the above example.
If the first access is mapped to a set where all of the ways are occupied and one of the existing lines has to be evicted, that would not be a conflict miss. A conflict miss occurs when the line to be accessed has been previously evicted because the associativity is too small but the total capacity is large enough.
Compulsory misses occur due to first time access to the block.
I understand that this is the textbook definition of a compulsory miss. In general, though, the first access to a line that misses in the cache may not necessarily be a compulsory miss. The miss can be a conflict or capacity miss. This can happen if the cache has a hardware prefetcher (or if software prefetches are not considered to be normal accesses). The prefetcher might have fetched a line that has never been accessed before into the cache but then it got evicted before it gets accessed for the first time. Later when it does get accessed, a miss occurs and that miss would not be a compulsory miss. This distinction is important because the number of compulsory misses is a measure of success of the prefetching algorithm (together with the number of hits to a prefetched line before it gets evicted). That said, your textbook or teacher probably considers prefetching to be out of scope.