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

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