Question:medium
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?
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?
Which one of the following options is true?
Show 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.
Updated On: Jul 22, 2026
- \(N = M + L\)
- \(N = M - L\)
- \(N = M + K\)
- \(N = M - K\)
Show Solution
The Correct Option is A
Solution and Explanation
A different way to confirm the relationship is to work with concrete numbers for one value of $L$ and see how the tag field changes when index bits move to associativity, rather than deriving both $M$ and $N$ abstractly at once.
Take $L=2$, so $K=2^2=4$, meaning the cache is 4-way set associative.
Step 1: As before, the block offset uses $\log_2(128)=7$ bits, and the cache holds $2^{23}/2^{7}=2^{16}$ total blocks (lines).
Step 2: For the direct mapped organisation, every line is its own set, so there are $2^{16}$ sets, needing 16 index bits, leaving$$ M = 32-16-7 = 9 \text{ bits of tag.} $$Step 3: For the 4-way set associative organisation with the same total capacity and block size, each set now holds 4 lines instead of 1, so the number of sets drops by a factor of 4:$$ \text{sets} = \frac{2^{16}}{4} = 2^{14} $$which needs only 14 index bits, 2 fewer than the direct mapped case (this matches $L=2$, the exponent of $K$, exactly). The freed 2 index bits are reassigned to the tag field so that tag + index + offset still totals 32 bits:$$ N = 32-14-7 = 11 $$Step 4: Compare $N$ and $M$.
$N-M = 11-9=2$, which is exactly $L$. So $N=M+2=M+L$ for this case, confirming option (A). Repeating the same steps for $L=1$ (2-way, sets $=2^{15}$, tag $=10=9+1$) and $L=3$ (8-way, sets $=2^{13}$, tag $=12=9+3$) gives $N-M=L$ again in both cases, so the relationship $N=M+L$ holds for every $L \in \{1,2,3\}$, not just one special case.$$ \boxed{N=M+L \ \text{(Option A)}} $$
Take $L=2$, so $K=2^2=4$, meaning the cache is 4-way set associative.
Step 1: As before, the block offset uses $\log_2(128)=7$ bits, and the cache holds $2^{23}/2^{7}=2^{16}$ total blocks (lines).
Step 2: For the direct mapped organisation, every line is its own set, so there are $2^{16}$ sets, needing 16 index bits, leaving$$ M = 32-16-7 = 9 \text{ bits of tag.} $$Step 3: For the 4-way set associative organisation with the same total capacity and block size, each set now holds 4 lines instead of 1, so the number of sets drops by a factor of 4:$$ \text{sets} = \frac{2^{16}}{4} = 2^{14} $$which needs only 14 index bits, 2 fewer than the direct mapped case (this matches $L=2$, the exponent of $K$, exactly). The freed 2 index bits are reassigned to the tag field so that tag + index + offset still totals 32 bits:$$ N = 32-14-7 = 11 $$Step 4: Compare $N$ and $M$.
$N-M = 11-9=2$, which is exactly $L$. So $N=M+2=M+L$ for this case, confirming option (A). Repeating the same steps for $L=1$ (2-way, sets $=2^{15}$, tag $=10=9+1$) and $L=3$ (8-way, sets $=2^{13}$, tag $=12=9+3$) gives $N-M=L$ again in both cases, so the relationship $N=M+L$ holds for every $L \in \{1,2,3\}$, not just one special case.$$ \boxed{N=M+L \ \text{(Option A)}} $$
Was this answer helpful?
0
Top Questions on Cache Memory - Direct Mapped and Set Associative Mapping
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems