edited by
14,503 views
23 votes
23 votes

Consider a $4$-way set associative cache (initially empty) with total $16$ cache blocks. The main memory consists of $256$ blocks and the request for memory blocks are in the following order:

$0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155.$

Which one of the following memory block will NOT be in cache if LRU replacement policy is used?

  1. $3$
  2. $8$
  3. $129$
  4. $216$
edited by

2 Answers

Best answer
70 votes
70 votes
$16$ blocks and sets with $4$ blocks each means there are $4$ sets.So, the lower $2$ bits are used
for getting a set and $4$-way associative means in a set only the last $4$ cache accesses can be stored.

$\text{0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155}$

mod $4$ gives,

$\text{0, 3, 1, 0, 3, 0, 1, 3, 0, 1, 3, 0, 0, 0, 1, 0, 3}$

Now for each of $0..3,$ the last $4$ accesses will be in cache.
So, $\text{{92, 32, 48, 8}, {155, 63, 159, 3}, {73, 129, 133, 1} and {}}$ will be in cache.
So, the missing element from choice is $216.$

Correct Answer: $D$
edited by
15 votes
15 votes

For selecting a set to place the block , do Block_request mod $4$ operation.

$Set\ No.$ $Line\ No.$ $Blocks$
$0$ $0$ $\require {cancel} \cancel {0}, 48$
$1$ $\require {cancel} \cancel {4},32$
$2$ $8$
$3$ $\require {cancel} \cancel {216}, 92$
$1$ $4$ $1$
$5$ $133$
$6$ $129$
$7$ $73$
$2$ $8$  
$9$  
$10$  
$11$  
$3$ $12$ $\require {cancel} \cancel {255}, 155$
$13$ $3$
$14$ $159$
$15$ $63$

We are using LRU replacement and $"8"$ came twice so when $92$ will arrive and replace $216$ not $8$ this way.

So $D.$ is the correct option.

Answer:

Related questions

52 votes
52 votes
10 answers
1
Kathleen asked Sep 22, 2014
33,924 views
Consider a $4$ stage pipeline processor. The number of cycles needed by the four instructions $I1, I2, I3, I4$ in stages $S1, S2, S3, S4$ is shown below:$$\begin{array}{|...