GATE CS 2018 Q.44 (CS Q.34): Memory Hierarchy: Cache, Main Memory and Secondary Storage

The size of the physical address space of a processor is $2^P$ bytes. The word length is $2^W$ bytes. The capacity of cache memory is $2^N$ bytes. The size of each cache block is $2^M$ words. For a $K$ -way set-associative cache memory, the length (in number of bits) of the tag field is

$P - N - \log_2 K$

$P - N + \log_2 K$

$P - N - M - W - \log_2 K$

$P - N - M - W + \log_2 K$

Official answer and solution

Official answer: B
From: Official GATE 2018 answer key

Solution

Partition the physical address into tag, set index, and block offset fields.

Determine the widths of each field:

Total physical address bits: Physical address space is $2^P$ bytes, so physical address length is $P$ bits.
Block size: Each block holds $2^M$ words. With word length $2^W$ bytes, block size is $2^M \times 2^W = 2^{M+W}$ bytes. Thus, the block offset field requires $M + W$ bits.
Cache capacity and sets: Total cache capacity is $2^N$ bytes. The total number of cache lines is $\frac{2^N}{2^{M+W}} = 2^{N - M - W}$ . For a $K$ -way set-associative cache, the number of sets is:

\text{Sets} = \frac{2^{N - M - W}}{K} = \frac{2^{N - M - W}}{2^{\log_2 K}} = 2^{N - M - W - \log_2 K}

Thus, the set index field requires $N - M - W - \log_2 K$ bits.

The tag field length is:

\text{Tag} = P - (\text{Set index bits}) - (\text{Block offset bits})

\text{Tag} = P - (N - M - W - \log_2 K) - (M + W)

\text{Tag} = P - N + M + W + \log_2 K - M - W = P - N + \log_2 K

Final answer

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

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 44 of 65, printed as CS Q.34
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