GATE CS 2018 Q34 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To find the length of the tag field in a $K$-way set-associative cache, we can divide the physical address into three fields: Tag, Set Index, and Block Offset.

1. Physical Address Length:
The size of the physical address space is $2^P$ bytes. Thus, the total physical address length is $P$ bits.

2. Block Offset Bits:

• Word length = $2^W$ bytes
• Block size = $2^M$ words = $2^M \times 2^W$ bytes = $2^{M+W}$ bytes

3. Set Index Bits:

• Total cache capacity = $2^N$ bytes
• Number of blocks in the cache = $\frac{\text{Cache Capacity}}{\text{Block Size}} = \frac{2^N}{2^{M+W}} = 2^{N - M - W}$
• For a $K$-way set-associative cache, the number of sets is:
  $$\text{Number of Sets} = \frac{\text{Total Blocks}}{K} = \frac{2^{N-M-W}}{K} = 2^{N - M - W - \log_2 K}$$

4. Tag Bits:
The sum of the fields must equal the total physical address length $P$: $$\text{Tag bits} + \text{Set index bits} + \text{Block offset bits} = P$$ $$\text{Tag bits} + (N - M - W - \log_2 K) + (M + W) = P$$ $$\text{Tag bits} + N - \log_2 K = P$$ $$\text{Tag bits} = P - N + \log_2 K$$

Thus, the correct option is B.