What Are Conflict Misses Exactly?

Question

I'm learning about basic cache concepts and the different types of cache misses. I understood the Compulsory types of misses but I'm having a hard time wrapping my head around the conflict and capacity types of misses! I still have to learn about replacement algorithms for the cache. I've read other questions on this site about this topic, but information on those other questions have been conflicting or vague regarding capacity and conflict misses. I'm hoping that on this one my question will be answered.

For example let's say that we have a 2 way associative cache with 4 sets. Let's talk about the first set that can store two cache lines/blocks(because it's a two way associative cache). I will now list the order of reads called from the processor. All of these addresses that are being read will just fall into the first set for simplicity sake.

-read address one (no cache line in set one for this address. This would be a compulsory cache miss. Data is copied from memory to the first cache line in this set).

-read address two (no cache line in set one for this address. This would also be a compulsory cache miss. Data is copied from memory to the second cache line in this set).

The first set of the cache is now "warmed up" meaning that the set is filled up to capacity with valid cache lines in them. Let's now try to access an address that would also fall into the first set.

-read address three (no cache line in set one for this address. Out of space in set one for anymore cache lines to be written.)

We run into the problem of trying to get a new cache line from memory into set number one but set one is fully occupied with two cache lines. In this situation you would have to use cache replacement policies. This problem is extremely prevalent in direct mapped cache. The way to mitigate this problem would be to increase the associativity of each set(meaning to increase the amount of cache lines that can be stored in one set).

My question is if this situation would be a compulsory or conflict miss? Or would a conflict miss affect all sets? What's the difference and how would each of them work in my example I wrote above? As said before, other questions on the site didn't really make sense to me so I'm hoping that I will figure this out soon.

Answer 1

First I'll give the precise definitions of these terms as were originally introduced in Mark Donald Hill's dissertation and then I'll give the loose definitions, which are more common.

Consider a cache with the following characteristics:

• It doesn't support hardware prefetching. Lines can only be filled in the cache due to incoming requests.
• It's blocking, meaning that it won't start processing a request before the current one has fully completed.
• There is only one agent, i.e. a processor, that can change the contents of the cache. No other unit in the system can cause a line to be invalidated, replaced, or filled.
• All accesses to the cache that miss result in the target cache line to be fully fetched and filled in the cache.
• The only way for an existing cache line to be evicted or invalidated is to make space for another to be filled. Otherwise, it will always be in a valid state in the cache.

Let T be a sequence of accesses that don't cross a line boundary and all of which are demand accesses (no software prefetches and no hardware prefetches from lower-numbered cache levels, if any). Each access would either count as a single miss or hit. Let M(N, S) denotes the number of misses that occur in a cache with all of the above characteristics where N is the number of ways and S is the number of sets. Note that M(N, S) must be a nonnegative integer and N and S must be positive integers. This is the cache that is under evaluation. Two other cache models can be defined based on it. Let M(N*S, 1) denotes the number of misses that occur in a cache that is identical in every way except that it has N*S ways and one set. Finally, let M(∞, 1) denotes the number of misses that occur in a cache that is identical in every way except that it has an infinite number of ways and one set (the number of sets doesn't really matter here).

Imagine now that all of the three cache models are being simulated in parallel with the same input, T, and with all caches being empty (i.e. cold start). A compulsory miss is a cache miss that occurs in the cache with an infinite number of cache ways. An access misses in the infinite cache if and only if it is the first access in T to the same cache line. If a compulsory miss occurs in the infinite model, it will necessarily also occur in the other two models. The number of compulsory misses is M(∞, 1), which is nonnegative.

A capacity miss is a cache miss that occurs in the fully associative model but not in the infinite capacity model. Therefore, the number of capacity misses is M(N*S, 1) - M(∞, 1), which is nonnegative. A capacity miss occurs in the fully associative model if and only if the access is not the first one to the cache line and the replacement policy had chosen the line to be replaced by a previously accessed line. For example, if the replacement policy is LRU, a capacity miss occurs if and only if the access is not the first one to the cache line and the total number of unique cache lines accessed so far exceed the capacity of the cache.

A conflict miss is a cache miss that occurs in the model under study but not in the fully associative model and not in the infinite capacity model. A miss is a conflict miss if and only if it's not a capacity miss and not a compulsory miss. If the model under study is fully associative, the number of conflict misses is zero. The number of conflict misses as originally defined is M(N, S) - M(N*S, 1). This quantity is nonnegative only if all accesses that miss in the fully-associative model also miss in the main model. While compulsory misses are identical in both models, not all other accesses that miss in the fully associative model will also miss in the main model and vice versa. This depends on the replacement policy. See, for example: Can a fully associative cache have a higher miss rate than a direct mapped cache?. Hence, the number of conflict misses can be negative. But then counting the number of conflict misses any other way would make the sum of all of the three types of miss counts may be larger than the total number of misses.

With the characteristics provided at the beginning, there are no other types of misses. I came up with this list of characteristics. They were not mentioned in the dissertation because most cache designs at that time were simple and had these characteristics anyway. But more modern caches used in real systems are more complicated.

Now you should be able to determine the type of the miss from the access "read address three" in your example on your own.

It's not uncommon that when people use the terms "conflict miss" and "capacity miss" they don't really mean these precise definitions but rather they are referring to these definitions in spirit. Conflict misses can be reduced by changing the layout of the data structures being accessed. Capacity misses can be reduced by reducing the working set size. When you want to measure these metrics on a real processor, you'd have to define them based on what performance monitoring features that are supported, which you cannot extend like in a simulator.

It's important to precisely define these terms when being used in an experimental evaluation context because they don't have standard definitions. Otherwise, they'd be ambiguous and no one can be sure what's being measured. If used in a discussion without numbers, then it's OK to use loosely because everybody knows what they mean in spirit.

I've read other questions on this site about this topic, but information on those other questions have been conflicting or vague regarding capacity and conflict misses.

It would have been nice if you provided links to those posts. If someone else has posted a good answer and maybe it requires only minor improvements, then there would be no need to write one from scratch. Otherwise, some of them can be closed as duplicates so that others like you who are trying to get an answer can be pointed directly to the correct answer without each one having to wade through the clutter.