The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x

GATE2005-IT-61

+10 votes
1.9k views

Consider a $2$-way set associative cache memory with $4$ sets and total $8$ cache blocks $(0-7)$ and a main memory with $128$ blocks $(0-127)$. What memory blocks will be present in the cache after the following sequence of memory block references if LRU policy is used for cache block replacement. Assuming that initially the cache did not have any memory block from the current job?
$0$ $5$ $3$ $9$ $7$ $0$ $16$ $55$

  1. $0$ $3$ $5$ $7$ $16$ $55$
  2. $0$ $3$ $5$ $7$ $9$ $16$ $55$
  3. $0$ $5$ $7$ $9$ $16$ $55$
  4. $3$ $5$ $7$ $9$ $16$ $55$
asked in CO & Architecture by Boss (19.1k points)
edited by | 1.9k views

2 Answers

+28 votes
Best answer

$128$ main memory blocks are mapped to $4$ sets in cache. So, each set maps $32$ blocks each. And in each set there is place for two blocks ($2$-way set). 

Now, we have $4$ sets meaning $2$ index bits. Also, $32$ blocks going to one set means $5$ tag bits. 

Now, these $7$ bits identify a memory block and tag bits are placed before index bits. (otherwise adjacent memory references- spatial locality- will hamper cache performance)

So, based on the two index bits (lower $2$ bits) blocks will be going to sets as follows:

Set Number Block Numbers
$0$ $0,16$
$1$ $5, 9$
$2$  
$3$ 3, $7, 55$

Since, each set has only $2$ places, $3$ will be throw out as its the least recently used block. So, final content of cache will be

$0$ $5$  $7$  $9$  $16$  $55$

$(C)$ choice.

answered by Veteran (353k points)
edited by
+4
Hi Arjun,

Just one minor correction, set 1 will have 9th m/m block along with 5. here concept is much simple, we have 4 sets 0-3, divide each m/m block no with 4 and place that m/m block on the remainder cache set no. if conflict occurs use LRU policy to replace the page.

-Manu
+2
Thanks for that. Yes, once index bits is found to be 2, we can just do mod 4 of block address and gets its corresponding set.
0
i am not able to grab the concept of such problems, can you please help me with that
0

Below table, 1st row represents memory block numbers and below them are their respective set numbers.

since, each set contains only 2 blocks,

for each set(0-3) scan table from right to left and corresponding to each set fetch 2 entries.

This will give you memory blocks in the cache.

0 5 3 9 7 0 16 55
0 1 3 1 3 0 0 3
+4 votes

Cache Memory has $4$ sets and each set contain $2$ lines. 
To map main memory block to cache we are going to use $Kmod4$
$0$ - Miss - Mapped to set $0$
$5$ - Miss - Mapped to set $1$
$3$ - Miss - Mapped to set $3$
$9$ - Miss - Mapped to set $1$
$7$ - Miss - Mapped to set $3$
$0$  - Hit
$16$ - Miss -  Mapped to set $0$
$55$ - Miss - Mapped to set $3$ ( since LRU is used we are going to replace $3$)

Set $0$ $0$
$16$
Set $1$ $5$
$9$
Set $2$  
 
Set $3$ $3$ replaced by $55$
$7$

So following memory block will be present at the end : $0,16,5.9,55,7$

answered by Loyal (7.4k points)
edited by
0
correct
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

37,117 questions
44,699 answers
127,273 comments
43,759 users