Test by Bikram | Mock GATE | Test 2 | Question: 40

Question

Consider a set associative cache memory with $8$ cache blocks $(0 - 7)$ and main memory with $128$ blocks. The following block requests are made by the $CPU$ ($\text{LRU}$ (Least Recently Used) policy is used for cache block replacement).

$0 \;5\;  3\;  9\;  7\;  0\;  16\;  55$

If the cache is $2 - way$ set associative, then the cache set and block pair in which main memory block $7$ is present is:

• A. $3, 7$
• B. $3, 6$
• C. $2, 5$
• D. $7$ is recently replaced

Answer 1

$8$ blocks in $2-way$ set-associative means we have $\frac{8}{2} = 4$ cache sets.

• $0\% 4 = 0$ - set $0,$ block $0$
• $5\% 4 = 1$ - set $1,$ block $2$
• $3\% 4 = 3$ - set $3,$ block $6$
• $9\% 4 = 1$ - set $1,$ block $3$ (as $2$ is occupied)
• $7\% 4 = 3$ - set $3$, block $7$ (as $6$ is occupied)
• $0\% 4 = 0$ - set $0$, block $1$ (as $0$ is occupied)
• $16\% 4 = 0$ - set $0$, block $0$ after replacement
• $55\% 4 = 3$ - set $3$, block $6$ after replacement

$7$ is present in set number $3$ and since $3$ is already there, $7$ moves to the second block which is block number $2\times 3 + 1=7.$

$55$ replaces $3$ in block $6$ due to $\text{LRU}$ replacement policy. With $\text{MRU}$ (Most Recently Used) policy it would have replaced $7$.

Comments

Sir why not block 6?

---

see this similar Gate question , see it if you understand ..

https://gateoverflow.in/3822/gate2005-it-61

---

Sir I am not able to get the concept is the last bit of tag  telling us where to put the block for example 7 is 0000111 there are 5 bits for tag and last bit is 1 is that signifying that it should be placed in second block of set 3 ???

---

@Abhinav93

actually your question is unclear to me, i m unable to understand your doubt..

read this slide , slide number 10 http://www.cs.utexas.edu/users/mckinley/352/lectures/16.pdf

also see this 

https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Memory/set.html