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$
edited | 1.9k views

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

edited
+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

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
0
correct