GATE 2026 CS (CS1) – Question 38
The size of the physical address space of a processor is $2^{32}$ bytes. The capacity of a cache memory unit is $2^{23}$ bytes. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a $K$-way set-associative cache, where $K = 2^L$ and $L \in \{1, 2, 3\}$. Let the length of the TAG field be $M$ bits for the direct mapped cache, and $N$ bits for the set-associative cache. Which one of the following options is true?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $N = M + L$
Explanation
Physical address size = 32 bits.
Block size = $128 = 2^7$ bytes $\implies$ Block offset field = 7 bits (identical for both designs).
1. **Direct Mapped Cache**:
- Total cache lines = $\frac{\text{Cache size}}{\text{Block size}} = \frac{2^{23}}{2^7} = 2^{16}$ lines.
- Index field = 16 bits.
- Tag field $M = 32 - (\text{Index} + \text{Offset}) = 32 - (16 + 7) = 32 - 23 = 9$ bits.
2. **$K$-way Set-Associative Cache ($K = 2^L$)**:
- Number of sets = $\frac{\text{Total lines}}{K} = \frac{2^{16}}{2^L} = 2^{16 - L}$ sets.
- Set index field = $16 - L$ bits.
- Tag field $N = 32 - ((16 - L) + 7) = 32 - 23 + L = 9 + L$ bits.
Comparing $N$ and $M$:
$$N = 9 + L = M + L$$
Therefore, option (A) is correct.