5.4.4 · D5Memory Hierarchy & Caches
Question bank — Cache line size and tags
Before the traps, look at one picture that fixes the whole mental model in your head:
The address bar above is sliced left-to-right into three coloured chunks. The magenta Tag on the left is the widest — it is everything not used for lookup. The violet Index in the middle points at one row of the cache grid. The orange Offset on the right points at one byte inside that fetched row. Notice the offset is on the low (right) end: consecutive byte addresses differ only there, so a whole line shares one tag+index — that is spatial locality made visible.
A quick shared vocabulary so every answer lands (all built in the parent):
True or false — justify
True or false: A cache miss on byte X means byte X+1 is also guaranteed to be a miss.
False. X and X+1 usually sit in the same line, so once X's line is fetched, X+1 is a hit — this is exactly why lines are multi-byte (see 3.1.04-Spatial-locality).
True or false: The offset bits are compared against a stored offset to detect a hit.
False. Only the tag is compared; the offset never participates in hit/miss — it just selects which byte to return after a hit.
True or false: Two different addresses can share the same index yet never collide in the cache.
True. In a set-associative cache the same set holds multiple ways, so two blocks with equal index can coexist as long as a free way (or a victim) is available.
True or false: Doubling the cache size while keeping line size fixed increases the number of tag bits.
False. Doubling capacity adds one index bit, so tag bits decrease by one — you need fewer bits to distinguish blocks because more of the address is now "which slot".
True or false: A valid bit is only needed for write-back caches.
False. Every cache needs a valid bit to know whether a slot holds real data or leftover garbage from power-on; the dirty bit is the one specific to write-back (see 5.4.08-Write-policies).
True or false: Making cache lines larger always lowers the miss rate.
False. Past a sweet spot you fetch bytes you never touch and shrink the line count, raising conflict misses and miss penalty — for typical general-purpose workloads the balance point measured across benchmarks (e.g. SPEC) tends to land near 64 bytes, but streaming or pointer-chasing workloads favour different sizes.
True or false: Tag bits are a fixed property of an address, independent of the cache.
False. The split point between tag/index/offset is chosen by the cache's size, line size, and associativity — the same address has different tags in different caches.
True or false: For a fixed cache and line size, direct-mapped and 2-way set-associative use the same number of offset bits.
True. Offset depends only on line size (); associativity changes the index/tag boundary, not the offset.
Spot the error
"64-byte lines need 7 offset bits because ." — what's wrong?
, not , so it's 6 offset bits. The exponent, not the value, gives the bit count.
"A 32 KiB, 64-byte-line, direct-mapped cache has 32768/64 = 512 sets, so it needs 512 index bits." — spot the slip.
You need index bits, not 512. Index bits count how many bits address the slots, not the slot count itself.
"To find a byte, hardware first uses the tag to pick a slot, then the index to confirm the data." — fix the roles.
Reversed. The index picks the slot (fast, direct lookup), then the tag confirms the block is correct.
"Set-associative caches drop the tag field since multiple blocks share a set." — what's the error?
They keep the tag and in fact need it more — each way in a set stores its own tag so the comparators can tell which way (if any) holds your block.
"Halving line size from 64 to 32 bytes reduces tag overhead per line." — where's the mistake?
It increases overhead. Smaller lines mean more lines total, each carrying its own (now larger) tag, so metadata as a fraction of capacity goes up.
"Since the offset is the low bits, changing the byte you want changes the index." — spot the confusion.
Only if you cross a line boundary. Within one line the index and tag are identical; the offset alone varies, which is the whole point of grouping neighbors.
"A hit requires the tag to match AND the valid bit to be 0." — correct the logic.
A hit requires the tag to match AND the valid bit to be 1 (line holds real data). Valid = 0 means the slot is empty, forcing a miss.
Why questions
Why does the offset live in the low bits of an address rather than the high bits?
Because consecutive byte addresses differ only in their low bits, so putting the offset low keeps a whole contiguous block sharing one tag+index — that is what makes spatial locality translate into cache hits.
Why compare a tag at all instead of just trusting the index?
Many memory blocks map to the same index (the index is only a few bits), so the tag is the collision check that answers "is this the block I stored, or a different one that happens to share the slot?"
Why is line size always a power of two?
So the byte offset is an exact whole number of bits (); a non-power-of-two would leave the address split misaligned and require division instead of a clean bit-slice.
Why do larger lines reduce total tag storage even though each tag is wider?
Fewer lines dominate: doubling halves the line count while adding just one bit per tag, so total metadata bytes fall — more data amortizes each tag.
Why can a 4 KiB cache have more tag bits than a 16 KiB cache with the same line size?
The smaller cache has fewer slots, so fewer index bits, so more of the address must serve as tag — tag width grows as index width shrinks.
Why doesn't the CPU just fetch exactly the one byte it asked for?
The memory bus and DRAM burst are optimized for wide transfers, and locality means neighbors are likely wanted soon — fetching a full line pays one slow access but serves many future requests fast.
Edge cases
What are the tag bits when index bits = 0 (a fully associative cache)?
With no index field, — every non-offset bit becomes tag, and hardware must compare that tag against every line in parallel.
What happens to the offset field if line size is exactly 1 byte?
, so there is no offset — every byte is its own line, giving maximum line count but zero spatial-locality benefit and huge tag overhead.
If the whole cache is one single line (), how many index bits are there?
Zero index bits: one slot means no selection needed, so the address is just tag + offset — effectively a trivial fully-associative cache of size one.
An access lands with offset = 0 and the requested data spans into the next line. What must happen?
The access crosses a line boundary, so the cache resolves two lookups (two index/tag pairs) — one per line — which is why unaligned accesses can cost extra.
Right after power-on, every tag comparison "matches" by luck. Why is it still a miss?
The valid bit is 0 for uninitialized slots, so the hardware ignores the accidental tag match and forces a miss — valid gates the comparison.
Two addresses differ only in their tag bits. Do they map to the same slot?
Yes — identical index and offset means the same slot, so they conflict: only one can occupy the slot at a time, causing conflict misses (see 5.4.05-Cache-miss-types).
If associativity equals the total number of lines, what does the index degenerate to?
Sets , so index bits — the cache becomes fully associative and the index field vanishes into the tag.
Connections
- Cache line size and tags — the parent note these traps stress-test.
- 5.4.01-Cache-fundamentals — foundation for the whole tag/index/offset model.
- 5.4.02-Direct-mapped-caches — where the one-tag-per-slot comparison lives.
- 5.4.03-Set-associative-caches — why the index becomes a set index and tags multiply.
- 5.4.05-Cache-miss-types — conflict vs. compulsory misses referenced in the edge cases.
- 5.4.08-Write-policies — the dirty bit distinction from the valid-bit traps.
- 6.2.01-Virtual-memory-pages — page tables reuse the same field-split idea.
- 3.1.04-Spatial-locality — the reason lines are wide, underpinning the "why" section.
- Hinglish version — same ideas in Hinglish.