The size of the physical address space of a processor is bytes. The capacity of a cache memory unit is bytes. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a -way set-associative cache, where and . Let the length of the TAG field be bits for the direct mapped cache, and bits for the set-associative cache.
Which one of the following options is true?
ANSWER
Option (A): N = M + L
Official answer: ASource: Official answer key, GATE 2026 CS1 (IIT Guwahati)
Block offset bits: block size = 128 = bytes, so offset = 7 bits. This is the same for the direct-mapped and set-associative organizations, since block size is unchanged.
Total number of blocks (lines) the cache can hold = .
Direct-mapped cache: each set holds exactly 1 block, so number of sets = number of lines = , giving index length = 16 bits. Then bits.
-way set-associative cache: each set holds blocks, so number of sets , giving index length = bits.
Tag length: .
Since , this gives , so option (A) is correct.
KEY IDEA
Tag = Total address bits − Block offset bits − Index (set) bits. Block offset is fixed (7 bits) regardless of mapping scheme; only the number of sets (hence index bits) changes between direct-mapped and K-way set-associative caches of the same total capacity and block size.
WATCH OUT FOR
Forgetting that increasing associativity (K-way) shrinks the number of sets by a factor of K, so it REDUCES the index bits and thus INCREASES the tag bits — students often think higher associativity increases index bits, leading them to pick B (N = M − L) instead of A.
From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 22 Memory & cache questions, with notes
