Consider a system with 2 KB direct mapped data cache with a block size of 64 bytes. The system has a physical address space of 64 KB and a word length of 16 bits. During the execution of a program, four data words P, Q, R, and S are accessed in that order 10 times (i.e., PQRSPQRS...). Hence, there are 40 accesses to data cache altogether. Assume that the data cache is initially empty and no other data words are accessed by the program. The addresses of the first bytes of P, Q, R, and S are 0xA248, 0xC28A, 0xCA8A, and 0xA262, respectively. For the execution of the above program, which of the following statements is/are TRUE with respect to the data cache?

### 1. Cache Parameters and Address Breakdown

• Physical Address Space:$64\text{ KB} = 2^{16}\text{ bytes} \implies 16\text{-bit address}$

• Block Size: $64\text{ bytes} = 2^6\text{ bytes} \implies 6\text{ bits for Block Offset}$

• Cache Size:$2\text{ KB} = 2048\text{ bytes}$

• Number of Lines: $\frac{2048\text{ bytes}}{64\text{ bytes}} = 32 = 2^5 \implies 5\text{ bits for Cache Line Index}$

• Tag Size:$16 - (5 + 6) = 5\text{ bits}$

The address fields are:

Alternatively, $\text{Block Number} = \lfloor\text{Address} / 64\rfloor$ and $\text{Line Index} = \text{Block Number} \pmod{32}$.

---

### 2. Mapping of P, Q, R, and S

1. P ($0\text{xA248} = 41544_{10}$):

   • $\text{Block Number} = \lfloor 41544 / 64 \rfloor = 649$

   • $\text{Line Index} = 649 \pmod{32} = 9$

   • $\text{Tag} = \lfloor 649 / 32 \rfloor = 20$

2. Q ($0\text{xC28A} = 49802_{10}$):

   • $\text{Block Number} = \lfloor 49802 / 64 \rfloor = 778$

   • $\text{Line Index} = 778 \pmod{32} = 10$

   • $\text{Tag} = \lfloor 778 / 32 \rfloor = 24$

3. R ($0\text{xCA8A} = 51850_{10}$):

   • $\text{Block Number} = \lfloor 51850 / 64 \rfloor = 810$

   • $\text{Line Index} = 810 \pmod{32} = 10$

   • $\text{Tag} = \lfloor 810 / 32 \rfloor = 25$

4. S ($0\text{xA262} = 41570_{10}$):

   • $\text{Block Number} = \lfloor 41570 / 64 \rfloor = 649$

   • $\text{Line Index} = 649 \pmod{32} = 9$

   • $\text{Tag} = \lfloor 649 / 32 \rfloor = 20$

Observe that:

• P and S belong to the same cache block (Block 649) and map to Line 9.

• Q and R map to the same Cache Line 10, but belong to different blocks (Block 778 and Block 810).

---

### 3. Execution Trace of Access Sequence $(\text{P, Q, R, S}) \times 10$

• Iteration 1:

  1. P: Miss (cold miss) $\rightarrow$ Block containing both P and S is loaded into Line 9.

  2. Q: Miss (cold miss) $\rightarrow$ Block containing Q is loaded into Line 10.

  3. R: Miss (conflict miss) $\rightarrow$ Block containing R replaces Q in Line 10 (evicts Q).

  4. S:Hit $\rightarrow$ Block was already brought into Line 9 by P.

• Iterations 2 to 10:

  1. P:Hit (Line 9 is undisturbed).

  2. Q: Miss $\rightarrow$ Evicts R from Line 10.

  3. R: Miss $\rightarrow$ Evicts Q from Line 10.

  4. S:Hit (Line 9 is undisturbed).

---

### 4. Evaluation of Options

• (A) True: Every access to S (all 10 accesses, including the first one) is a hit because P is accessed before S in each iteration.

• (B) True: Line 9 is never mapped to by Q or R, so once P is brought in during the first access, it is never evicted.

• (C) False: At the end of execution, Line 9 contains the block with P and S, and Line 10 contains the block with R. Thus, P, R, and S reside in the cache.

• (D) True: Since Q is accessed right before R in every iteration, Q always resides in Line 10 when R is accessed. Therefore, every access to R evicts Q from Line 10.

Hence, the correct options are A, B, and D.