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

To find the size of the cache tag directory, we need to calculate the number of blocks in the cache, the tag size for each block, and then the total bits required for all entries.

Step 1: Calculate the number of cache blocks (lines)

$$\text{Total Blocks} = \frac{\text{Cache Size}}{\text{Block Size}} = \frac{256 \text{ KB}}{32 \text{ Bytes}} = \frac{2^{18} \text{ Bytes}}{2^5 \text{ Bytes}} = 2^{13} = 8192 \text{ blocks}$$

Step 2: Calculate the number of sets

Since the cache is 4-way set associative: $$\text{Number of Sets} = \frac{\text{Total Blocks}}{\text{Associativity}} = \frac{2^{13}}{4} = 2^{11} = 2048 \text{ sets}$$

Step 3: Determine the address bit division

The processor uses a 32-bit address. We divide the address into Tag, Set Index, and Block Offset fields:

• Block Offset: $\log_2(32) = 5$ bits
• Set Index: $\log_2(2048) = 11$ bits
• Tag: $32 - (11 + 5) = 16$ bits

Step 4: Calculate the size of each tag directory entry

Each entry in the tag directory corresponds to one cache block and contains:

• Address tag: $16$ bits
• Valid bits: $2$ bits
• Modified bit: $1$ bit
• Replacement bit: $1$ bit

Step 5: Calculate the total tag directory size

Since there is one entry per cache block: $$\text{Total Tag Directory Size} = \text{Total Blocks} \times \text{Bits per entry}$$ $$\text{Total Tag Directory Size} = 8192 \times 20 \text{ bits} = 163,840 \text{ bits}$$

Converting to Kbits ($1 \text{ Kbit} = 1024 \text{ bits}$): $$\text{Size} = \frac{163,840}{1024} = 160 \text{ Kbits}$$

Therefore, the correct option is A.