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

Alternative approach - reason about tag growth directly. Step 1: Every extra way in a set-associative cache merges \(2^L\) direct-mapped lines into a single set, since \(K=2^L\) lines are now searched in parallel for one index. This shrinks the index field by exactly \(L\) bits versus the direct-mapped case, because \(2^{16}\) direct-mapped lines become \(2^{16}/2^L = 2^{16-L}\) sets. Step 2: The address width (32 bits) and block offset (7 bits, fixed by the 128-byte block) never change between the two organizations - only the split between index bits and tag bits changes. Step 3: For the direct-mapped cache, \(32 = M + 16 + 7\), so \(M=9\). Step 4: For the K-way set-associative cache, the index shrinks by L bits to \(16-L\), so the freed-up L bits must go into the tag field instead: \(N = M+L = 9+L\). Step 5: Intuitively, the more ways a cache has, the fewer sets it needs for the same total capacity, so the index gets shorter and the tag gets correspondingly longer by exactly L. Final answer: N=M+L, option A.