GATE CSE 2017 Set 1 | Question: 51

Question

Consider a $2$-way set associative cache with $256$ blocks and uses $\text{LRU}$ replacement. Initially the cache is empty. Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of access to memory blocks :

      $\big \{0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129 \big \}$

is repeated $10$ times. The number of conflict misses experienced by the cache is _________ .

Comments

More questions to practice –

https://gateoverflow.in/20086/page-replacement 

https://gateoverflow.in/30994/direct-mapping-and-types-of-misses 

Read - 

https://gatecse.in/cache-misses/

 

---

endurance1

i exactly did the same mistake!😥

---

@jatinmittal199510

Thanks for the references :)

Answer 1

$\{0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129\}$

1$^{\text{st}}$ Iteration:

For $\left \{ 0,128,256,128,0,128,256,128 \right \}$

\begin{array}{|l|c|l|} \hline \textbf {Block ID} \ & \textbf{Type} &  \textbf{Set 0 content } \\\hline \text{0} & \text{Compulsory Miss} & \text{0} \\\hline\text{128} & \text{Compulsory Miss} & \text{0   128} \\\hline \text{256} & \text{Compulsory Miss} & \text{128   256}\\\hline \text{128} & \text{Hit} & \text{256   128} \\\hline \text{0} & \text{Conflict miss} & \text{128   0} \\\hline \text{128} & \text{Hit} & \text{0   128} \\\hline \text{256} &  \text{Conflict miss} & \text{128   256} \\\hline \text{128} & \text{Hit} & \text{256   128} \\\hline \end{array}

Total number of conflict misses $=2$;

Similarly for  $\left \{ 1,129,257,129,1,129,257,129 \right \}$, total number of conflict misses in $\text{set1} = 2$

Total number of conflict misses in $1^{\text{st}}$ iteration $= 2+2=4$

$2^{\text{nd}}$ iteration:

for $\left \{ 0,128,256,128,0,128,256,128 \right \}$

\begin{array}{|l|c|l|} \hline \textbf {Block ID} \ & \textbf{Type} &  \textbf{Set 0 content } \\\hline \text{0} & \text{Conflict Miss} & \text{128   0} \\\hline\text{128} & \text{Hit} & \text{0   128} \\\hline \text{256} & \text{Conflict miss} & \text{128   256}\\\hline \text{128} & \text{Hit} & \text{256   128} \\\hline \text{0} & \text{Conflict miss} & \text{128   0} \\\hline \text{128} & \text{Hit} & \text{0   128} \\\hline \text{256} & \text{Conflict miss} & \text{128   256} \\\hline \text{128} & \text{Hit} & \text{256   128} \\\hline \end{array}

Total number of conflict misses $= 4$.

Similarly for  $\{1,129,257,129,1,129,257,129\}$, total number of conflict misses in $\text{set1} = 4$

Total Number of conflict misses in $2^{\text{nd}}$ iteration $= 4+4=8$

Note that content of each set is same, before and after $2^{\text{nd}}$ iteration. Therefore each of the remaining iterations will also have $8$ conflict misses.

Therefore, overall conflict misses $= 4+8\ast 9 = 76$

Comments

Why Set 0 has maximum 2 memory blocks??

---

@Swarnava Bose because we have 2-way set associative cache .

In general for a k-way set associative cache we have k blocks in one set. 

---

“Note that content of each set is same, before and after 2nd iteration. Therefore each of the remaining iterations will also have 8 conflict misses.”
how did u reach to this conclusion

Answer 2

In first iteration there are 4 conflict misses and 6 compulsory misses.

In second iteration, there are 4+4 = 8 conflict misses and this is the same for iterations 3..10. So, totally $8 \times 9 + 4 = 76$ conflict misses.

Comments

@Arjun Sir isn't it 78?

(0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129) - For first iteration, the bolded ones are conflict misses ie 6 misses. Please confirm.

---

(0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129)

These 2 are compulsory misses - conflict miss won't occur in a fully associative cache- but these two are fist accesses and hence not conflict misses. Many people take this as conflict as a block is thrown out affter colliding - but that is not a conflict miss- conflict miss happens when the thrown out block is again accessed.

---

Ok. Understood :(

---

@Arjun, I feel that number of blocks = 2* number of different sets. It means that all memory blocks would be mapped to 128 different sets. What do you say?

---

That happens if the block numbers are consecutive 128 numbers. (taking mod 128) as hash function rt?

---

@Arjun, your answer is right. Your colorful explanation confused me a bit :) .

---

@Arjun Sir, Please can you elaborate on the answer Sir as I m not able to understand your answer. :(

---

@arjun sir...are you absolutely sure with this answer and concept as many other institutes or websites are giving different answer.. i am confused sir.

---

@debanjan18 Are you saying I must look at their keys and correct?

Just looked at ME keys and I'm happy that they have improved a lot. This question I never expected them to be correct, but https://gateoverflow.in/118597/gate2017-2-45  answer given by them is horrible- they assuming data and instruction caches as separate cache levels. So, why should we even care for their answer to this question assuming both are given by same person? But I must say in set 2, all their other answers are reasonable.

---

And I take back my word about ME keys after seeing their set 1 keys...

---

Hi Sir,

I have seen your response but my doubt is still unclear.

As per question :

"Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set"

I agree 1st occurrence of 256 and 257 are compulsory misses but still they satisfy definition of conflict miss as well right ?(Since 0 and 128 are in 1st and 1 and 129 are in second so.)

I mean we can't say it like, miss does not occur due to the contention of multiple blocks for the same cache set 

I mean we can't assert that it is not conflict miss right ?

It can be conflict as well as compulsory 

Then why shouldn't we count them as well ?

---

@Digvijay As per definition, if a block is removed due to another block and then when a future access happens and a miss results, then it is a conflict miss. This is what they meant by that definition - they did not put it like this to test the understanding of aspirants.

---

Sir,

contention of multiple block on same cache set with lru page replacement means.

cache set is already full.and u are going to insert another page.it will make a contention.

---

I still did not understand by contention in conflict miss,plz explain in more detail.

---

@ yogesh sharma  and @_

contention of multiple block on same cache set with lru page replacement means.

Cache set is already full and you are going to insert another memory block. So here LRU replacement is used .That means new block is replaced by older one .

suppose memory blocks are 5 , 13 ,  29  and 5 .

There are 4 sets set 0, set 1 , set 2 and set 3 .

Total number of sets are 4 and blocks per set is 2 .

Set selection = ( memory block reference or block address) % (number of sets)

• 5 is mapped to set 1 ,  5%4 = 1  > it is compulsory miss ,

the cache memory scenario is at this moment  5 | __Blank__

• 13 is mapped to set 1  , 13%4 = 1  >  compulsory miss again ,

the cache memory scenario is at this moment 5 | 13

• 29 is mapped to   set 1 and 5 get replaced ,          29%4 = 1 > it is compulsory miss , the cache memory scenario is at this moment 13 | 29

• now again 5 comes and 5 is mapped to set 1 by replacing 13 , it is considered as Conflict Miss , as 5 come once previously so when next time 5 is mapped it is conflict miss .

Contention means conflict , here when 5 is mapped in same set it does not find previous block  5 , as that get replaced , so here in this example " multiple block " which is mapped again is 29 and 5 , that same cache set is set 1 .

 the scenario is at this moment 29 | 5 .

So in my example, number of compulsory miss is 3 and number of conflict miss is 1 .

Hope now confusion gets clear .

---

thanks a lot sir.

---

what about capacity misses?

---

How is it 4 conflict miss at the first time?

when  256 try to access the cache then already we have (0 and 128) in set 0? And it will be replacing 0 hence its a conflict miss right!!

---

@Star2020

Try to see the reason why miss has occured..It will clear a lot of doubts

0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129

0,128 are compulsory misses.now they are in set 0.

Now comes 256 which gets mapped to set 0.This is also a miss.

But it is also treated as compulsory miss instead of conflict miss. why??

Because even if the blocks 0,128 are not there in set 0, access to 256 is going to be a miss.

So the main reason of miss of 256 is not the competition between the blocks 0,128,256 for the place in set 0.It is due to the first time access to block and it is unavoidable.

So it is treated as compulsory miss

---

@Bikram sir when 5 comes again why will it not be treated as Capacity miss??

Answer 3

This is ms-paint edited solution

Comments

appreciated your efforts in making this:) thanks alot:)

Answer 4

There are a total of $160$ accesses to the cache blocks and these accesses will include compulsory misses, conflict misses and hits. Now, since there are 6 distinct blocks, so there will be 6 compulsory misses and if we look at the first iteration we have 6hits and after that iteration we are left with $256,128$ in set 0 and $257,129$ in set1, so from the next iteration onwards we'll have 6+2=8hits(+2 as 128 and 129 will be hits). So for 9 iterations, $9*8=72$ hits.

Total no of hits and compulsory misses= $6$(compulsory misses)+$6$(hits for 1st iteration)+$8*9$hits(8hits/iteration for 9 iterations)= $6+6+72=84$

$\therefore$ No of conflict misses $=160-84=76$

Comments

Nice Explanation @sukannya