Question 54

Let $A$ be the number of bits in the physical address.
The cache has capacity $N$ words and block size $B$ words.
The number of word-offset bits within a block is $\log_2 B$.

1. Direct Mapped Cache:

• The number of blocks (lines) is $N / B$.
• In a direct mapped cache, each line forms its own set, so the number of sets is $N / B$.
• The number of index bits is $\log_2(N / B)$.
• The physical address is partitioned as:
  $$\text{TAG} + \text{Index} + \text{Offset} = A$$
  $$\text{TAG}_{\text{DM}} = A - \log_2(N / B) - \log_2 B = A - \log_2 N = 10\text{ bits}$$

2. 16-way Set-Associative Cache:

• Associativity $P = 16$.
• The number of sets is:
  $$\text{Sets} = \frac{N / B}{16}$$
• The number of set-index bits is:
  $$\text{Index}_{\text{SA}} = \log_2\left(\frac{N / B}{16}\right) = \log_2(N / B) - \log_2(16) = \log_2(N / B) - 4$$
• Because the physical address width $A$ and block size $B$ remain the same, decreasing the index field by 4 bits increases the TAG field by 4 bits:
  $$\text{TAG}_{\text{SA}} = \text{TAG}_{\text{DM}} + 4 = 10 + 4 = 14\text{ bits}$$