GATE CS 2026 Set 1 Q.38: Memory Hierarchy: Cache, Main Memory and Secondary Storage

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?

$N = M + L$

$N = M - L$

$N = M + K$

$N = M - K$

Official answer and solution

Official answer: A
From: Official GATE 2026 answer key

Solution

Compute the number of cache lines, number of sets, index bits, and tag bits for both cache organizations.

Physical address length $= 32$ bits; block offset $= \log_2(128) = 7$ bits.
Number of cache blocks (lines) $= \frac{2^{23}}{2^7} = 2^{16}$ .
Direct-mapped cache: Index field $= 16$ bits, so tag length $M = 32 - 16 - 7 = 9$ bits.
$K$ -way set-associative cache ( $K = 2^L$ ): Number of sets $= \frac{2^{16}}{2^L} = 2^{16 - L}$ , so the set index field has $16 - L$ bits and the tag length is: $N = 32 - (16 - L) - 7 = (32 - 16 - 7) + L = M + L$

Final answer

Option (A)

Common trap

Subtracting $L$ instead of adding $L$ , or using $K$ instead of $\log_2 K = L$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 38 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source