Set-associative and fully associative caches: Exercises

This page is a graded ladder. Each rung is harder than the last: L1 Recognition (can you name the piece?) → L2 Application (can you plug into the formula?) → L3 Analysis (can you reason about behaviour?) → L4 Synthesis (can you design a whole thing?) → L5 Mastery (can you compare and defend a choice?).

Every problem hides its full answer inside a collapsible [!recall]- block — so you can test yourself first, then reveal. Do the work on paper before you open a solution.

Before we start, here is the one picture that every problem leans on. Keep it open in a second tab.

Figure — Set-associative and fully associative caches

Read the picture left to right: an address (a plain string of bits — think of it as the house number of one byte in memory) gets sliced into three fields. The rightmost slice, the offset, picks a byte inside one block. The middle slice, the index, picks which set to look in. The leftmost slice, the tag, is the label the cache stores so it can later confirm "yes, this really is your block."

We'll use these words constantly, so let's pin them down once:

Level 1 — Recognition

Goal: name the piece, read a config, no arithmetic beyond powers of two.

L1.1 A cache is described as 8-way set-associative. In plain words, how many lines are in each set, and how many places can a single memory block be stored?

L1.2 Which cache organisation is the special case $N = 1$ of set-associative? Which is the special case where $N$ equals the total number of lines?

L1.3 A fully associative cache has an address split of $⟨ Tag ∣ Offset ⟩$ . Why is there no index field?

Recall Solution L1

L1.1 "8-way" means each set contains $N = 8$ lines. A block maps to exactly one set (fixed by its index bits), but inside that set it may sit in any of the 8 lines. So it has 8 possible homes.

L1.2

$N = 1$ → direct-mapped: one line per set, so exactly one home per block.
$N = L$ (all lines in one set) → fully associative: any line at all is a valid home.

L1.3 The index field exists only to choose which set to search. A fully associative cache has just one set — there is nothing to choose — so those bits would carry zero information. All the "which block is this" work is pushed into the tag, and every line is searched in parallel.

Level 2 — Application

Goal: plug numbers into the four equations.

L2.1 A 32 KB, 4-way set-associative cache uses 64-byte blocks with 32-bit addresses. Find: total lines $L$ , sets $S$ , and the bit split (offset / index / tag).

L2.2 A 16 KB fully associative cache, 32-byte blocks, 32-bit addresses. Find lines, offset bits, index bits, tag bits.

L2.3 Address 0xDEADBE00 (32 bits) hits the cache from L2.1. Extract its offset, index (as a decimal set number), and tag (in hex).

Recall Solution L2

L2.1 $C = 32 KB = 32 \times 1024 = 32768$ bytes. $L = \frac{C}{B} = \frac{32768}{64} = 512 lines$ $S = \frac{L}{N} = \frac{512}{4} = 128 sets$ Bits: $b = lo g_{2} 64 = 6$ , $i = lo g_{2} 128 = 7$ , $t = 32 - 6 - 7 = 19$ . Answer: 512 lines, 128 sets, split 19 tag / 7 index / 6 offset (sum $= 32$ ✓).

L2.2 $C = 16384$ , $B = 32$ . $L = \frac{16384}{32} = 512 lines$ $b = lo g_{2} 32 = 5$ , index $= 0$ (fully associative), $t = 32 - 5 = 27$ . Answer: 512 lines, 27 tag / 0 index / 5 offset.

L2.3 Use the L2.1 split (19/7/6). Write the low 3 hex digits E00 in binary (the high bits only feed the tag): $0xDEADBE00 = 19 tag 1101111010101101101 7 index 1111000 6 offset 000000$

Offset = last 6 bits = 000000 = $0$ .
Index = next 7 bits = 1111000 = $64 + 32 + 16 + 8 = 120$ . → set 120.
Tag = top 19 bits. Numerically, tag $= ⌊ 0xDEADBE00 / 2^{13} ⌋ = 0x6F56D$ . Answer: offset $0$ , set 120, tag 0x6F56D.

Level 3 — Analysis

Goal: reason about hits, misses and eviction — not just bit counts.

L3.1 A 2-way set-associative cache with 1 set (so it's really tiny: 2 lines, fully associative in effect) uses LRU. The access stream of block numbers is: $A, B, A, C, B, A$ Both lines start empty. Mark each access as HIT or MISS and give the final miss count. (See LRU.)

L3.2 Same 2-line cache, same stream $A, B, A, C, B, A$ , but now with FIFO replacement. Miss count?

L3.3 Why can a direct-mapped cache never need a replacement policy, while a 2-way cache does?

Recall Solution L3

Notation: cache state written as [most-recent, least-recent]; ✗ = miss, ✓ = hit.

L3.1 (LRU)

Access	Hit/Miss	Reason	State after (MRU→LRU)
A	✗	empty	[A]
B	✗	not present	[B, A]
A	✓	A present	[A, B]
C	✗	full → evict LRU = B	[C, A]
B	✗	B was evicted	[B, C]
A	✗	A was LRU, evicted when B loaded	[A, B]

Misses = 5, hits = 1.

L3.2 (FIFO) — evict oldest by insertion, ignore re-use. State = [newest, oldest].

Access	Hit/Miss	State
A	✗	[A]
B	✗	[B, A]
A	✓	[B, A] (order unchanged — FIFO doesn't refresh on hit)
C	✗ evict oldest A	[C, B]
B	✓	[C, B]
A	✗ evict oldest B	[A, C]

Misses = 4, hits = 2.

Interesting: here FIFO beats LRU (4 vs 5). It's a small hand-picked stream — LRU wins on average in real workloads, but no policy wins on every trace.

L3.3 A direct-mapped cache offers each block exactly one legal line ( $N = 1$ ). On a miss there is nothing to choose: you overwrite that one line. A 2-way cache offers two legal lines per set, so on a miss you must decide which of the two to throw out — that decision is the replacement policy.

Level 4 — Synthesis

Goal: design a full cache from a spec and defend each field.

L4.1 Design a cache meeting all of these: total size 256 KB, 8-way set-associative, 128-byte blocks, 40-bit physical addresses. Give $L$ , $S$ , and the full offset/index/tag split. Verify the sum.

L4.2 You are told a set-associative cache has 11 index bits, 6 offset bits, and 512 KB total size. Deduce its associativity $N$ and address width $A$ if the tag is 17 bits.

Recall Solution L4

L4.1 $C = 256 \times 1024 = 262144$ bytes, $B = 128$ , $N = 8$ , $A = 40$ . $L = \frac{262144}{128} = 2048 lines$ $S = \frac{2048}{8} = 256 sets$ $b = lo g_{2} 128 = 7$ , $i = lo g_{2} 256 = 8$ , $t = 40 - 8 - 7 = 25$ . Answer: 2048 lines, 256 sets, split 25 tag / 8 index / 7 offset (sum $= 40$ ✓).

L4.2 Work backwards.

Offset bits $b = 6 \Rightarrow B = 2^{6} = 64$ bytes.
Index bits $i = 11 \Rightarrow S = 2^{11} = 2048$ sets.
$C = 512 KB = 524288$ bytes, so $L = C / B = 524288/64 = 8192$ lines.
$N = L / S = 8192/2048 = 4$ . → 4-way.
$A = t + i + b = 17 + 11 + 6 = 34$ bits. Answer: $N = 4$ (4-way), $A = 34$ bits.

Level 5 — Mastery

Goal: compare organisations, reason about tradeoffs, defend a design choice.

L5.1 You must cache a program whose hot inner loop repeatedly touches exactly 3 arrays whose base addresses all map to the same set index in a direct-mapped cache. Explain why a direct-mapped cache thrashes here, and the minimum associativity that removes these conflict misses. (See Conflict misses vs capacity misses.)

L5.2 A fully associative cache and a direct-mapped cache have the same total size and block size. Which has (a) lower miss rate, (b) faster hit time, (c) more comparator hardware? For each, one sentence why.

L5.3 A Translation Lookaside Buffer (TLB) is almost always fully associative even though large caches rarely are. Give the two reasons this makes sense specifically for a TLB.

Recall Solution L5

L5.1 All three array bases share one index, so in a direct-mapped cache all three fight for one single line. Each access to a different array evicts the previous one → every touch is a conflict miss, even though the cache has thousands of free lines elsewhere. The set has room for only 1 block but 3 want to coexist. Minimum associativity = 3-way (or higher): a 3-way set holds all three simultaneously, so once loaded they stay resident and the conflict misses vanish. In practice you'd round up to 4-way (a power of two, cleaner indexing).

L5.2

(a) Lower miss rate → fully associative. A block may occupy any line, so it never suffers conflict misses; only true capacity misses remain.
(b) Faster hit time → direct-mapped. Exactly one candidate line, one tag comparison, no multiplexing among ways → shortest critical path.
(c) More comparators → fully associative. It compares the tag against every line ( $L = C / B$ comparators) in parallel; direct-mapped needs just one.

L5.3 (1) A TLB is small (tens of entries), so the cost of "compare against everything" — a comparator per entry — is affordable, unlike a 512-line data cache. (2) Address translations have scattered, unpredictable page numbers; conflict misses there would be very costly (a miss triggers a slow page-walk), so eliminating them entirely by full associativity is worth the hardware.

Recall One-line self-test

Sets from cache config ::: $S = C / (B N)$ ; then index bits $i = lo g_{2} S$ , offset $b = lo g_{2} B$ , tag $t = A - i - b$ . Why does direct-mapped need no replacement policy? ::: One legal line per block — no choice on eviction. Under FIFO, does a hit change eviction order? ::: No — only insertion time counts; hits don't refresh.