GATE CS 2017 Set 1 Q54 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To find the length of the $\text{TAG}$ field for the $16$-way set-associative cache, we can analyze how the physical address bits are partitioned in both cache designs.

1. Direct-Mapped Cache

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

• Let the capacity of the cache be $N$ words and the block size be $B$ words.
• The number of cache blocks is $C = \frac{N}{B}$.
• The number of index bits is $\log_2(C) = \log_2\left(\frac{N}{B}\right)$.
• The number of block offset bits is $\log_2(B)$.

Given that $\text{TAG}_{\text{direct}} = 10$ bits, the total physical address size $A$ is:

2. 16-Way Set-Associative Cache

In a $16$-way set-associative cache, the physical address is divided as:

• The number of sets in the cache is $S = \frac{C}{16} = \frac{N}{16B}$.
• The number of index bits is: $$\text{Index}_{\text{set}} = \log_2(S) = \log_2\left(\frac{N}{16B}\right) = \log_2\left(\frac{N}{B}\right) - 4$$
• The block offset remains the same: $\log_2(B)$ bits.

3. Calculating the New TAG Field

Since the physical address size $A$ remains constant:

Equating the two expressions for the physical address size $A$:

Alternative Shortcut:
When moving from a direct-mapped cache (which is $1$-way set-associative) to a $16$-way set-associative cache, the number of sets decreases by a factor of $16$. This reduces the index field by $\log_2(16) = 4$ bits. Since the total address length and block offset remain unchanged, these $4$ bits are added directly to the $\text{TAG}$ field:
$$\text{TAG}_{\text{set}} = \text{TAG}_{\text{direct}} + 4 = 10 + 4 = 14 \text{ bits}$$