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. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a \(K\)-way set-associative cache, where \(K = 2^{L}\) and \(L \in \{1,2,3\}\). Let the length of the TAG field be \(M\) bits for the direct mapped cache, and \(N\) bits for the set-associative cache.

Which one of the following options is true?

• A. \(N = M + L\)
• B. \(N = M - L\)
• C. \(N = M + K\)
• D. \(N = M - K\)

Hint:

Work out the number of bits used for block offset, set index and tag for the direct mapped cache and for the K way set associative cache separately, then compare the tag widths.

Answer 1

The Correct Option is A

Step 1: Find the block offset bits.
Block size is 128 bytes \(=2^{7}\) bytes, so the block offset field needs\[ \text{offset bits} = \log_2(128) = 7 \]This is the same for both cache organisations, since the block size does not change.
Step 2: Find the total number of cache lines (blocks) in the cache.
Cache capacity is \(2^{23}\) bytes and each block holds \(2^7\) bytes, so the number of blocks the cache can hold is\[ \frac{2^{23}}{2^{7}} = 2^{16} \]Step 3: Compute the tag length \(M\) for the direct mapped cache.
In a direct mapped cache, each of the \(2^{16}\) cache lines forms its own set, so the number of sets equals the number of lines, \(2^{16}\), and the set index field needs 16 bits. The physical address is 32 bits wide, split into tag, index and offset, so\[ M = 32 - 16 - 7 = 9 \]Step 4: Compute the tag length \(N\) for the \(K\)-way set associative cache.
With \(K=2^{L}\) ways per set, the \(2^{16}\) lines are grouped into\[ \text{number of sets} = \frac{2^{16}}{2^{L}} = 2^{16-L} \]so the set index field needs \(16-L\) bits, and\[ N = 32 - (16-L) - 7 = 32 -16 + L - 7 = 9 + L \]Step 5: Relate \(N\) to \(M\).
Since \(M=9\), substituting gives\[ N = 9 + L = M + L \]Step 6: Check the remaining options.
Option (B) \(N=M-L\) would mean the tag gets shorter as associativity increases, but increasing \(K\) reduces the number of sets, which means the index field shrinks and the tag field must grow to keep the total address width fixed at 32 bits, so (B) has the wrong sign. Options (C) and (D) mix the tag length with \(K\) itself (an integer such as 2, 4 or 8) rather than with the bit count \(L\); since \(M\) and \(N\) are measured in bits while \(K\) is a count of ways, adding or subtracting \(K\) directly is dimensionally inconsistent with how tag, index and offset fields are computed, and does not match the value derived in Step 4 for any \(L \in \{1,2,3\}\). Only option (A) matches the derivation exactly for every valid value of \(L\).\[ \boxed{N = M + L \ \text{(Option A)}} \]