GATE CS 2012 Q54 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To find the number of bits in the tag field of the address, we analyze the structure of the physical address for a set-associative cache.

The $32$-bit physical address is divided into three fields:

[ Tag ] [ Set Index ] [ Block Offset ]

Step 1: Calculate the Block Offset

The block size is given as $32\text{ Bytes}$.

$$\text{Block Offset} = \log_2(32) = 5\text{ bits}$$

Step 2: Calculate the Set Index

First, find the total number of blocks in the cache:

$$\text{Total Cache Size} = 256\text{ KB} = 2^{18}\text{ Bytes}$$

$$\text{Number of Blocks} = \frac{\text{Cache Size}}{\text{Block Size}} = \frac{2^{18}}{2^5} = 2^{13}\text{ blocks}$$

Since the cache is $4$-way set associative ($2^2$ blocks per set), the number of sets is:

$$\text{Number of Sets} = \frac{\text{Number of Blocks}}{\text{Associativity}} = \frac{2^{13}}{2^2} = 2^{11}\text{ sets}$$

Thus, the number of bits required for the set index is:

$$\text{Set Index Bits} = \log_2(2^{11}) = 11\text{ bits}$$

Step 3: Calculate the Tag Bits

The total address size is $32\text{ bits}$. Therefore:

$$\text{Tag Bits} = \text{Total Address Bits} - \text{Set Index Bits} - \text{Block Offset Bits}$$

$$\text{Tag Bits} = 32 - 11 - 5 = 16\text{ bits}$$

Note: The extra bits (valid, modified, and replacement bits) are stored in the cache tag directory entry alongside the tag, but they do not affect the address division.

Hence, the correct option is C.