Set-associative and fully associative caches: Question bank

This is a question bank for the parent note Set-associative and fully associative caches (index 5.4.3). Every item is a one-line reveal: read the prompt, answer out loud, then check. The answers give reasoning, not just a verdict — that reasoning is the whole point.

Prerequisite ideas you should already have: Direct-mapped caches, Conflict misses vs capacity misses, Cache replacement policies, Cache performance metrics.

Symbols used on this page (read first)

The whole page leans on four letters. Even if you met them in the parent note, pin them down here so no reveal uses an undefined symbol.

The one relation that ties them together, and that half this page rests on:

The address is then chopped into three fields whose bit-widths depend only on $S$ and $B$ . Figure s01 is the picture to keep in your head the whole way down.

True or false — justify

A "way" is one line slot per set, and a "set" is a group of ways selected by the index bits. Keep those two straight before you start. Figure s02 draws a 4-way cache so you can see a set as a row and a way as a column.

A 4-way set-associative cache stores 4× more data than a direct-mapped cache of the same block size.

False. Associativity (

N

) is where a block may go, not how much fits. Since

C = S \times N \times B

, a 64 KB 4-way cache and a 64 KB direct-mapped cache hold the same 64 KB — the 4-way one just has 4× fewer sets, each holding 4 lines.

Increasing associativity always lowers the miss rate.

Mostly true but with a ceiling. More ways removes conflict misses, but once conflicts are gone you only face capacity and compulsory misses, which associativity cannot fix — see Conflict misses vs capacity misses. Beyond ~8 ways the improvement is usually negligible.

Increasing associativity always lowers the average memory access time.

False. More ways means more parallel comparators and a bigger tag mux, which lengthens hit time. If hit time grows faster than the miss rate shrinks, AMAT (see Cache performance metrics) can get worse.

A fully associative cache has zero conflict misses.

True. A conflict miss is an eviction forced by limited placement. With any-block-anywhere placement, a block is only evicted when the whole cache is full — that's a capacity miss, not a conflict miss.

A fully associative cache has zero misses.

False. It still suffers compulsory misses (first-ever touch of a block) and capacity misses (working set exceeds total size). Associativity only kills the conflict category.

A direct-mapped cache is just a 1-way set-associative cache.

True. With

N = 1

each set holds one line, so the index picks exactly one slot and there is no choice — which is precisely the direct-mapped rule.

A fully associative cache is an

S = 1

set-associative cache.

True. One set containing all

C / B

lines means no index bits and every line is a candidate — that is the definition of fully associative.

The set index field is part of the address stored in the tag.

False. The index selects the set; it is implied by where the block sits, so it is never stored. Only the tag bits are stored to disambiguate blocks within that set.

In a fully associative cache the tag is larger than in a same-size set-associative cache.

True. With no index bits, all the bits that would have been index bits are absorbed into the tag, so the tag must uniquely identify the block among all of memory that maps to the (single) set.

LRU can be implemented with 1 bit per set in a 2-way cache.

True. With only two ways, one bit records which of the two was used more recently; on a hit you set it, on a miss you evict the other. Higher associativity needs more state — see the pseudo-LRU tree in figure s04.

Replacement policy matters in a direct-mapped cache.

False. A block has exactly one legal slot, so there is no choice to make — the incumbent is always evicted. Policies only matter when

N \geq 2

. See Cache replacement policies.

Doubling associativity while halving the number of sets keeps total capacity fixed.

True. Capacity is

C = S \times N \times B

. If

N

doubles and

S

halves, the product is unchanged, so the same total bytes remain.

Spot the error

Each statement below contains a mistake. Name it and correct it.

"64 KB, 64 B blocks, 4-way → sets = C/(B) = 1024."

Forgot to divide by N. Sets

= C / (B \cdot N) = 65536/ (64 \cdot 4) = 256

, not 1024. Dividing only by

B

gives the total lines (

C / B = 1024

), not the number of sets.

"Fully associative caches need index bits to pick which line to search."

There is no index. With

S = 1

we get

i = lo g_{2} 1 = 0

index bits; every line is searched in parallel, so the address is only Tag | Offset.

"A 2-way cache needs 2 comparators, so it costs twice the hardware of direct-mapped."

The comparators aren't the whole cost. It's more than 2× just for comparators, but the total isn't simply "twice" — there's also replacement state, a wider tag mux, and way-select logic. "2 comparators" ≈ correct; "twice the total cost" is an oversimplification.

"With 256 sets you need log₂(256) = 16 index bits."

$lo g_{2} 256 = 8$ , not 16. Because

2^{8} = 256

. The writer likely confused it with a byte count.

"Increasing block size

B

always reduces the number of index bits."

Only if $C$ and $N$ stay fixed — here is the chain. Start from

S = C / (B \cdot N)

, so

i = lo g_{2} S = lo g_{2} (C / (B \cdot N)) = lo g_{2} C - lo g_{2} B - lo g_{2} N

. Doubling

B

adds 1 to

lo g_{2} B

, which subtracts 1 from

i

only when $C$ and $N$ are held constant. If capacity grows with

B

(or

N

changes),

i

need not drop — figure s03 traces this.

"Tag + index + offset can exceed the address width if the cache is large enough."

Impossible — the fields partition the $A$ bits. By construction

t = A - i - b

, so

t + i + b = A

exactly, no matter how big the cache is. Toy example:

A = 8

B = 4 \Rightarrow b = 2

S = 4 \Rightarrow i = 2

, hence

t = 8 - 2 - 2 = 4

and

4 + 2 + 2 = 8

. Making the cache bigger just moves bits from tag to index; the sum never leaves 8.

"LRU always beats every other policy, so real hardware always uses true LRU."

LRU usually wins, but true LRU is expensive for high associativity. True LRU for

N

ways needs to order all

N

lines (

\approx N lo g_{2} N

bits per set); real 8-way+ caches use the cheap pseudo-LRU tree in figure s04 (only

N - 1

bits) or even random, trading a tiny miss-rate loss for far less state.

"A hit requires the tag to match; the valid bit doesn't matter."

Both are required. A stale/uninitialised line may hold a matching tag by accident; the valid bit = 1 confirms the line actually holds real data. Hit = tag match AND valid.

Why questions

Why do set-associative caches compare all N tags in parallel rather than one at a time?

To keep hit time at one cycle. Sequential comparison would multiply hit latency by

N

, defeating the purpose of a fast cache — parallel comparators pay area/power to buy speed. See the comparator fan-out in figure s02.

Why does a fully associative cache scale badly to large sizes?

It needs one comparator per line (

C / B

of them) plus a big priority encoder. For a large cache that's hundreds or thousands of comparators — far too much area and power, which is why it's reserved for tiny structures like the Translation Lookaside Buffer (TLB).

Why is the tag needed at all if the index already selects the set?

The index only narrows you to a set; many different memory blocks map to the same set (they share index bits but differ elsewhere). The tag stores those distinguishing high bits so you can tell which block actually sits in each way.

Why does LRU exploit temporal locality?

Temporal locality says a recently-used block is likely to be reused soon. LRU evicts the least recently used line — the one least likely to be needed next — minimising future misses.

Why do L1 caches favor low associativity while L3 favors high?

L1 is on the critical path for speed, so it keeps associativity low to keep hit time tiny. L3 is farther from the core where a slower hit is tolerable, so it spends associativity to cut its miss rate and reduce costly main-memory trips.

Why doesn't a direct-mapped cache need a replacement policy but a fully associative one does?

Direct-mapped gives each block exactly one home, so "which to evict" is predetermined. Fully associative gives every block many homes, so on a miss the hardware must choose a victim — that choice is the policy.

Why can two programs with the same total data size see very different miss rates on the same cache?

Miss rate depends on access pattern, not just data size. Strided or aliasing patterns can pile many blocks onto one set (conflict misses in low-associativity caches), while a friendlier pattern spreads them out. Associativity is a defense specifically against the bad patterns.

Edge cases

What happens when N equals the total number of cache lines (

N = C / B

You get exactly

S = 1

set — a fully associative cache. This is the upper limit of associativity; you can't go higher.

What is the set index field when

S = 1

Zero bits.

lo g_{2} 1 = 0

, so there is no index — the address is purely Tag | Offset, consistent with fully associative.

If block size

B

equals the whole cache size

C

(with

N = 1

), how many sets are there?

One set with one line:

S = C / (B \cdot N) = C / (C \cdot 1) = 1

. The entire cache is a single block — a degenerate case with no useful associativity or indexing.

In a 2-way cache, both ways of a set are invalid (cold). A new block arrives — which way is filled and does the policy matter?

Either empty way is filled first; the replacement policy only kicks in once both ways are valid. On a cold set, "fill an invalid line" takes priority over LRU/FIFO.

Two addresses have identical tag and identical index but different offset. Same block or different?

Same block. Tag+index identify the block; the offset only picks a byte within it. So they hit the same cache line and, on a hit, both are served from it.

If every access in a loop maps to the same set and the set is 2-way, but three distinct blocks are cycled, what miss pattern appears?

Thrashing — each of the three blocks repeatedly evicts one of the other two because only 2 can coexist. These are conflict misses; a 3-way (or more) set, or full associativity, would eliminate them.

What is the smallest associativity that can hold a working set of K blocks all mapping to one set without any conflict miss?

N = K

. You need at least as many ways in that set as there are simultaneously-live blocks competing for it; fewer forces evictions.