Question

The size of the physical address space of a processor is \(2^{32}\) bytes.
The capacity of a cache memory unit is \(2^{23}\) bytes and the cache block size is 128 bytes.
The cache can be direct-mapped or \(K\)-way set-associative, where \(K=2^L\) and \(L\in\{1,2,3\}\).
Let the TAG field contain \(M\) bits for the direct-mapped cache and \(N\) bits for the set-associative cache.
Which one of the following options is true?

• A. 𝑁= 𝑀+ 𝐿
• B. 𝑁= 𝑀−𝐿
• C. 𝑁= 𝑀+ 𝐾
• D. 𝑁= 𝑀−𝐾

Hint:

Total address bits are fixed at 32 = tag + index + offset. The offset (7 bits) never changes; moving from direct-mapped to K-way set-associative shrinks the index by L bits, so the tag grows by exactly L bits.

Answer 1

The Correct Option is A

Step 1: Compute the address width. The physical address space is \(2^{32}\) bytes, so the address is 32 bits wide.

Step 2: Compute offset bits. Block size = 128 = \(2^{7}\) bytes, so the block offset field is 7 bits in both cache organizations.

Step 3: Direct-mapped cache - find M. Number of cache lines = cache size / block size = \(2^{23}/2^{7} = 2^{16}\), so the line/index field is 16 bits. Tag bits \(M = 32-16-7 = 9\).

Step 4: Set-associative cache - find N. With \(K=2^{L}\) ways, number of sets = cache size / (block size times K) = \(2^{23}/(2^{7}\times 2^{L}) = 2^{16-L}\), so the set-index field is \((16-L)\) bits. Tag bits \(N = 32-(16-L)-7 = 9+L\).

Step 5: Relate N and M. Since \(M=9\), we get \(N = M+L\).

Final Answer: \(\boxed{N = M+L \text{ (Option A)}}\)