The Gateway to Computer Science Excellence
+16 votes
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$
in CO and Architecture by Veteran (52.2k points)
edited by | 4.1k views
0
can't understand the solution by Kathleen.How last 4  cache acesses stored?

2 Answers

+47 votes
Best answer
$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 by
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
+3 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.

by Boss (24.2k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
198,556 comments
105,368 users