The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
3k 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$
asked in CO & Architecture by Veteran (59.7k points)
edited by | 3k views
0
can't understand the solution by Kathleen.How last 4  cache acesses stored?

1 Answer

+39 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.$
answered by Veteran (369k 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
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

44,303 questions
49,797 answers
164,411 comments
65,857 users