GATE IT 2005 | Question: 61

Question

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$

• A. $0$ $3$ $5$ $7$ $16$ $55$
• B. $0$ $3$ $5$ $7$ $9$ $16$ $55$
• C. $0$ $5$ $7$ $9$ $16$ $55$
• D. $3$ $5$ $7$ $9$ $16$ $55$

Comments

Why in the option sequence like 0,16,5,9,55,7 is not given .I think it is actual sequence .

---

@BASANT KUMAR

In the question they are asking only the blocks present in the cache. They are not asking the exact sequence of blocks.

---

block number 3,7, 55 all these are block mapped to set 3 and each set have 2 blocks so only two blocks are present in sequence  only C option

 

---

Option C is correct

Answer 1

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

$$\begin{array}{|c|c|} \hline \textbf {Set Number} &  \textbf{Block Numbers} \\\hline \text{$0$} & \text{$0,16$}  \\\hline\text{$1$} & \text{$5,9$}  \\\hline \text{$2$} &  \\\hline \text{$3$} & \text{ $\require{cancel} \cancel{3}$,$7,55$} \\\hline  \end{array}$$

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

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

(C) choice.

Comments

i am not able to grab the concept of such problems, can you please help me with that

---

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

---

Below statement is from above answer :-

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)

Anyone please help to understand, what is meaning of content written inside parentheses in above statement ?

Answer 2

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$

Comments

correct

---

Nicely explain and fantastic approach.

Answer 3

There are 4 sets in the cache. 

So given a block reference, we perform modulo 4 operation to determine the set.

Once we enter the set, the line that the block occupies depends on replacement policy.

Here Y-axis represents time.

consider set 3.. Here when 55 enters the set, 3,7 have already occupied the set. So replacement has to be done.

Here block 3 is accessed at the time instance 2 and block 7 is accessed at time instance 4.

So, block 3 is the least recently used .Hence it has to be replaced.

Let me know if you have any doubts...

Reference:https://gateoverflow.in/3691/gate2004-it-48?show=174421#a174421

 

Answer 4

We can terminate, Option A, B and D easily. One thing to observe.

No of sets = 4

3 Modulo 4 = 3

7 Modulo 4 = 3

55 Modulo 4 = 3

Therefore 3, 7 and 55 all are mapped in Set 3 whereas each set can only keep 2 blocks at most.

A has 0 3 5 7 16 55    =    block 3,7,55 are there  hence it’s false

B has 0 3 5 7 9 16 55 = block 3,7,55 are there  hence it’s false

D has 3 5 7 9 16 55   =   block 3,7,55 are there  hence it’s false.

Therefore C is the correct Answer.

Answer 5

…………………………………………………………………………….