Cache organization — direct-mapped, n-way set associative, fully associative: Exercises

Definition Every symbol used on this page (built from zero)

$m$ = address width in bits (how many bits the CPU puts on the address bus). Example: $m = 32$ .
$B$ = block size = number of bytes in one cache line (the smallest chunk moved between memory and cache).
$S$ = number of sets = number of "shelves" the cache is divided into.
$E$ = associativity (ways) = number of slots inside one set (how many blocks a set can hold at once).
$N = S \cdot E$ = total blocks the whole cache can hold. Also $N = (cache size in bytes) / B$ .
The address splits into three named fields that add up to $m$ : $which block [tag t] which set [index s] which byte [offset b], t + s + b = m,$ where $b = lo g_{2} B$ (bits to pick a byte inside a block), $s = lo g_{2} S$ (bits to pick a set), and $t = m - s - b$ is "everything left over" (bits to tell apart the blocks that land in the same set).

Figure — Cache organization — direct-mapped, n-way set associative, fully associative

Read the ruler above like this, and we will use it verbatim in the very next problem (L2.1): the address bar is exactly the split 18 | 8 | 6 you compute in L2.1 — the orange offset (6 bits) is fixed by $B$ , the violet index (8 bits) selects one of $S$ sets, and the magenta tag (18 bits) is the remainder. Whenever a problem asks for a split, you are literally cutting this bar at two places: first cut at $b = lo g_{2} B$ from the right, then decide $S$ and cut $s = lo g_{2} S$ more, and the magenta piece that survives is the tag.

Level 1 — Recognition

Recall Solution L1.1

One set means there is nothing to select — so there are zero index bits ( $s = lo g_{2} 1 = 0$ ). With any block allowed anywhere, this is fully associative. Reveal: $s ::: 0$ bits.

Recall Solution L1.2

Direct-mapped gives each set exactly one slot, so $E = 1$ (and then $S = N$ ). Fully associative crams every block into one set, so $S = 1$ (and then $E = N$ ).

Recall Solution L1.3

The offset. It is $b = lo g_{2} B$ , and $B$ (bytes per block) is a property of block size alone. Changing $E$ or $S$ never moves the offset boundary.

Level 2 — Application

Recall Solution L2.1

Offset: $b = lo g_{2} 32 = 5$ . (32 bytes per block.)
Total blocks $N = 8 KiB /32 = 8192/32 = 256$ . Direct-mapped $\Rightarrow S = N = 256$ .
Index: $s = lo g_{2} 256 = 8$ .
Tag: $t = 32 - 8 - 5 = 19$ . Split: 19 | 8 | 5.

Recall Solution L2.2

Offset unchanged: $b = 5$ (block size unchanged).
$N = 256$ . Sets $S = N / E = 256/8 = 32$ .
Index: $s = lo g_{2} 32 = 5$ .
Tag: $t = 32 - 5 - 5 = 22$ . Split: 22 | 5 | 5. Comparators $= E =$ 8. Notice the index shrank from 8→5 and the tag grew from 19→22 (exactly the 3 bits index lost).

Recall Solution L2.3

$S = 1 \Rightarrow s = 0$ .
$b = 5$ (unchanged).
Tag: $t = 32 - 0 - 5 = 27$ . Split: 27 | — | 5. Comparators $= E = N =$ 256 (fire on every access).

Recall Solution L2.4

Each line stores $t = 22$ tag bits, and there are $N = 256$ lines. Total $= 22 \times 256 = 5632$ tag bits $= 704$ bytes.

Level 3 — Analysis

Recall Solution L3.1

A block with number $k$ goes to set $k mod 4$ (four sets, one slot each). Both $k = 0$ and $k = 4$ give $k mod 4 = 0$ , so both map to set $0$ — they fight over the same single slot.

Access $k = 0$ → miss (cold), load block 0.
Access $k = 4$ → miss, evicts 0, loads 4.
Access $k = 0$ → miss (0 was evicted), evicts 4, loads 0.
… every access evicts the previous occupant. All 8 misses. Miss rate $= 8/8 = 100% = 1.0$ .

The figure below contrasts this thrashing direct-mapped case with the 2-way fix you will compute in L3.2 — keep it in view as you read both.

Recall Solution L3.2

With $S = 2$ , block number $k$ goes to set $k mod 2$ . Both $k = 0$ and $k = 4$ are even → both map to set 0 — but set 0 now has 2 slots, enough for both (see the right half of the figure above).

Access $k = 0$ → miss (cold), place in set 0.
Access $k = 4$ → miss (cold), place in the other slot of set 0.
Every access after: both 0 and 4 are resident → hit. Only 2 misses (both compulsory). Miss rate $= 2/8 = 0.25$ . This is the reason associativity exists: it removed 6 pure conflict misses.

Recall Solution L3.3

Two distinct blocks ( $k = 0$ and $k = 4$ ) are ever touched, so exactly 2 compulsory misses (first sight of each). The remaining $8 - 2 =$ 6 misses are conflict misses — the cache had room (4 lines, only 2 blocks live) but placement rules forced eviction. A fully associative cache (or any cache with $\geq 2$ lines and a sane policy) keeps both blocks resident forever → only the 2 compulsory misses. Fully associative has zero conflict misses by definition.

Recall Solution L3.4

They map to the same set iff their index bits (bits 6..13, the 8 bits just above the 6 offset bits) are equal. Equivalently the set is $k mod 256$ where $k = ⌊ addr /64 ⌋$ .

0x00001040 $= 4160$ . Block number $k = ⌊ 4160/64 ⌋ = 65$ . Set $= 65 mod 256 = 65$ .
0x00002040 $= 8256$ . Block number $k = ⌊ 8256/64 ⌋ = 129$ . Set $= 129 mod 256 = 129$ . Set $65 \neq = 129$ → they do NOT collide (different sets). In binary the differing address bit is bit 13, which lands inside the 8-bit index field, so it changes the set.

Level 4 — Synthesis (design)

Recall Solution L4.1

$b = lo g_{2} 64 = 6$ .
6 index bits ⇒ $S = 2^{6} = 64$ sets.
Total blocks $N = 32 KiB /64 = 32768/64 = 512$ .
$E = N / S = 512/64 =$ 8. So an 8-way set-associative cache. Check tag: $t = 32 - 6 - 6 = 20$ bits.

Recall Solution L4.2

$b = lo g_{2} 64 = 6$ .
$t = 21$ , so index $s = m - t - b = 32 - 21 - 6 = 5$ bits ⇒ $S = 2^{5} = 32$ sets.
$E = 4$ ⇒ $N = S \cdot E = 32 \times 4 = 128$ blocks.
Size $= N \times B = 128 \times 64 = 8192$ bytes $=$ 8 KiB.

Recall Solution L4.3

Direct-mapped: set $= k mod 128$ . Blocks $0, 128, 256$ all satisfy $k mod 128 = 0$ → all fight for set 0's single slot → thrash (100% miss on the loop after the first pass). $N = 128$ , $b = 0$ (1-byte blocks), $m$ = address width.

Before (direct): $S = 128$ , $s = 7$ .
We need one set to hold 3 blocks at once ⇒ $E \geq 3$ . Smallest usable associativity that is a design-friendly power of two is $E = 4$ (a 3-way cache is legal but power-of-two ways keep index bits integer; a strict answer of $E = 3$ also stops the thrash — accept $E \geq 3$ ).
After (4-way): $S = N / E = 128/4 = 32$ , $s = lo g_{2} 32 = 5$ . Now blocks $0, 128, 256$ still share a set ( $k mod 32 = 0$ ) but that set has 4 slots → all three fit, no eviction. Conflict misses gone. Total size unchanged (still 128 lines); only the shape changed.

Level 5 — Mastery (full integration)

Recall Solution L5.1

Why we compute a tag at all. The address split says $t + s + b = m$ . Here $b = lo g_{2} 4 = 2$ (offset) and $s = lo g_{2} 4 = 2$ (index). Strip the low $b$ bits and you have the block number $k = ⌊ addr / B ⌋$ ; strip $s$ more index bits from $k$ and the remaining high bits are the tag, i.e. $tag = ⌊ k / S ⌋$ . The tag is exactly the leftover magenta piece of the ruler figure — its whole job is to tell apart the different blocks that share one set, so we must store and compare it. So: block number $k = ⌊ addr /4 ⌋$ ; set $= k mod 4$ ; tag $= ⌊ k /4 ⌋$ .

Read the trace table below row by row from the top — the last column tags each row as a hit or a miss so the pattern of the two ✗ hits stands out from the five misses:

#	addr	block# $k$	set = $k mod 4$	tag = $⌊ k /4 ⌋$	result
1	0	0	0	0	✗ miss (cold)
2	4	1	1	0	✗ miss (cold)
3	8	2	2	0	✗ miss (cold)
4	20	5	1	1	✗ miss (cold)
5	0	0	0	0	✓ HIT
6	36	9	1	2	✗ miss (evict)
7	8	2	2	0	✓ HIT

Walk it (each set holds 2 ways, LRU evicts the least-recently-used):

0 → set 0 empty → miss. Set0 = {tag0}.
4 → set 1 empty → miss. Set1 = {tag0}.
8 → set 2 empty → miss. Set2 = {tag0}.
20 → set 1, tag1 not present → miss. Set1 = {tag0, tag1} (both slots now used).
0 → set 0, tag0 present → HIT.
36 → set 1, tag2 not present, set1 full {tag0,tag1}. LRU of set1 is tag0 (from step 2, older than tag1 at step 4) → evict tag0 → miss. Set1 = {tag1, tag2}.
8 → set 2, tag0 present → HIT.

(c) Misses $= 5$ , hits $= 2$ , total $= 7$ . Miss rate $= 5/7 \approx 0.714$ . (d) $AMAT = hit time + miss rate \times miss penalty = 1 + \frac{5}{7} \times 100 = 1 + \frac{500}{7} \approx 72.43$ cycles.

Recall Solution L5.2

Capacity $= 8$ blocks; the trace only ever touches 5 distinct blocks (numbers 0,1,2,5,9). All 5 fit simultaneously → each block misses exactly once (its first sight) and never gets evicted. Misses $=$ 5 (all compulsory). Same count as L5.1! Why no improvement? Look back at step 6 of L5.1: the block evicted from set 1 was block 1 (its tag was tag0 within set 1), and block 1 is never referenced again in the stream — so its eviction never forced a re-fetch. The 5 misses in L5.1 were therefore all first-touches (compulsory); there were no conflict misses to remove, so associativity couldn't help. Lesson: associativity is insurance against conflict; if the trace has none, it buys nothing.

Recall Solution L5.3

Fixed size $= 32$ bytes. With 8-byte blocks, $N = 32/8 =$ 4 blocks (down from 8). Bigger blocks fetch more neighbors per miss (good for spatial locality), but the cache now holds fewer distinct blocks. Here is the explicit why it hurts: if the program's accesses jump around (poor spatial locality), the extra bytes dragged in on each miss are never used before the block is evicted — so you paid extra memory bandwidth for nothing. Simultaneously, halving the block count from 8 to 4 means fewer independent blocks can be resident at once, so a working set of 5 distinct blocks no longer fits (only 4 slots) → previously-compulsory-only traces now suffer extra capacity/conflict misses. Both effects push the miss rate up. That is why miss-rate-vs-block-size is a U-shaped curve: it falls at first (locality captured) then rises (waste + fewer blocks), with an optimum in between — never "always fewer misses."

Wrap-up recall

Recall The one-line summary of every L2 problem

Offset is fixed by $B$ ; choose how to slice $N$ into $S = N / E$ sets; index $= lo g_{2} S$ ; tag is everything left. Raising $E$ ⇒ smaller $S$ ⇒ fewer index bits ⇒ bigger tag.

Recall The one-line summary of every L3–L5 problem

Same index ⇒ same set ⇒ competition; ways $E$ decide how many competitors coexist; conflict misses vanish only when $E$ (or full associativity) is large enough to hold all same-set blocks live at once.