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/

Dark Mode

32,569 views

85 votes

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 _________ .

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/

2

124 votes

Best answer

$\{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$

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$

0

@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.

0

19 votes

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.

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.

0

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**

3

10 votes

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$

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$