Skip to content
GATETECH
Official PYQ · 2025Set 1 · Q26Memory Hierarchy: Cache, Main Memory and Secondary StorageMCQ2 marks

GATE CS 2025 Set 1 Q26 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

Explain with AI

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

Choose one option
View worked solution

Answer: A

To find the total number of bits required to store all the tag values in the cache, we can break down the memory address structure for a direct-mapped cache.

1. Identify the Given Parameters

  • Main Memory Size: 1 MB=220 bytes1 \text{ MB} = 2^{20} \text{ bytes} (which corresponds to a 2020-bit physical address)
  • Cache Size: 16 KB=16×210 bytes=214 bytes16 \text{ KB} = 16 \times 2^{10} \text{ bytes} = 2^{14} \text{ bytes}
  • Block Size: 16 bytes=24 bytes16 \text{ bytes} = 2^4 \text{ bytes}

2. Calculate the Number of Cache Lines

The number of lines (or blocks) in the cache is given by:

Number of Cache Lines=Cache SizeBlock Size=21424=210\text{Number of Cache Lines} = \frac{\text{Cache Size}}{\text{Block Size}} = \frac{2^{14}}{2^4} = 2^{10}

3. Determine the Address Fields

In a direct-mapped cache, the 2020-bit physical address is split into three fields:

Physical Address (20 bits)=Tag+Line Index+Block Offset\text{Physical Address (20 bits)} = \text{Tag} + \text{Line Index} + \text{Block Offset}
  • Block Offset: Since the block size is 16 bytes=24 bytes16 \text{ bytes} = 2^4 \text{ bytes}, we need log⁡2(16)=4 bits\log_2(16) = 4 \text{ bits}.
  • Line Index: Since there are 2102^{10} cache lines, we need log⁡2(210)=10 bits\log_2(2^{10}) = 10 \text{ bits}.
  • Tag Bits: The remaining bits are used for the tag: Tag bits=20−(10+4)=6 bits\text{Tag bits} = 20 - (10 + 4) = 6 \text{ bits}

4. Calculate Total Tag Bits

Each of the 2102^{10} cache lines must store its own 66-bit tag. Therefore, the total number of bits required to store all the tag values is:

Total Tag Bits=Number of Cache Lines×Tag bits per line\text{Total Tag Bits} = \text{Number of Cache Lines} \times \text{Tag bits per line} Total Tag Bits=210×6=6×210 bits\text{Total Tag Bits} = 2^{10} \times 6 = 6 \times 2^{10} \text{ bits}

Thus, the correct option is A.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Memory Hierarchy: Cache, Main Memory and Secondary Storage questions