Cache Misses

Understanding Cache Types

Three Types of Cache Misses

Compulsory Miss: First access to a memory block will cause a miss (unless mechanism like prefetching is used) and is termed Compulsory miss. Though this is termed compulsory miss this may get reduced by an increase in cache block size (which effectively reduces the number of memory blocks). This is also the misses that will occur even in a infinite size cache.
Capacity Miss: When a cache block is replaced due to lack of space and in future this block is again accessed, the corresponding cache miss is a Capacity miss. i.e., this miss could be avoided with a potentially larger cache. For the purpose of finding if a miss is a capacity miss we will assume the cache as fully-associative one.
Conflict Miss: This miss happens due to conflict and hence absent in a fully associative cache (with LRU replacement policy). When a cache goes from fully-associative to set-associative and then to direct-mapped, conflicts increases and the misses due to them are called conflict misses. To be precise, a conflict miss happens when a cache block is replaced due to a conflict and in future that same block is accessed again causing a cache miss.

Without explaining more lets directly go to some examples:

Consider a physical memory of $1\; MB$ size and a direct mapped cache of $8\; KB$ size with block size $32$ bytes. That is in one go $32$ bytes of data will be taken from/trasferred to main memory to/from cache. This means there are $1\;MB/8\; KB = 128$ blocks in main memory corresponding to a single cache block. Since $128$ memory blocks can map to a single cache entry, this means we need $\log_2 128 = 7$ tag bits.

Tag bits will be chosen from the higher order bits of main memory address so that adjacent main memory blocks won’t map to the same cache entry (useful in case of spatial locality). i.e., if main memory block $x$ gets mapped to a cache entry the next main memory block that maps to the same cache block will be after $X$ bytes where $X$ is the cache size (round robin fashion).
The main address bits get split into $3:$ $\text{tag }: \text{index }: \text{offset}$
For the above configuration we have $20$ bit physical address, $7$ bits of tag, $8$ bits for index ($2^{8} = 256$ entries in cache each of size 32 bytes = 8 KB) and $5$ bits of offset.

Lets see how the cache misses go.

Let there be a sequence of block accesses given by
$$2, 216, 100, 256, 2048, 728, 256, 216$$

Since physical memory is 1 MB we need 20 bits for byte addressing. Out of these 5 bits are taken by a cache block (of size 32 bytes). So, remaining 15 bits are used for block addressing (means the block address can range from 0 – 32767)

If instead of block address, memory addresses were given we have to divide by 32 (or remove the lower 5 bits) to get the block addresses

If values are in decimal consider dividing and if they are in hexa-decimal consider removing the lower bits

No. of blocks in cache $= 8\; KB / 32 B = 256$

Now, to find which cache block a memory block goes, we just have to do $\boxed{\mod 256}$ because the set/index bits of the cache are lower bits and tag bits are upper (as mentioned earlier for utilizing any spatial locality).

Thus $$\begin{array}{c|c} 2& 2\\216 & 216 \\ 100 & 100 \\ 256 & 0 \\2048 & 0 \\ 728 & 216 \\256 & 0 \\ 216 & 216\end{array}.$$

Now, lets classify the misses happened here:

$$\begin{array}{c|c|c} 2& 2 & \text{Compulsory Miss}\\216 & 216& \text{Compulsory Miss} \\ 100 & 100& \text{Compulsory Miss}\\ 256 & 0& \text{Compulsory Miss}\\2048 & 0& \text{Compulsory Miss}\\ 728 & 216& \text{Compulsory Miss}\\256 & 0& \text{Conflict Miss}\\ 216 & 216& \text{Conflict Miss}\end{array}.$$

Now, why are the first $6$ accesses “Compulsory Misses”?

Because they are all FIRST access to a cache block

Why are the last $2$ accesses “Conflict Misses”?

Because these blocks were once in cache and replaced due to a conflict

Why are there no capacity misses?

We have $256$ cache blocks and in the access sequence we accessed only $6$ unique memory blocks. A capacity miss is one which is caused due to shortage in cache size. This is the miss which will happen even if we assume the cache to be fully associative.