GATE CS 2020 Q30 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To determine which cache set each physical address maps to, we first analyze the division of the physical address bits.

1. Address Bit Division:

• Main Memory Size: $16\text{ MB} = 2^{24}$ bytes $\implies$ Physical Address = $24$ bits.
• Block Size: $256\text{ bytes} = 2^8$ bytes $\implies$ Block Offset = $8$ bits.
• Number of Cache Blocks: $\frac{64\text{ KB}}{256\text{ B}} = \frac{2^{16}}{2^8} = 256$ blocks.
• Number of Sets: Since the cache is $4$-way set associative, $\text{Number of Sets} = \frac{256}{4} = 64 = 2^6$ sets $\implies$ Set Index = $6$ bits.
• Tag: $24 - (6 + 8) = 10$ bits.

Thus, the $24$-bit physical address is structured as:

[ Tag (10 bits) | Set Index (6 bits) | Block Offset (8 bits) ]

2. Extracting Set Index for each Address:

Since the block offset is the lower $8$ bits (corresponding to the last $2$ hexadecimal digits), the Set Index consists of the next $6$ bits.

• $A1 = \text{0x42C8A4}$
  Binary: $\underbrace{0100\,0010\,11}_{\text{Tag}}\ \underbrace{00\,1000}_{\text{Set Index}}\ \underbrace{1010\,0100}_{\text{Offset}}$
  Set Index = $001000_2 = 8_{10}$
• $A2 = \text{0x546888}$
  Binary: $\underbrace{0101\,0100\,01}_{\text{Tag}}\ \underbrace{10\,1000}_{\text{Set Index}}\ \underbrace{1000\,1000}_{\text{Offset}}$
  Set Index = $101000_2 = 40_{10}$
• $A3 = \text{0x6A289C}$
  Binary: $\underbrace{0110\,1010\,00}_{\text{Tag}}\ \underbrace{10\,1000}_{\text{Set Index}}\ \underbrace{1001\,1100}_{\text{Offset}}$
  Set Index = $101000_2 = 40_{10}$
• $A4 = \text{0x5E4880}$
  Binary: $\underbrace{0101\,1110\,01}_{\text{Tag}}\ \underbrace{00\,1000}_{\text{Set Index}}\ \underbrace{1000\,0000}_{\text{Offset}}$
  Set Index = $001000_2 = 8_{10}$

Comparing the set indices, we find that $A2$ and $A3$ both map to set $40$.