4.1.9 · D5Computer Architecture (Deep)
Question bank — Cache organization — direct-mapped, n-way set associative, fully associative
This bank targets the boundary cases the topic invites: the extremes ( and ), the sign of "more associativity", the difference between where a block may live and how you find it, and the exact miss type each design does or does not remove.
True or false — justify
TRUE or FALSE: A direct-mapped cache is just a 1-way set-associative cache.
TRUE. Direct-mapped is the case , so each set holds exactly one line — every formula (, index ) collapses to the direct-mapped rules with no special-casing needed.
TRUE or FALSE: A fully associative cache never has any misses.
FALSE. It removes only conflict misses; the first-ever touch of a block is still a compulsory (cold) miss, and a working set larger than the cache still causes capacity misses.
TRUE or FALSE: Increasing associativity (fixed total size) makes the tag larger.
TRUE. Fixed means more ways fewer sets fewer index bits, and since , the tag absorbs exactly the bits the index gave up.
TRUE or FALSE: A fully associative cache needs no tag bits because a block can go anywhere.
FALSE. It is the opposite — with there is no index to pre-select a set, so the tag must encode the entire block number; fully associative has the largest tags of all.
TRUE or FALSE: Direct-mapped caches still need a replacement policy like LRU.
FALSE. A block has exactly one legal slot (), so there is never a choice about what to evict — a replacement policy only becomes meaningful once .
TRUE or FALSE: The block offset field depends on the associativity.
FALSE. Offset depends only on the block size ; changing (ways) trades bits between index and tag but leaves the offset untouched.
TRUE or FALSE: Two different memory blocks can be present in the same set at the same time in a 4-way cache.
TRUE. A set holds lines, so up to four distinct blocks that all map to that set can coexist — that is precisely the mechanism that dissolves conflict misses.
TRUE or FALSE: The valid bit and the tag match are two independent conditions for a hit.
TRUE. A hit requires BOTH (valid ) AND (stored tag address tag); a leftover tag from a flushed line could match by accident, so the valid bit guards against reading stale garbage.
TRUE or FALSE: More sets always means a larger cache.
FALSE. Total capacity is ; you can raise while lowering (or ) and keep size fixed — sets alone say nothing about size.
Spot the error
Spot the error: "Fully associative caches are fast because they need no index computation."
The missing-index part is true, but it is slow to search, not fast — with no index to narrow things down it must fire tag comparators in parallel on every access, which is exactly why it is hardware-expensive.
Spot the error: "Going from direct-mapped to 4-way doubled my tag by 2 bits, so the cache got bigger."
The tag grew because index bits moved into the tag (fixed ), not because capacity grew — data capacity is unchanged; only the per-line tag-storage overhead increased.
Spot the error: "Blocks 0 and 4 collide in a 4-line direct-mapped cache because they are far apart in memory."
They collide because both have the same low index bits: , so both map to set 0 — collision is about matching index bits, not about the numeric distance between blocks.
Spot the error: "Since fully associative has zero conflict misses, it always has the lowest total miss rate."
Not necessarily — for a given trace a smart direct-mapped layout can occasionally tie or beat it on capacity/compulsory misses, and fully associative's benefit is only on the conflict component; it also costs far more hardware for that benefit.
Spot the error: "We use the high bits of the block number for the index so that neighbouring blocks land in the same set."
We use the low block-number bits for the index precisely so consecutive blocks spread across different sets, which helps spatial locality — using high bits would clump neighbours together and worsen conflicts.
Spot the error: "Bigger blocks always reduce the miss rate because they pull in more neighbours."
Only up to a point — bigger blocks mean fewer blocks fit in a fixed cache, raising conflict/capacity misses and wasting bandwidth when locality is weak, so there is an optimal block size, not a monotonic win.
Spot the error: "An -way cache needs comparators, one per set."
It needs comparators — one per line within the selected set — because only that one set is searched per access; the number of sets has nothing to do with comparator count.
Why questions
Why does restricting where a block may live make the cache cheaper and faster?
Fewer legal slots means fewer stored tags to compare each access, so you need fewer comparators and less parallel-search logic — the whole cost of a lookup scales with , the number of candidate lines.
Why does a fully associative cache have no index bits ()?
With there is only one set, and ; since there is nowhere to pre-select, the address spends none of its bits choosing a set and all of them (minus the offset) on the tag.
Why must the tag hold the entire block number in a fully associative cache?
Because no bits were spent on an index, nothing about the block's identity is implied by where it sits — the tag alone must fully identify the block, so it equals the whole block number.
Why does associativity eliminate conflict misses but not capacity misses?
Conflict misses come from too many blocks fighting for one set; giving a set more ways removes that fight. Capacity misses come from the whole working set exceeding total capacity — more ways in a set does not add total storage, so those remain.
Why is no replacement policy needed in a direct-mapped cache?
Every block has exactly one legal slot, so on a miss there is never any decision about which line to evict — the target line is forced, making a policy meaningless.
Why does raising associativity increase tag-storage overhead even when data capacity is unchanged?
More ways fewer sets fewer index bits a wider tag; and that wider tag must be stored per line, so the SRAM spent on tags grows across all lines.
Edge cases
Edge case: What happens to the index field when (all blocks in one set)?
, so — the index field vanishes entirely, which is the definition of fully associative.
Edge case: What happens to the tag field when (direct-mapped) with maximum sets?
gives the largest possible index , so the tag is at its smallest — direct-mapped has the shortest tags and the fewest comparators (just one).
Edge case: If the block size equals the whole cache size, how many blocks fit?
Exactly one (), so — there is a single line and the "organization" distinction disappears; every access to a different block is a miss with heavy eviction.
Edge case: A cache has one set and one way (, ). Is it direct-mapped or fully associative?
Both descriptions coincide — with a single line there is one legal slot (direct-mapped view) which is also "anywhere" (fully associative view); the labels only diverge once .
Edge case: With 1-byte blocks, what is the offset field and why?
— no offset bits, because a 1-byte block has only one byte to select, so nothing needs indexing inside the block.
Edge case: The access trace is on a 4-line direct-mapped cache — what miss rate results?
100% misses: both block 0 and block 4 map to set 0 () and evict each other every access; the same trace on a 2-way (2-set) cache lets both live in set 0's two lines, giving only 2 cold misses then all hits.
Recall One-line summary of the whole trap family
Almost every trap confuses where a block may live (placement, set by index) with how you find it (search, tag comparison) — keep those two separate and the misconceptions dissolve.