Cache line size and tags: Worked examples — Hardware deep dive

This page is the drill hall for the parent note. There we learned the recipe: split every address into [ Tag | Index | Offset ]. Here we push that recipe through every kind of input it can meet — big caches, tiny caches, associativity, 64-bit machines, and the sneaky "degenerate" cases where a field shrinks to zero bits.

Before we start, one sentence of ground-truth so no symbol sneaks in undefined:

The scenario matrix

Every cache-address problem is one of a handful of case classes. Below is the full grid; each worked example afterwards is tagged with the cell it hits, so together they cover every cell.

#	Case class	What makes it special	Example
A	Baseline direct-mapped	$A = 1$ , all three fields non-trivial	Ex 1
B	Splitting a concrete address	turn hex/binary into T, I, O values	Ex 2
C	Set-associative	$A > 1$ shrinks index, grows tag	Ex 3
D	Fully associative (degenerate index)	$i = 0$ — no index field at all	Ex 4
E	Line = whole cache (degenerate index, other end)	one line only, $i = 0$ again	Ex 4b (inside Ex 4)
F	Offset = 0 (degenerate offset)	$L = 1$ byte, no offset field	Ex 5
G	64-bit / huge address space	$N = 64$ , giant tag	Ex 6
H	Real-world word problem	array-stride & spatial locality	Ex 7
I	Exam twist: solve backwards	given the fields, find $C$ or $L$	Ex 8
J	Limiting behaviour	tag $\to 0$ as $C \to$ full memory	Ex 9

Look at the figure: the same 32-bit ruler is chopped differently in each case. As the index field (blue) grows, the tag (yellow) must shrink — they share a fixed total. The offset (pink) is pinned by $L$ alone. Keep this "sliding boundary" picture in mind for every example.

The worked examples

Cell A — Baseline direct-mapped

Worked example Example 1 — 32 KiB, 64-byte lines, direct-mapped

Given $C = 32 KiB = 32768$ B, $L = 64$ , $A = 1$ , $N = 32$ . Find $b$ , $i$ , $t$ .

Forecast: before reading on, guess: will the tag be closer to 10 bits or 20 bits? (Jot it down.)

Offset $b = lo g_{2} 64 = 6$ . Why this step? The offset must name every byte inside one line; 64 bytes $= 2^{6}$ , so 6 bits.
Line count $= C / L = 32768/64 = 512$ . Since $A = 1$ , sets $=$ lines $= 512$ . Why this step? The index names a set; we need to know how many sets exist first.
Index $i = lo g_{2} 512 = 9$ . Why this step? $512 = 2^{9}$ , so 9 bits name one of the 512 slots.
Tag $t = 32 - 9 - 6 = 17$ . Why this step? The tag is whatever bits are left; they distinguish the $2^{17}$ blocks that all land in the same slot.

Verify: $b + i + t = 6 + 9 + 17 = 32 = N$ ✓. The fields must exactly repartition the address — no bit lost, none double-counted.

Cell B — Splitting a concrete address

Worked example Example 2 — Split address 0x0001_8ABC in that same cache

Given the Ex-1 layout [17 | 9 | 6]. Address = 0x00018ABC.

Forecast: which field will the lowest hex digit C land in? (Hint: C = 4 bits, offset is 6 bits.)

To decimal: 0x00018ABC $= 1 \cdot 1 6^{4} + 8 \cdot 1 6^{3} + 10 \cdot 1 6^{2} + 11 \cdot 16 + 12 = 100540$ . Why this step? We work in plain integers so we can use division/modulo instead of eyeballing binary.
Offset $= addr mod 2^{6} = 100540 mod 64$ . $100540 = 1571 \cdot 64 + 60$ , so offset $= 60$ . Why this step? The low $b$ bits are exactly the remainder after dividing by $2^{b}$ .
Index $= ⌊ addr / 2^{6} ⌋ mod 2^{9} = 1571 mod 512$ . $1571 = 3 \cdot 512 + 35$ , so index $= 35$ . Why this step? Shift past the offset (divide by $2^{b}$ ), then take the low $i$ bits (mod $2^{i}$ ).
Tag $= ⌊ addr / 2^{15} ⌋ = ⌊ 100540/32768 ⌋ = 3$ . Why this step? Everything above index+offset ( $= 15$ bits) is the tag.

Verify: reassemble: $tag \cdot 2^{15} + index \cdot 2^{6} + offset = 3 \cdot 32768 + 35 \cdot 64 + 60 = 98304 + 2240 + 60 = 100604$ . That's wrong! Recompute step 1 carefully: $10 \cdot 256 = 2560$ , $11 \cdot 16 = 176$ ; $65536 + 32768 + 2560 + 176 + 12 = 101052$ . Redo with $100540$ ? The mismatch means my decimal was off — so verification caught the error. Correct value: $addr = 101052$ . Then offset $= 101052 mod 64 = 101052 - 1578 \cdot 64 = 101052 - 100992 = 60$ ; index $= 1578 mod 512 = 1578 - 3 \cdot 512 = 42$ ; tag $= ⌊ 101052/32768 ⌋ = 3$ . Reassemble: $3 \cdot 32768 + 42 \cdot 64 + 60 = 98304 + 2688 + 60 = 101052$ ✓.

Lesson: always do the reassembly check — it is the units-check of address arithmetic.

Cell C — Set-associative

Cells D & E — Degenerate index ( $i = 0$ )

Worked example Example 4 — Fully associative, and its mirror image

Part D (fully associative): $C = 32768$ , $L = 64$ , and $A = C / L = 512$ (one giant set).

$b = lo g_{2} 64 = 6$ .
Sets $= C / (L \cdot A) = 32768/ (64 \cdot 512) = 1$ . Why this step? Every line is in the same set, so there is exactly one set.
$i = lo g_{2} 1 = 0$ — there is no index field. Why this step? With one set, you never choose where to look; you compare the tag against all lines.
$t = 32 - 0 - 6 = 26$ .

Verify: $6 + 0 + 26 = 32$ ✓. The whole non-offset part of the address is now tag — makes sense, since only the tag can pick a block.

Part E (line = whole cache): direct-mapped but $L = C = 32768$ , so $b = lo g_{2} 32768 = 15$ , lines $= C / L = 1$ , $i = 0$ , $t = 32 - 15 = 17$ .

Verify: $15 + 0 + 17 = 32$ ✓. Two different roads to $i = 0$ : a fully associative cache (many lines, one set) and a one-line cache (one line total). The formula handles both without special-casing.

Cell F — Degenerate offset ( $b = 0$ )

Cell G — 64-bit address space

Cell H — Real-world word problem

Worked example Example 7 — Striding through an array

Statement. You loop over a double[] array (8 bytes each) sequentially: sum += a[k] for k=0,1,2,…. Cache line $L = 64$ B, initially empty. On average, what fraction of accesses miss?

Forecast: guess the miss fraction — will more than half of accesses miss?

Doubles per line $= L /8 = 64/8 = 8$ . Why this step? Spatial locality means one miss drags in a whole line; how many array elements ride along?
Accessing a[0] misses → brings a[0..7]. Then a[1..7] all hit. a[8] misses (new line), etc. Why this step? Each fresh line costs exactly one compulsory miss (see 5.4.05-Cache-miss-types).
Pattern: 1 miss per 8 accesses ⇒ miss rate $= 1/8 = 0.125 = 12.5%$ .

Verify: miss rate $\times$ elements-per-line $= 0.125 \times 8 = 1$ miss per line ✓ (units: misses/element × elements/line = misses/line). This is exactly why bigger $L$ helps sequential code: doubling to 128 B would halve the miss rate to $6.25%$ .

Cell I — Exam twist (solve backwards)

Cell J — Limiting behaviour

Worked example Example 9 — What happens as the cache swallows all of memory?

Statement. Keep $L = 64$ , $N = 32$ , direct-mapped, but grow $C$ toward the whole $2^{32}$ -byte address space. Track $t$ .

Forecast: does the tag shrink to 0? If so, at what $C$ ?

General $t = 32 - lo g_{2} (C /64) - 6 = 32 - (lo g_{2} C - 6) - 6 = 32 - lo g_{2} C$ . Why this step? Substitute $i = lo g_{2} (C / L)$ and $b = 6$ ; the two 6's cancel, leaving a clean formula.
Try $C = 2^{32}$ (whole memory): $t = 32 - 32 = 0$ . Why this step? If the cache is as big as memory, there is exactly one place each block can go and no ambiguity to resolve — the tag becomes unnecessary.
Try $C = 2^{31}$ (half of memory): $t = 32 - 31 = 1$ . One tag bit distinguishes the two halves of memory.

Verify: at $C = 2^{32}$ , lines $= 2^{32} /64 = 2^{26}$ , so $i = 26$ , and $b = 6$ , giving $i + b = 32 = N$ — leaving $t = 0$ ✓. The tag width measures how much memory each cache slot must disambiguate; when the cache is all of memory, that ambiguity is zero.

Recall

Recall Two roads to

$i = 0$ — name them Which fields vanish? ::: Index vanishes ( $i = 0$ ) in a fully associative cache (many lines, one set) OR in a single-line cache (one line total). Both remove the "which slot" question.

Recall Why does the reassembly check work?

Tag· $2^{i + b}$ + Index· $2^{b}$ + Offset ::: reconstructs the exact original address, because the three fields are just the high, middle, and low bit-groups of that one integer — no information is added or lost.

Recall The three field widths always sum to what?

$b + i + t$ ::: equals $N$ , the address width. If they don't, a field was miscounted.

Connections

5.4.02-Direct-mapped-caches — Cells A, B, E, I, J live here.
5.4.03-Set-associative-caches — Cells C, D (associativity ↔ tag/index trade).
5.4.05-Cache-miss-types — Cell H's compulsory misses.
3.1.04-Spatial-locality — why Cell F ( $L = 1$ ) is a bad idea and Cell H works.
5.4.01-Cache-fundamentals — the "why cache at all" foundation.
6.2.01-Virtual-memory-pages — same tag/index/offset split, applied to pages.