52

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

Phonolog
  • 6,321
  • 3
  • 36
  • 64
xiaodong
  • 952
  • 1
  • 7
  • 19

3 Answers3

71

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.

Leeor
  • 19,260
  • 5
  • 56
  • 87
29

My favorite definition for conflict misses from Reducing Compulsory and Capacity misses by Norman P. Jouppi:

Conflict misses are misses that would not occur if the cache were fully associative with LRU replacement.

Let's look at an example. We have a direct-mapped cache of size of 4. The access sequences are

0(compulsory miss), 1(compulsory miss), 2(compulsory miss), 3(compulsory miss), 4(compulsory miss), 1(hit), 2(hit), 3(hit), 0(capacity miss), 4(capacity miss), 0(conflict miss)

The second to last 0 is a capacity miss because even if the cache were fully associative with LRU cache, it would still cause a miss because 4,1,2,3 are accessed before last 0. However the last 0 is a conflict miss because in a fully associative cache the last 4 would have replace 1 in the cache instead of 0.

tartaruga_casco_mole
  • 1,086
  • 3
  • 21
  • 29
  • 2
    sir why you have considered 4 as compulsary miss? isn't it be a conflict miss because there is a competition for same block?I mean 0 is in block 0 and 4 too want to be in 0th block – laura Nov 13 '17 at 15:34
  • 2
    @laura, because even if 0 was not there, 4 would still be a miss. Let's do it step by step: an infinitely large fully associative cache has only compulsory misses; now let's set a limit on the size of cache and the new misses are considered capacity miss; finally, let the cache be a set associative cache and the new misses are considered conflict misses. – tartaruga_casco_mole Nov 13 '17 at 19:20
  • @RafaelJ I got little misunderstanding on your answer and checked with a cache simulator. http://www.ecs.umass.edu/ece/koren/architecture/Cache/frame1.htm Found this answer, which is little different than urs: 0(compulsory miss), 1(compulsory miss), 2(compulsory miss), 3(compulsory miss), 4(capacity miss), 1(hit), 2(hit), 3(hit), 0(capacity miss), 4(capacity miss), 0(hit) I didn't see conflict miss here, can you please explain about conflict miss? – duslabo Nov 25 '17 at 09:38
  • I have used cache size 4 and number of sets 1, If I use number of sets 2 all the capacity miss will become conflict miss. – duslabo Nov 25 '17 at 09:43
  • @JeshwanthKumarNK, in my example the setting is direct mapping ( only 1 way) In your first example, it is fully associative cache – tartaruga_casco_mole Nov 25 '17 at 13:11
  • Even with 1-way set associative(direct mapped) setting in the simulator, it shows only 4 compulsory misses and 4 conflict misses, and no capacity misses. Is the simulator wrong? – Rishabh Gupta Dec 05 '17 at 09:55
  • 1
    I got your explanation till `0(compulsory miss), 1(compulsory miss), 2(compulsory miss), 3(compulsory miss), 4(compulsory miss), 1(hit), 2(hit), 3(hit)`, Now I am unable to understand why `0(capacity miss)` is now? It's already accessed once in starting. Similarly for `4(capacity miss)`. Could you please explain? Thanks in advance. – Display Name is missing Jan 02 '18 at 13:14
  • @RishabhGupta, I think that the simulator is wrong. First 4 is definitely a cold miss (compulsory miss) since it has never been accessed before. – tartaruga_casco_mole Jan 02 '18 at 15:23
17

Compulsory miss: when a block of main memory is trying to occupy fresh empty line of cache and the very first access to a memory Block that must be brought into cache is called compulsory miss.

Conflict miss: when still there are empty lines in the cache, block of main memory is conflicting with the already filled line of cache, ie., even when empty place is available, block is trying to occupy already filled line. its called conflict miss.

Capacity miss: miss occured when all lines of cache are filled.

conflict miss occurs only in direct mapped cache and set-associative cache. Because in associative mapping, no block of main memory tries to occupy already filled line.

Pooja Gupta
  • 191
  • 1
  • 5
  • 1
    Pooja, you definition of conflict miss is not covering all the cases. Conflict miss can also occur when we don't have empty lines and are conflicting with some already occupied line. See @tartaruga_casco_mole answer. – Vinay Yadav Jan 22 '21 at 02:22