GATE CS 2016 Set 2 Q.42 (CS Q.32): Memory Hierarchy: Cache, Main Memory and Secondary Storage

The width of the physical address on a machine is 40 bits. The width of the tag field in a 512 KB 8-way set associative cache is ________ bits.

Your answer

Official answer and solution

Solution

Use the relationship between total cache capacity, associativity, and physical address bits to find the tag width.

Given parameters:

Let $B = 2^b$ be the block size in bytes. The physical address is partitioned into:

\text{Physical Address (40 bits)} = [\text{Tag}] + [\text{Set Index}] + [\text{Block Offset}]

where the block offset field has $b$ bits.

Calculate the number of sets $S$ in the cache:

S = \frac{\text{Cache Size}}{\text{Associativity} \times \text{Block Size}} = \frac{2^{19}}{2^3 \times 2^b} = \frac{2^{16}}{2^b} = 2^{16 - b}

The number of index bits required to address the sets is:

\text{Index bits} = \log_2(S) = 16 - b

Now compute the tag field width:

\text{Tag bits} = \text{Address bits} - (\text{Index bits} + \text{Offset bits})

\text{Tag bits} = 40 - ((16 - b) + b) = 40 - 16 = 24 \text{ bits}

Notice that the block size $b$ cancels out completely. The tag width is 24 bits.

Final answer

Common trap

Assuming the block size must be known, or miscalculating the number of sets by omitting associativity.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.