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

https://gateoverflow.in/131023/test-by-bikram-computer-organization-and-architecture-test-2-question-15

---

Easy explanation here ...

https://gateoverflow.in/118745/gate-cse-2017-set-1-question-51?show=516617#a516617

 

---

Thanks @endurance1 i GOT 78 only and got my mistake!

 

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

this question clears the concept of all types of misses

conflict,compulsary and capacity nice question and beautiful explaination

---

where is capacity miss concept here ?

---

 @Dev_Ops not, here only Conflict miss they ask

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

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

Answer 5

Please refer to the solution below:

 

Comments

Best explanation now got it

Answer 6

There are 256 lines, so a memory block will numbered x will sit inside the cache in x mod 256th block. (Numbered 0 - 127)

But here, we got a 2-way set associative cache on our hands, so we have a total of 128 sets, and a memory block will sit inside x mod 128th set. (Numbered 0 - 127)

First iteration: 4 conflict misses.

Subsequent 9 iterations: 8 conflict misses each.

Total conflict misses = 76 

---

This image shows the first iteration. When a block comes in for the first time, it's compulsory miss.

So, conflict misses = 4 (second appearances of 0, 256, 1 and 257)

 

For the remaining iterations, the first block of Set 0, and the first block of Set 1 would repeat identically. While 128 and 129 would be untouched. But this time, all misses are conflict misses, because it's not the first time the block is introduced in the cache.
So, conflict misses = 8 for nine iterations.

So, 4 + 9(8) = 76.

---

 

Comments

This is the diagram I am looking for...Thank you bhai   @JashanArora

---

yea same here lol searching for that diagram