GATE CS 2022 Q44 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To analyze the cache behavior, we first determine the address division for the direct-mapped cache:

• Cache Size: $2 \text{ KB} = 2^{11} \text{ bytes}$
• Block Size: $64 \text{ bytes} = 2^6 \text{ bytes} \implies$ Block Offset: $6 \text{ bits}$
• Number of Cache Lines: $\frac{2 \text{ KB}}{64 \text{ bytes}} = 32 = 2^5 \implies$ Line Index: $5 \text{ bits}$
• Tag Size: $16 - (5 + 6) = 5 \text{ bits}$

Now, we convert the physical addresses of the first bytes of $\text{P, Q, R,}$ and $\text{S}$ to binary to find their Tag (bits 15–11) and Line Index (bits 10–6):

• P (0xA248): 10100 01001 001000 $\implies$ Tag = $20$, Line Index = $9$
• Q (0xC28A): 11000 01010 001010 $\implies$ Tag = $24$, Line Index = $10$
• R (0xCA8A): 11001 01010 001010 $\implies$ Tag = $25$, Line Index = $10$
• S (0xA262): 10100 01001 100010 $\implies$ Tag = $20$, Line Index = $9$

From this mapping, we observe:

1. P and S have the same Tag ($20$) and Line Index ($9$). Thus, they reside in the same cache block on Line 9.
2. Q and R map to the same Line Index ($10$) but have different Tags ($24$ and $25$). Thus, they conflict and evict each other.

Let's evaluate the statements based on the access sequence $\text{P} \to \text{Q} \to \text{R} \to \text{S}$:

• Statement A is TRUE: The very first access to $\text{P}$ loads the block containing both $\text{P}$ and $\text{S}$ into Line 9. Since Line 9 is never evicted, every subsequent access to $\text{S}$ is a hit.
• Statement B is TRUE: No other accessed data maps to Line 9, so once $\text{P}$ is loaded, it is never evicted.
• Statement C is FALSE: At the end of execution, the block containing $\text{P}$ and $\text{S}$ remains in Line 9, and the block containing $\text{R}$ is in Line 10. Thus, $\text{P}$, $\text{R}$, and $\text{S}$ all reside in the cache.
• Statement D is TRUE: Since $\text{Q}$ is accessed immediately before $\text{R}$ in each iteration, $\text{Q}$ is always in Line 10 when $\text{R}$ is accessed. Thus, every access to $\text{R}$ evicts $\text{Q}$.