GATE CS 2026 Set 1 Q28 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To find the relationship between the TAG field lengths $M$ and $N$, we analyze the address division for both direct-mapped and $K$-way set-associative cache configurations.

1. Given Parameters

• Physical Address Space: $2^{32}$ bytes $\implies$ Physical Address (PA) length = $32$ bits.
• Cache Capacity: $2^{23}$ bytes.
• Block Size: $128$ bytes = $2^7$ bytes $\implies$ Block Offset = $7$ bits.
• Total Cache Blocks: $\frac{2^{23}}{2^7} = 2^{16}$ blocks.

2. Direct-Mapped Cache

In a direct-mapped cache, each block in the cache corresponds to a unique index.

• Number of Index Bits: $\log_2(\text{Total Blocks}) = \log_2(2^{16}) = 16$ bits.
• TAG Bits ($M$): $$M = \text{PA length} - \text{Index bits} - \text{Block Offset bits}$$ $$M = 32 - 16 - 7 = 9 \text{ bits}$$

3. $K$-Way Set-Associative Cache

Here, the cache is divided into sets, where each set contains $K = 2^L$ blocks.

• Number of Sets: $\frac{\text{Total Blocks}}{K} = \frac{2^{16}}{2^L} = 2^{16-L}$ sets.
• Number of Set Index Bits: $\log_2(2^{16-L}) = 16 - L$ bits.
• TAG Bits ($N$): $$N = \text{PA length} - \text{Set Index bits} - \text{Block Offset bits}$$ $$N = 32 - (16 - L) - 7 = 9 + L \text{ bits}$$

4. Relationship Between $M$ and $N$

Substituting $M = 9$ into the expression for $N$:

Thus, the correct option is A.