Conflict Miss Compulsory Miss Capacity Miss Direct Mapped Cache


#1

Consider a direct mapped cache of size 4 lines with line size 4 Bytes. If the following memory addresses are requested, then how many compulsory,capacity and conflict miss are there respectively ?
0, 4, 256, 4, 268, 4, 8, 0, 256, 4

(i)5,0,2
(ii)5,1,2
(iii)5,1,1
(iv)5,2,0


#2

Direct Mapped Cache Contains
[ Tag bits | Line No | Line Offset ]

Line Size = 4 Bytes = 2^2 Bytes, So Line Offset = 2 bits

No. of Lines = 4 = 2^2, So for Line No we would use 2 bits

Now Lets see the Memory Requests,

`Request        Binary       Tag_Bits       Line_No      Line_Offset`
     0         0000 0000       0000            00            00
     4         0000 0100       0000            01            00
     8         0000 1000       0000            10            00
    256      1 0000 0000      10000            00            00
    268      1 0000 1100      10000            11            00

IMPORTANT NOTE:
Priority_Order: Compulsory_Misses > Conflict_Misses > Capacity_Misses

Always 1st try to find Compulsory_misses then Conflict_Misses and Finally Capacity_Misses.

Now as there are 5 unique or distinct memory requests, So compulsorily there will be 5 misses because initially the cache will be empty and we have to load these pages at least once into our cache compulsorily.
So, Compulsory Misses = 5 (Or, We can count while solving)

Now let’s try to find the Conflict Miss, Capacity Miss & Compulsory Misses in a detailed way,

Line 0 -
Line 1 -
Line 2 -
Line 3 -

Initially our cache is empty.
Now Memory request ‘0’ arrives and it will be mapped to Line No = 0 ( See the Line number from the above table we have made) —> Compulsory_Miss_1
Then Memory request ‘4’ arrives and it will be mapped to Line No = 1 —> Compulsory_Miss_2
This is how our cache looks right now.

Line 0 - 0
Line 1 - 4
Line 2 -
Line 3 -

Now when memory request ‘256’ arrives it will be mapped to Line = 0.
But Line 0 is already occupied.
We might think that there would be a capacity miss but actually there will be a Compulsory Miss as 256 request has arrived for the 1st time. —> Compulsory_Miss_3

Line 0 - 256
Line 1 - 4
Line 2 - 
Line 3 -

Now 4 arrives and it will be a HIT as 4 is already present in the cache.
Next 268 arrives and it will be mapped to Line No = 3 —> Compulsory_Miss_4
Next Again 4 arrives and again it will be a HIT.
Next 8 arrives and it will be mapped to Line No = 2 —> Compulsory_Miss_5
This is how our cache looks right now.

Line 0 - 256
Line 1 - 4
Line 2 - 8
Line 3 - 268

Now 0 arrives. We have already seen 0 before. So no chance of Compulsory Miss here.
It will try to map to Line No =0
Now see the Least Recently Used Element in the table, i.e. 256
So there won’t be a Conflict Miss as we are trying to remove the LRU element only.
So it is a Capacity Miss. ----> Capacity_Miss_1
This is how our cache looks now.

Line 0 - 0
Line 1 - 4
Line 2 - 8
Line 3 - 268

Now again 256 arrives. We have already seen it before. So no chance of Compulsory Miss.
It will try to map to Line No = 0
LRU element is 268.
But we are trying to remove 0, So there would be a conflict miss. ----> Conflict_Miss_1
This is how our tables looks now.

Line 0 - 256
Line 1 - 4
Line 2 - 8
Line 3 - 268

Now Finally 4 arrives and there will be a HIT.

So you can clearly see,
Compulsory Misses = 5
Capacity Misses = 1
Conflict Misses = 1

option (iii) is the correct answer.

References:


https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Memory/introCache.html


#3

The second memory request i.e., for 4 will be mapped ti line 0 only because it is direct mapped cache. In fact, all the requests here will be mapped to line 0 only because remainder when divided with 4 will be 0 in all the cases