caching - What's the difference between conflict miss and capacity miss

Question

Capacity miss occurs because blocks are being discarded from cache because cache cannot contain all blocks needed for program execution (program working set is much larger than cache capacity).

Conflict miss occurs in the case of set associative or direct mapped block placement strategies, conflict misses occur when several blocks are mapped to the same set or block frame; also called collision misses or interference misses.

Are they actually very closely related?

For example, if all the cache lines are filled and we have a read request for memory B, for which we have to evict memory A.

So should it be considered as a capacity miss since we don't have enough space? And later if we want to access memory A, and since it's evicted before, it's considered as a conflict miss.

Am I understanding this correctly? Thanks

Answer 1

The important distinction here is between cache misses caused by the size of your data set, and cache misses caused by the way your cache and data alignment are organized.

Lets assume you have a 32k direct mapped cache, and consider the following 2 cases:

1. You repeatedly iterate over a 128k array. There's no way the data can fit in that cache, therefore all the misses are capacity ones (except the first access of each line which is a compulsory miss, and would remain even if you could increase your cache infinitely).

2. You have 2 small 8k arrays, but unfortunately they are both aligned and map to the same sets. This means that while they could theoretically fit in the cache (if you fix your alignment), they will not utilize the full cache size and instead compete for the same group of sets and thrash each other. These are conflict misses, since the data could fit, but still collides due to organization. The same problem can occur with set associative caches, although less often (let's say the cache is 2-way, but you have 4 aligned data sets...).

The 2 types are indeed related, you could say that given high levels of associativity, set skewing, proper data alignments and other techniques, you could reduce the conflicts, until you're mostly left with true capacity misses that are unavoidable.