Q. Consider a 4-way set-associative cache of size 128 KB, organized into…
Q. Consider a 4-way set-associative cache of size 128 KB, organized into 32-byte blocks. The CPU generates a 32-bit physical address, and besides the tag, each cache line carries 2 valid bits and 1 dirty bit.
The following statements are given:
1. Each line in a cache set contains a 17-bit tag.
2. The cache controller maintains a tag directory of 20 Kbits.
3. The main memory address 0x000A1B3C maps to set number 25 in the cache.
4. Each cache set can potentially map 8 different main memory blocks.
Enter the numbers of all statements that are true, concatenated in ascending order _________ .
Answer: 1 — Concept: For an N-way set-associative cache — total lines = cache size / block size; number of sets = total lines / N; offset bits = log₂(block size); index…
Attempted by 19 students.
Show answer & explanation
Correct answer: 1
Concept: For an N-way set-associative cache — total lines = cache size / block size; number of sets = total lines / N; offset bits = log₂(block size); index bits = log₂(number of sets); tag bits = address width − index bits − offset bits. The tag-directory holds one entry per cache LINE (not per set), each entry being tag bits + status bits (valid + dirty). A given memory address's set index is fixed by (address >> offset bits) mod (number of sets); the number of blocks a set can HOLD at once equals the associativity (the "N" in N-way) — nothing else.
Application: Cache size = 128 KB, block size = 32 B, associativity = 4, address width = 32 bits.
Total cache lines = 128 KB / 32 B = 131072 / 32 = 4096 lines.
Number of sets = 4096 lines / 4 ways = 1024 sets.
Offset bits = log2(32) = 5 bits; Index bits = log2(1024) = 10 bits.
Tag bits = 32 − 10 − 5 = 17 bits → Statement 1 ("17-bit tag") is TRUE.
Per-line overhead = 17 (tag) + 2 (valid) + 1 (dirty) = 20 bits. Tag-directory size = 4096 lines × 20 bits = 81,920 bits = 80 Kbits (81920/1024). Statement 2 claims 20 Kbits → FALSE (20 Kbits only results from multiplying the number of SETS, 1024, by 20 — not the number of lines).
Address 0x000A1B3C = 662,332 in decimal. Block number = ⌊662332 / 32⌋ = 20,697. Set index = 20697 mod 1024 = 217. Statement 3 claims set 25 → FALSE.
A 4-way set-associative cache set holds exactly 4 blocks at a time (one per way), by definition of "4-way" — not 8. Even under the loosest reading of "map" (every main-memory block that could alias to this set), that count is 217 = 131072, still not 8. Statement 4 claims 8 → FALSE either way.
Cross-check: With 17 tag bits, each set index can distinguish 217 = 131072 competing blocks — consistent with a 4 GB (232 B) address space split into 1024 sets of 32 B blocks (232 / (1024 × 32) = 131072 = 217), confirming the tag width. The set index for Statement 3 also checks out via direct bit-extraction: 662332 in binary is 10100001101100111100; the lowest 5 bits (offset) are 11100 = 28, and the next 10 bits (index) are 0011011001 = 217 — the same 217 obtained by division, confirming Statement 3 is false.
Result: Only Statement 1 is true, so the concatenated answer (ascending order) is 1.
A video solution is available for this question — log in and enroll to watch it.