Redirected
edited by
8,854 views
22 votes
22 votes

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

5 Answers

Best answer
51 votes
51 votes

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

edited by
24 votes
24 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$

edited by
1 votes
1 votes

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

 

0 votes
0 votes

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:

Related questions

24 votes
24 votes
1 answer
2