Consider a system with a processor and a 4 KB direct mapped cache with block size of 16 bytes. The system has a 16 MB physical memory. Four words P, Q, R, and S are accessed by the processor in the same order 10 times. That is, there are a total of 40 memory references in the sequence P, Q, R, S, P, Q, R, S,... Assume that the cache memory is initially empty. The physical addresses of the words are given below (1 word =1 byte). P: 0x845B32, Q: 0x845B26, R: 0x845B36, S: 0x846B32 Which of the following statements is/are true? Note: $1\text{K}=2^{10}$ and $1\text{M}=2^{20}$

### Cache Parameter Breakdown

1. Physical Address Space:

   $$\text{Physical Memory Size} = 16\text{ MB} = 2^{24}\text{ bytes} \implies 24\text{ address bits (6 hexadecimal digits)}$$

2. Block Offset:

   $$\text{Block Size} = 16\text{ bytes} = 2^4\text{ bytes} \implies 4\text{ bits (least significant hex digit)}$$

3. Cache Line (Index) Bits:

   $$\text{Number of Cache Lines} = \frac{\text{Cache Size}}{\text{Block Size}} = \frac{4\text{ KB}}{16\text{ B}} = \frac{2^{12}}{2^4} = 256 = 2^8 \implies 8\text{ bits (middle 2 hex digits)}$$

4. Tag Bits:

   $$\text{Tag} = 24 - 8 - 4 = 12\text{ bits (most significant 3 hex digits)}$$

---

### Address Decomposition

For an address format of [Tag (12 bits) | Line Index (8 bits) | Block Offset (4 bits)]:

• P (0x845B32): Tag = 0x845, Line Index = 0xB3, Offset = 0x2

• Q (0x845B26): Tag = 0x845, Line Index = 0xB2, Offset = 0x6

• R (0x845B36): Tag = 0x845, Line Index = 0xB3, Offset = 0x6

• S (0x846B32): Tag = 0x846, Line Index = 0xB3, Offset = 0x2

---

### Access Trace

• Iteration 1:

  1. P: Cache line 0xB3 is empty $\rightarrow$ Miss (compulsory). Block with Tag 0x845 is loaded into line 0xB3.

  2. Q: Cache line 0xB2 is empty $\rightarrow$ Miss (compulsory). Block with Tag 0x845 is loaded into line 0xB2.

  3. R: Accesses line 0xB3. Tag in line 0xB3 is 0x845 (matching R) $\rightarrow$ Hit.

  4. S: Accesses line 0xB3. Tag in line 0xB3 is 0x845, but S has Tag 0x846$\rightarrow$Miss (conflict). Block with Tag 0x846 replaces Tag 0x845 in line 0xB3.

• Iterations 2 through 10:

  1. P: Accesses line 0xB3. Line 0xB3 contains Tag 0x846 from S $\rightarrow$ Miss (conflict). Block with Tag 0x845 is loaded.

  2. Q: Accesses line 0xB2. Line 0xB2 still has Tag 0x845$\rightarrow$Hit.

  3. R: Accesses line 0xB3. Line 0xB3 contains Tag 0x845 (loaded by P) $\rightarrow$ Hit.

  4. S: Accesses line 0xB3. Line 0xB3 contains Tag 0x845$\rightarrow$Miss (conflict). Block with Tag 0x846 is loaded.

---

### Verification of Options

• (A) is TRUE: P misses on all 10 accesses.

• (B) is TRUE: R hits on all 10 accesses (since P always pre-loads the block containing R immediately before R is accessed).

• (C) is FALSE: Q misses only on the first access and hits in all remaining 9 accesses.

• (D) is FALSE: S results in a cache miss on every access (10 misses total).