edited by
38,317 views
91 votes
91 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 _________ .

edited by

9 Answers

Best answer
127 votes
127 votes
$\{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$
edited by
22 votes
22 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.
11 votes
11 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$
edited by
Answer:

Related questions