GATE CS 2025 Set 1 Q.36: Memory Hierarchy: Cache, Main Memory and Secondary Storage

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory is byte addressable, $\text{1K}=2^{10}$ , $\text{1M}=2^{20}$ .]

$6 \times 2^{10}$

$8 \times 2^{10}$

$2^{12}$

$2^{14}$

Official answer and solution

Official answer: A
From: Official GATE 2025 answer key

Solution

Determine the number of cache lines and the tag width in bits for each line, then multiply them.

Cache geometry:
- Cache size $= 16\text{ KB} = 2^{14}$ bytes.
- Block size $= 16\text{ bytes} = 2^4$ bytes $\implies$ Byte offset $= 4$ bits.
- Number of cache lines (blocks) $= \frac{2^{14}}{2^4} = 2^{10}$ lines $\implies$ Line index $= 10$ bits.
Tag size per cache line:
- Memory address $= 20$ bits.
- Tag bits per line $= 20 - \text{Index} - \text{Offset} = 20 - 10 - 4 = 6$ bits.
Total tag storage:

\text{Total tag bits} = \text{Number of lines} \times \text{Tag bits per line} = 6 \times 2^{10}

Final answer

Option (A)

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

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 36 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