GATE2025_CS1_Q36

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=2¹⁰, 1M=2²⁰.]

✅ Final Answer:

The correct answer is option (A) 6 × 2¹⁰.

🔹 Short Answer:

First, calculate the number of cache lines: 16 KB / 16 B = 2¹⁴ / 2⁴ = 2¹⁰ lines. Next, determine the address bit distribution for direct mapping: the 20-bit physical address is split into Tag, Line, and Word bits. Word bits = log₂(16) = 4. Line bits = log₂(2¹⁰) = 10. Tag bits = 20 - 10 - 4 = 6. Total bits for tag storage = (Number of lines) × (Tag bits per line) = 2¹⁰ × 6.

🔸 Long Answer:

To solve this, we need to break down the physical address into its components (Tag, Line, and Word/Offset) and then calculate the total size of the tag directory.

Step 1: Analyze Given Parameters

• Main Memory Size: 1M bytes = 2²⁰ bytes. This confirms the Physical Address (PA) size is 20 bits.
• Cache Memory Size: 16K bytes = 16 × 2¹⁰ = 2⁴ × 2¹⁰ = 2¹⁴ bytes.
• Cache Block Size (Line Size): 16 bytes = 2⁴ bytes.
• Mapping: Direct Mapping.

Step 2: Calculate the Number of Cache Lines

The number of lines in the cache determines how many blocks of data the cache can hold simultaneously. Each line will have its own tag associated with it.

Number of Cache Lines = (Cache Size) / (Block Size)
= 2¹⁴ bytes / 2⁴ bytes = 2¹⁰ lines
= 1024 lines

Step 3: Deconstruct the Physical Address

For a direct-mapped cache, the 20-bit physical address is divided into three parts:

• Word (Block) Offset: Identifies a specific byte within a cache block.
  Word bits = log₂(Block Size) = log₂(16) = 4 bits.
• Line Number: Identifies which line in the cache the memory block maps to.
  Line bits = log₂(Number of Cache Lines) = log₂(2¹⁰) = 10 bits.
• Tag: The remaining bits, used to identify which of the many possible main memory blocks is currently stored in that cache line.
  Tag bits = (Total PA bits) - (Line bits) - (Word bits)
Tag bits = 20 - 10 - 4 = 6 bits.

Step 4: Calculate Total Tag Storage

The cache needs to store a tag for each of its lines. The total storage required for all tags is the number of lines multiplied by the size of each tag.

Total Tag Bits = (Number of Cache Lines) × (Tag Bits per Line)
= 2¹⁰ × 6 bits

This matches option (A). The result is 1024 × 6 = 6144 bits.

Bibliography:
- Patterson, D. A., & Hennessy, J. L. (2017). Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufmann. (Chapter 5: Large and Fast: Exploiting Memory Hierarchy).
- Stallings, W. (2016). Computer Organization and Architecture: Designing for Performance. Pearson. (Chapter 4: Cache Memory).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.