5.4.2 · D5Memory Hierarchy & Caches
Question bank — Cache organization (direct-mapped)
Before starting, remember the address split from the parent note: an address is carved into Tag (which memory block), Index (which cache line), and Block Offset (which byte inside the block). High bits → low bits = T → I → C.
True or false — justify
Direct-mapped means each memory block can live in exactly one cache line.
True — the index bits force a single line; there is no choice, unlike set-associative where a block may go in any way of its set (see Set-Associative Caches).
Direct-mapped means each cache line can only ever hold one specific memory block.
False — one line is the target of many blocks (all blocks sharing that index). The tag decides which of those competing blocks is resident right now.
Two addresses with the same index always collide in the cache.
False — if they also share the same tag they are the same block and both hit; collision only happens when index matches but tag differs.
Two addresses with the same tag always map to the same cache line.
False — same tag but different index bits go to different lines; the tag alone does not locate anything.
Increasing the number of index bits always reduces conflict misses.
False in practice — index bits are pinned by , so you cannot add them without growing the cache or shrinking blocks (which hurts spatial locality).
A cold (compulsory) miss can be avoided by making the cache larger.
False — the first-ever reference to a block must miss regardless of size; only prefetching or larger blocks (spatial locality) can hide it.
If the valid bit is 0, the tag comparison result does not matter.
True — an invalid line holds garbage; the hit condition is , so forces a miss before the tag is even trusted.
Doubling the block size while keeping cache size fixed reduces the number of cache lines.
True — lines cache size block size, so bigger blocks mean fewer lines, hence fewer index bits and more tag bits.
Two consecutive byte addresses always land in the same cache line.
False — they usually do, but a boundary between two blocks (offset rolls over from to ) increments the index, sending them to different lines.
The tag stored in a line is redundant because the index already identifies the line.
False — the index identifies the line, but many blocks share that index; the tag is the only thing distinguishing which of those blocks is present.
Spot the error
"To find data, first search all the tags for a match, then jump to that line."
Wrong order — index bits go straight to the line (no search), then a single tag compare confirms. Searching all tags is associative-cache behaviour, not direct-mapped.
"The block offset tells you which memory block you're accessing."
The offset selects a byte within a block; the block itself is identified by tag+index (the block address). Offset never affects which line is chosen.
"A conflict miss means the cache ran out of space."
No — conflict misses happen even in a mostly-empty cache; the problem is two live blocks mapping to the same line, not total capacity being exhausted.
"Address 0x0D and 0x4D differ, so they use different cache lines."
They share the same index bits (both index 3 in the parent's 16-byte cache), so they fight over the same line; only their tags differ, causing thrashing.
"Storage overhead is just the tag bits, so it's negligible."
You must also count the valid bit (and any dirty/coherence bits from Cache Write Policies); overhead is (tag + valid + …) over the data bits, which grows as blocks shrink.
"Since direct-mapped uses modulo, block maps to line ."
Modulo wraps — block , so it maps to line 0, colliding with block 0. That wrap-around is exactly why tags exist.
"If a line's tag matches, it's automatically a hit."
Only if the valid bit is also 1 — a freshly powered-up cache may have matching-looking garbage tags in invalid lines, which must still miss.
Why questions
Why does the index come from the middle bits, not the high bits?
Middle (block-address low) bits change most often as you stream through consecutive blocks, so they spread nearby blocks across different lines, maximizing usable lines and reducing conflicts.
Why is the offset taken from the lowest bits?
Consecutive bytes within a block differ only in their lowest bits; using the low bits as offset makes bytes index cleanly inside one block via .
Why is direct-mapped faster per access than set-associative?
It needs exactly one tag comparison at one known line (no multi-way search), so there is no comparator array or multiplexer to pick a winner — see the trade-off in Set-Associative Caches.
Why can a program with a perfectly-sized working set still thrash?
If two hot addresses happen to share an index, direct-mapping forces them into one line; they evict each other every access even though total capacity is ample.
Why doesn't the tag need to store the index bits too?
You already know the index (you used it to arrive at the line), so re-storing it would be redundant; the tag only needs the bits above the index to fully identify the block.
Why are Cache Replacement Policies like LRU irrelevant to a pure direct-mapped cache?
Each block has exactly one legal line, so on a conflict there is only one possible victim — no policy is needed to "choose" what to evict.
Edge cases
What happens on the very first access to any block after power-on?
Every line has , so the tag compare is skipped and it is a compulsory (cold) miss regardless of the tag value; the block is fetched and set to 1.
What if block size equals the whole cache size (one line, )?
There is exactly one line; every block maps to it, so the cache degenerates to a single-block buffer and any two distinct blocks thrash — index has 0 bits.
What if block size is 1 byte ()?
There is no offset field; every byte is its own block, so you lose spatial-locality prefetching and pay maximal tag overhead per byte of data.
What if the whole address is index+offset with zero tag bits?
This means the cache is as large as the entire address space, so no two blocks ever collide — the tag comparison becomes trivially always-true and could be omitted.
Address 0x2F then 0x30 in the parent's 16-byte/4-byte cache — same line?
No — 0x2F is offset 3 of index 3's block; 0x30 rolls into the next block (index 0), so the index changes and they land in different lines despite being adjacent.
What does flushing/invalidating a line change without touching data?
It clears the valid bit to 0, so the next access misses and refetches; the stale data bytes stay physically present but are ignored because gates the hit.
If you halve the cache size but keep block size, what shifts in the address split?
Index loses one bit (half as many lines), and that bit moves up into the tag, so tags grow by one bit and more blocks now share each line — see impact in Cache Performance Metrics.
Recall One-line self-test
If someone says "same index, therefore a miss," what's your instant correction? Correction ::: "Same index only sets up a potential collision; it's a miss only if the tags differ (and it's a hit if tags match and the line is valid)."