The size of the physical address space of a processor is bytes. The word length is bytes. The capacity of cache memory is bytes. The size of each cache block is words. For a -way set-associative cache memory, the length (in number of bits) of the tag field is
ANSWER
The tag field length is P − N + log₂K bits, so option (B) is correct.
Official answer: BSource: Official answer key, GATE 2018 CS (IIT Guwahati)
The physical address (P bits total) splits into three fields: tag, set index, and block offset.
Block offset: each block holds 2^M words, each word is 2^W bytes, so a block is 2^(M+W) bytes; addressing a byte within a block needs (M+W) bits.
Number of blocks in the cache = cache size / block size = 2^N / 2^(M+W) = 2^(N-M-W).
For a K-way set-associative cache, number of sets = (number of blocks)/K = 2^(N-M-W)/K = 2^(N-M-W-log2 K); so the set-index field needs (N-M-W-log2 K) bits.
Tag bits = total address bits − offset bits − index bits = P − (M+W) − (N−M−W−log2 K).
Simplify: P − M − W − N + M + W + log2 K = P − N + log2 K.
This is option (B): P − N + log2 K.
KEY IDEA
Split the physical address into tag | set-index | block-offset. Compute block-offset bits from block size (word count × word size), compute index bits from (cache blocks / K), and the tag gets whatever bits remain — note that in the final simplification the offset bits (M+W) cancel out exactly against the subtraction in the index-bit term, which is why the answer surprisingly doesn't depend on M or W.
WATCH OUT FOR
Forgetting that the block-offset subtraction and the (M+W) term embedded in the index-bit count cancel algebraically, so students either leave stray M, W terms in the final tag expression (wrongly picking C or D) or forget the log₂K adjustment entirely (picking A).
From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 22 Memory & cache questions, with notes
