Skip to content
GATETECH
Official PYQ · 2005Q67Memory Hierarchy: Cache, Main Memory and Secondary StorageMCQ1 mark

GATE CS 2005 Q67 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

Explain with AI

Consider a direct mapped cache of size 3232 KBKB with block size 3232 bytesbytes. The CPUCPU generates 3232 bitbit addresses. The number of bits needed for cache indexing and the number of tag bits are respectively,

Choose one option
View worked solution

Answer: A

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

[ Tag Bits | Index Bits | Block Offset Bits ]

We are given:

  • CPU Address Size: 32 bits32\text{ bits}
  • Cache Size: 32 KB=32×210 bytes=215 bytes32\text{ KB} = 32 \times 2^{10}\text{ bytes} = 2^{15}\text{ bytes}
  • Block Size: 32 bytes=25 bytes32\text{ bytes} = 2^5\text{ bytes}

Step 1: Calculate Block Offset Bits

The number of bits required to identify a byte within a cache block is:

Block Offset Bits=log⁡2(Block Size)=log⁡2(25)=5 bits\text{Block Offset Bits} = \log_2(\text{Block Size}) = \log_2(2^5) = 5\text{ bits}

Step 2: Calculate Cache Index Bits

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

Number of Lines=Cache SizeBlock Size=215 bytes25 bytes=210\text{Number of Lines} = \frac{\text{Cache Size}}{\text{Block Size}} = \frac{2^{15}\text{ bytes}}{2^5\text{ bytes}} = 2^{10}

Since it is a direct-mapped cache, each line corresponds to a unique index. The number of index bits is:

Index Bits=log⁡2(Number of Lines)=log⁡2(210)=10 bits\text{Index Bits} = \log_2(\text{Number of Lines}) = \log_2(2^{10}) = 10\text{ bits}

Step 3: Calculate Tag Bits

The total address size is the sum of the tag, index, and block offset bits:

Address Size=Tag Bits+Index Bits+Block Offset Bits\text{Address Size} = \text{Tag Bits} + \text{Index Bits} + \text{Block Offset Bits}32=Tag Bits+10+532 = \text{Tag Bits} + 10 + 5Tag Bits=32−15=17 bits\text{Tag Bits} = 32 - 15 = 17\text{ bits}

Thus, the number of cache indexing bits is 1010 and the number of tag bits is 1717.

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