GATE CS 2016 Set 2 Q32 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

In a set-associative cache, the physical address is divided into three fields:

$$\text{Physical Address} = \text{Tag} + \text{Set Index} + \text{Block Offset}$$

Let:

• $s$ be the number of bits for the Set Index.
• $b$ be the number of bits for the Block Offset.

The total number of bytes in one way of the cache (or the size of each set's capacity contribution) is given by:

$$\text{Number of Sets} \times \text{Block Size} = \frac{\text{Cache Size}}{\text{Associativity}}$$

Taking the base-2 logarithm on both sides gives the combined bits for the Set Index and Block Offset:

$$s + b = \log_2\left(\frac{\text{Cache Size}}{\text{Associativity}}\right)$$

Given:

• $\text{Cache Size} = 512\text{ KB} = 2^{19}\text{ bytes}$
• $\text{Associativity} = 8 = 2^3$

Substituting these values:

$$s + b = \log_2\left(\frac{2^{19}}{2^3}\right) = \log_2(2^{16}) = 16\text{ bits}$$

Since the total physical address width is $40$ bits, the width of the tag field is:

$$\text{Tag bits} = \text{Physical Address Width} - (s + b)$$

$$\text{Tag bits} = 40 - 16 = 24\text{ bits}$$