GATE CSE 2009 | Question: 29

Question

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?

• A. $3$
• B. $8$
• C. $129$
• D. $216$

Comments

can't understand the solution by Kathleen.How last 4  cache acesses stored?

---

its ok. one day you will understand.

Answer 1

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

Comments

Good approach.

---

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

---

The approach towards this kind of question is explained here. Apart from that, it’s an easy question.

Answer 2

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.