4.1k views

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 | 4.1k views
0
can't understand the solution by Kathleen.How last 4  cache acesses stored?

$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$
by Veteran (431k points)
edited
0
Good approach.
0
We are using LRU replacement and "8" came twice so when 92 will arrive it replace 216 not "8" this way......216 will be missing from cache

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.

by Boss (24.2k points)