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

This is a Deep Dive child of the parent Cache Organization note. There we derived the address split $[tag ∣ index ∣ offset]$ . Here we exercise it against every case a problem can throw at you — every organization, degenerate sizes, limiting values, a word problem, and an exam trick.

Before line one, let us re-anchor the five symbols we will use, in plain words and with the picture below.

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

The scenario matrix

Every cache-organization problem is one cell of this grid. The worked examples below are tagged with the cell they cover, and together they fill every cell.

#	Case class	What makes it tricky	Covered by
C1	Direct-mapped ( $E = 1, S = N$ )	most index bits, no replacement policy	Ex 1
C2	$n$ -way set associative ( $1 < E < N$ )	index shrinks, tag grows	Ex 2
C3	Fully associative ( $E = N, S = 1$ )	$s = 0$ , no index bits at all	Ex 3
C4	Degenerate: $B = 1$ byte	$b = 0$ , no offset bits	Ex 4
C5	Degenerate: whole cache = 1 block	$N = 1$ , both extremes collapse	Ex 5
C6	Conflict vs capacity trace	which miss type fires, and why	Ex 6
C7	Limiting behaviour: $E \to N$	tag/comparator cost as flexibility rises	Ex 7
C8	Word problem (real-world)	translate English → $m, B, N, E$	Ex 8
C9	Exam twist: given tag size, find $E$	run the derivation backwards	Ex 9

Worked examples

Worked example Example 1 — Cell C1: plain direct-mapped

32-bit address, 8 KiB cache, 32-byte blocks, direct-mapped. Find the split $t ∣ s ∣ b$ and the number of tag comparators.

Forecast: guess now — will the index be large or small compared with a 4-way cache? Write down your split before reading.

Offset $b = lo g_{2} 32 = 5$ . Why this step? The offset selects one byte inside a block. $32$ bytes need $lo g_{2} 32 = 5$ bits to name.
Total blocks $N = \frac{8 KiB}{32 B} = \frac{8192}{32} = 256$ . Why this step? Cache holds $N$ blocks, and cache-size $= N \cdot B$ , so $N =$ size $/ B$ .
Sets $S = N = 256$ because direct-mapped means $E = 1$ and $S = N / E$ . Why this step? Each set holds one block, so there are as many sets as blocks.
Index $s = lo g_{2} 256 = 8$ . Why this step? We must name one of $256$ sets; $lo g_{2} 256 = 8$ bits do it.
Tag $t = m - s - b = 32 - 8 - 5 = 19$ . Why this step? Whatever address bits are left over must identify which block sits in the chosen set.
Comparators $= E = 1$ . Why this step? Only one line can match, so one tag comparison per access.

Split: $19 ∣ 8 ∣ 5$ .

Verify: $t + s + b = 19 + 8 + 5 = 32 = m$ . ✓ The three fields exactly tile the address — no bit is lost or double-counted.

Worked example Example 2 — Cell C2: same cache, 4-way associative

32-bit, 8 KiB, 32-byte blocks, 4-way ( $E = 4$ ).

Forecast: compared with Example 1 (same cache size!), predict whether the tag grows or shrinks.

Offset $b = 5$ — unchanged. Why this step? Offset depends only on block size $B$ , and $B$ is still $32$ . Associativity never touches the offset.
Total blocks $N = 256$ — unchanged (same size, same block size).
Sets $S = N / E = 256/4 = 64$ . Why this step? Now $4$ blocks share each set, so there are $4 \times$ fewer sets.
Index $s = lo g_{2} 64 = 6$ . Why this step? Fewer sets $\Rightarrow$ fewer index bits. We lost $8 - 6 = 2$ index bits versus Example 1.
Tag $t = 32 - 6 - 5 = 21$ . Why this step? $t = m - s - b$ : the $2$ bits the index gave up must reappear in the tag. Tag grew by exactly $2$ .
Comparators $= E = 4$ .

Split: $21 ∣ 6 ∣ 5$ .

Verify: $21 + 6 + 5 = 32$ ✓, and $t_{4-way} - t_{direct} = 21 - 19 = 2 = s_{direct} - s_{4-way} = 8 - 6$ . ✓ Bits moved from index to tag, none created or destroyed — this refutes the "more associativity = more index bits" myth.

Worked example Example 3 — Cell C3: fully associative,

$s = 0$ 32-bit, 8 KiB, 32-byte blocks, fully associative.

Forecast: how many index bits does a cache with one set have?

Offset $b = 5$ (block size still $32$ ).
Sets $S = 1$ , so Index $s = lo g_{2} 1 = 0$ . Why this step? Fully associative means any block may sit in any slot — there is only one set, and naming "which of one set" needs zero bits. This is why the index field vanishes.
Tag $t = 32 - 0 - 5 = 27$ . Why this step? With no index to pre-select a set, the tag alone must carry the entire block identity — hence the largest tag of the three organizations.
Comparators $= E = N = 256$ . Why this step? Any of the $256$ lines could hold the block, so all $256$ tags are compared in parallel every access — this is the hardware cost of zero conflict misses.

Split: $27 ∣ - ∣ 5$ .

Verify: $27 + 0 + 5 = 32$ ✓. Also $t_{full} = 27$ is the tag width of a $1$ -set cache; compare to direct's $19$ — exactly the $8$ index bits that "disappeared" reappeared in the tag ( $27 - 19 = 8$ ). ✓ Nothing lost.

Worked example Example 5 — Cell C5: degenerate cache = 1 block

A cache holding exactly $N = 1$ block, block size $8$ bytes, $16$ -bit address. Show that direct-mapped, fully associative and "1-way" are the same cache here.

Forecast: if there is only one slot, does the organization even matter?

$E$ can only be $1$ (only one block exists), so $S = N / E = 1/1 = 1$ . Why this step? With one block you cannot have more than one way; and one block in one set means one set.
Offset $b = lo g_{2} 8 = 3$ .
Index $s = lo g_{2} 1 = 0$ .
Tag $t = 16 - 0 - 3 = 13$ .

Split: $13 ∣ - ∣ 3$ .

Verify: $13 + 0 + 3 = 16$ ✓. Here $E = N = 1$ and $S = 1$ simultaneously, so the direct-mapped condition ( $E = 1$ ) and the fully-associative condition ( $S = 1$ ) both hold. A one-slot cache is all three organizations at once — every incoming block evicts the only resident, so it thrashes on any two distinct blocks. Limiting sanity check for both extremes.

Worked example Example 6 — Cell C6: conflict miss vs capacity miss trace

Two caches, each holds $N = 4$ blocks, $B = 1$ byte, $16$ -bit address. Trace the block-number stream $0, 4, 0, 4, 0, 4$ . (a) direct-mapped, (b) the same stream but on $0, 1, 2, 3, 4$ in a fully associative $4$ -block cache.

Forecast: which run is 100% miss, and is its cause conflict or capacity?

(a) Placement rule block $k \to k mod S$ , and direct-mapped gives $S = N = 4$ . Why this step? Direct-mapped forces one legal slot; that slot is $k mod 4$ .
Both $0$ and $4$ satisfy $k mod 4 = 0$ (since $0 mod 4 = 0$ and $4 mod 4 = 0$ ). They collide in slot $0$ .
Trace $0, 4, 0, 4, 0, 4$ : each access evicts the other. Miss, miss, miss, miss, miss, miss $\Rightarrow$ 6 misses / 6 accesses = 100%. Why this step? The cache had 3 other empty slots, but the mapping forbade using them — that is the definition of a conflict miss.
(b) Fully associative, stream $0, 1, 2, 3, 4$ : slots fill $0, 1, 2, 3$ (four cold/compulsory misses), then $4$ arrives and the cache is genuinely full — one block must go regardless of organization. That fifth miss is a capacity miss. Why this step? No mapping restriction exists here (any slot allowed), so the eviction is forced purely by size, not by placement. Different C, same symptom.

Verify: run (a) miss count $= 6$ , hit count $= 0$ . Run (b) misses $= 5$ (four compulsory + one capacity), and crucially zero conflict misses because fully associative cannot produce them. Both counts checked in VERIFY. ✓

Worked example Example 7 — Cell C7: limiting behaviour as

$E$ climbs $1 \to N$ Fixed cache: $32$ -bit address, $N = 256$ blocks, $B = 64$ bytes. Tabulate tag size and comparator count as $E$ runs through $1, 2, 4, \dots, 256$ .

Forecast: as $E$ doubles, by how many bits does the tag change each time, and what is the comparator trend?

Offset is fixed: $b = lo g_{2} 64 = 6$ .
For a given $E$ : $S = 256/ E$ , $s = lo g_{2} (256/ E) = 8 - lo g_{2} E$ , and $t = 32 - s - 6 = 18 + lo g_{2} E$ . Why this step? Substituting $s$ into $t = m - s - b$ shows the tag grows linearly in $lo g_{2} E$ .
Table:

$E$	$S$	$s$	$t$	comparators
1	256	8	18	1
2	128	7	19	2
4	64	6	20	4
8	32	5	21	8
256	1	0	26	256

Verify: every row satisfies $t + s + b = 32$ ; each doubling of $E$ adds exactly $+ 1$ to $t$ and $- 1$ to $s$ ; the last row is the fully-associative case ( $t = 26$ , matches an independent computation $32 - 0 - 6$ ). Comparators equal $E$ throughout. ✓ The limit $E \to N$ gives max tag and max hardware — flexibility is bought with tag bits and comparators.

Worked example Example 8 — Cell C8: real-world word problem

"A camera chip has a $2 MiB$ cache with $128$ -byte lines, built $8$ -way set associative, on a machine with $34$ -bit physical addresses. The vendor sheet is missing the index width — recover it."

Forecast: guess the index width before computing; is it bigger or smaller than a direct-mapped version of the same cache?

Translate English → symbols: $m = 34$ , cache size $= 2 MiB = 2^{21}$ bytes, $B = 128 = 2^{7}$ , $E = 8$ . Why this step? Every cache problem is these four numbers; the rest is arithmetic.
Offset $b = lo g_{2} 128 = 7$ .
Total blocks $N = 2^{21} / 2^{7} = 2^{14} = 16384$ .
Sets $S = N / E = 2^{14} /8 = 2^{14} / 2^{3} = 2^{11} = 2048$ .
Index $s = lo g_{2} 2048 = 11$ . Why this step? This is the missing number the vendor wanted.
Tag $t = 34 - 11 - 7 = 16$ .

Answer: index width $= 11$ bits (split $16 ∣ 11 ∣ 7$ ).

Verify: $16 + 11 + 7 = 34$ ✓. A direct-mapped version would have $s = lo g_{2} 16384 = 14$ bits — larger, as predicted, because direct-mapped has $8 \times$ more sets. Units check: $2^{21}$ bytes $\div 2^{7}$ bytes/block $= 2^{14}$ blocks, dimensionally clean. ✓

Worked example Example 9 — Cell C9: exam twist, run the derivation backwards

"A $30$ -bit-address cache with $64$ -byte blocks has a measured tag width of $19$ bits and total capacity $32 KiB$ . What is its associativity $E$ ?"

Forecast: you are given $t$ and asked for $E$ — which intermediate quantity must you solve for first?

Offset $b = lo g_{2} 64 = 6$ .
From $t = m - s - b$ : solve for the index $s = m - b - t = 30 - 6 - 19 = 5$ . Why this step? The address always tiles, so knowing any two fields plus $m$ pins the third.
Sets $S = 2^{s} = 2^{5} = 32$ .
Total blocks $N = \frac{32 KiB}{64 B} = \frac{2 ^{15}}{2 ^{6}} = 2^{9} = 512$ .
Associativity $E = N / S = 512/32 = 16$ . Why this step? $S \cdot E = N$ rearranged; this is the requested answer.

Answer: $E = 16$ (16-way set associative).

Verify: reconstruct forwards: $s = lo g_{2} 32 = 5$ , $t = 30 - 5 - 6 = 19$ ✓ matches the given tag; $S \cdot E = 32 \cdot 16 = 512 = N$ ✓; capacity $= N \cdot B = 512 \cdot 64 = 32768 = 32 KiB$ ✓. All three consistency checks close.

Recall

Recall (Ex 2 vs Ex 3) Two caches have the same size and block size; one is 4-way, one is fully associative. Which has the bigger tag and why?

Fully associative — it has fewer sets (just one, $s = 0$ ), so more bits are pushed from index into tag. Fixed size means index and tag trade bits one-for-one.

Recall (Ex 6) In the

$0, 4, 0, 4$ direct-mapped trace, name the miss type and the one-line reason. Conflict misses — the cache had empty slots, but the mapping rule $k mod 4$ forbade using them.

Recall (Ex 9) Given tag and address widths, what do you compute first to find

$E$ ? The index bits: $s = m - b - t$ . Then $S = 2^{s}$ , $N =$ size $/ B$ , and $E = N / S$ .