Consider a system with the following cache configuration:
Block size = 128 bytes
Physical memory size = 2²³ bytes
Cache size = 2¹³ bytes.
Two cache organizations are used:
1. A direct-mapped cache with tag size = m bits.
2. Ak-way set associative cache with tag size = n bits where k = 2L, L ∈ {1,2,3,....}.
Which of the following relations between n and m is / are correct?

The correct option is n = m + L.

Step-by-step Explanation:

1. Determine the address bits from the physical memory and block size:
The physical memory size is given as 2²³ bytes. Therefore, the total number of physical address bits is 23 bits.
The cache block size is 128 bytes, which can be written as:

$\text{Block size}=128\text{bytes}=2^7\text{bytes}$

This means the block offset requires 7 bits.

2. Direct-Mapped Cache Configuration (Tag size = m bits):
The cache size is given as 2¹³ bytes. The number of blocks in the cache is calculated as:

$\text{Number of blocks}=\frac{\text{Cache size}}{\text{Block size}}=\frac{2^{13}}{2^7}=2^6$

In a direct-mapped cache, the number of index bits is log₂(Number of blocks) = 6 bits.
The physical address structure for a direct-mapped cache is partitioned as:
Physical Address (23 bits) = Tag (m bits) + Index (6 bits) + Block Offset (7 bits)

$m=23-(6+7)=10\text{bits}$

3. k-way Set Associative Cache Configuration (Tag size = n bits):
Here, the associativity is k = 2^L. The number of sets in the cache is:

$\text{Number of sets}=\frac{\text{Number of blocks}}{k}=\frac{2^6}{2^L}=2^{6-L}$

Thus, the set index requires 6 - L bits.
The physical address structure for a set-associative cache is partitioned as:
Physical Address (23 bits) = Tag (n bits) + Set Index (6 - L bits) + Block Offset (7 bits)

$n=23-(6-L+7)$

$n=23-13+L$

$n=10+L$

4. Relating n and m:
Since m = 10, we can substitute it into the expression for n:

$n=m+L$

This matches the correct relation.