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, 1K=, 1M=.]
ANSWER
The correct answer is (A) .
Official answer: ASource: Official answer key, GATE 2025 CS1 (IIT Roorkee)
Main memory = 1M = bytes, so the processor address is 20 bits (given).
Cache size = 16K = bytes; block size = 16 = bytes.
Number of cache lines = cache size / block size = lines.
Block offset bits = bits.
Direct mapping: index (line) bits = bits.
Tag bits per line = total address bits − index bits − offset bits = bits.
Total tag storage across the whole cache = tag bits per line × number of lines = .
This matches option (A).
KEY IDEA
In direct-mapped caches, the address splits into Tag | Line Index | Block Offset. The total tag storage for the whole cache is (tag bits per line) × (number of lines) — a per-line quantity, not a fraction of the total address space.
WATCH OUT FOR
Computing only the tag width per line (6 bits) and stopping there, or matching it to an option like / by confusing "bits per tag" with "total tag storage across the cache"; also miscounting the number of lines by forgetting to divide cache size by block size before comparing to the address bits.
From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 22 Memory & cache questions, with notes
