Worked examples — Cache lines, tags, index, offset

This page is the worked-examples companion to the parent note on cache lines, tags, index, offset. There we derived the three-field split; here we exercise it against every case class the topic can hand you — every associativity, the degenerate ends (direct-mapped and fully associative), a zero/edge address, a word problem, and an exam twist. Nothing new is assumed: if a symbol shows up, it was earned in the parent note or is re-earned here.

Throughout this page, $A$ denotes the memory address we are splitting — a plain non-negative integer, written in hex (like 0x1234) or decimal. Every example takes some $A$, cuts its bits, and reads off the three fields.

Figure s01 (below) draws that address row once, with the two scissor cuts labelled: cut 1 strips the low offset bits (accent red), cut 2 separates tag from index. Notice the caption "compute low-to-high": you always find the offset first, then the index, and the tag is whatever remains on the left.

---

The scenario matrix

Before working anything, let us list every kind of situation this topic can throw. If an example doesn't fit a cell here, we've missed a case. (Recall $A$ = the address being split.)

Cell	What varies	Why it's a distinct case
A. Direct-mapped	$w=1$, so $S=L$	Maximum index bits, minimum tag bits
B. $w$-way set-assoc	$1<w<L$	Bits shift from index to tag
C. Fully associative	$S=1$	Zero index bits (degenerate low end)
D. Offset-boundary trap	index does not start on a hex nibble	Sign of a careless bit-peel
E. Zero / tiny address	address $A=0$, or $A<B$	All fields zero — the degenerate address
F. Line-size sweep	change $B$ only	Offset moves, index/tag react
G. Address-width sweep	change $n$ only (e.g. 64-bit)	Only tag changes
H. Word problem	real hit/miss on a loop	Locality meets the split
I. Exam twist	given tag bits, solve backwards for $w$	Inverting the formula

The eight worked examples below cover cells A–I (one example hits two cells). We reuse the notation from the parent: $n$ = address bits, $B$ = bytes per line, $L$ = total lines, $w$ = ways, $S=L/w$ = sets, and $A$ = the address being split.

Recall The three formulas we keep reusing

Offset bits ::: ${\log }_{2}B$ Index bits ::: ${\log }_{2}S$ where $S=L/w$ Tag bits ::: $n-{\log }_{2}S-{\log }_{2}B$

---

Example 1 — Cell A: direct-mapped, clean split

Forecast: before reading on, guess — how many offset bits does a 32-byte line need? And since it's direct-mapped, is the index big or small?

1. Offset bits $={\log }_{2}B={\log }_{2}32=5$. Why this step? Inside a 32-byte line there are 32 nameable bytes; it takes exactly 5 bits to count $0\dots 31$.
2. Sets $S=L/w=128/1=128$, so index bits $={\log }_{2}128=7$. Why this step? Direct-mapped means one line per set, so there are as many rows as lines.
3. Tag bits $=n-\text{index}-\text{offset}=16-7-5=4$. Why this step? Every address bit not spent on picking a row or a byte must be stored and compared to confirm identity.
4. Split $A=$ 0x1234. In binary, 0x1234 = 0001 0010 0011 0100.
   • Offset = low 5 bits = 10100 = $20$.
   • Index = next 7 bits = bits 11..5 = 0010001 wait — peel carefully: bits (high→low) are 0001 0010 0011 0100; strip low 5 (10100), left with 0001 0010 001; low 7 of that = 0010001 = $17$.
   • Tag = top 4 bits = 0001 = $1$.

Verify: reassemble $\text{tag}\cdot (S\cdot B)+\text{index}\cdot B+\text{offset}=1\cdot 4096+17\cdot 32+20=4096+544+20=4660=\text{0x1234}$. ✓ Bits add: $4+7+5=16=n$. ✓

---

Example 2 — Cell B & I: 4-way, then invert to find $w$

Forecast: in part (b), do we need more ways or fewer ways to make the tag bigger?

Part (a):

1. Offset $={\log }_{2}64=6$. Why? line size only.
2. $S=L/w=1024/8=128$, index $={\log }_{2}128=7$. Why? 8 lines share each set, so $8\times$ fewer rows than lines.
3. Tag $=32-7-6=19$. Why? leftover.

Part (b) — invert:

1. We want tag $=22$, so index $=n-\text{tag}-\text{offset}=32-22-6=4$ bits. Why this step? The address is a fixed budget of 32 bits; fixing tag and offset pins the index.
2. Index $=4$ bits ⇒ $S=2^4=16$ sets. Why? index bits and set count are tied by ${\log }_{2}S$.
3. $w=L/S=1024/16=64$-way. Why? sets and ways always multiply to total lines.

Verify: part (a) bits $6+7+19=32$ ✓. Part (b): with $w=64$, $S=16$, index $={\log }_{2}16=4$, tag $=32-4-6=22$ ✓ — and bigger tag came from more ways (fewer sets), matching the parent's "tag grows by ${\log }_{2}w$" rule: from part (a)'s 8-way (tag 19) to 64-way, $w$ went $\times 8$, so tag $+{\log }_{2}8=+3\Rightarrow 22$. ✓

---

Example 3 — Cell C: fully associative (zero index bits)

Forecast: with everything in one set, which field disappears?

1. Fully associative ⇒ $S=1$, so index $={\log }_{2}1=0$ bits. Why this step? One giant set means there is no "which row?" question — any line may live anywhere.
2. Offset $={\log }_{2}64=6$. Why? still one line's worth of bytes to name.
3. Tag $=32-0-6=26$. Why? every non-offset bit is now identity, because the hardware must compare against every slot's tag.
4. Bit-level split. Write the low 16 bits of $A$: 0x1F80 = 0001 1111 1000 0000. There are 32 bits total; the 16 higher bits are all 0. Now cut off the low 6 as offset and take everything above as the 26-bit tag:
   • Offset = low 6 bits = 00 0000 = $0$.
   • Index = 0 bits (there is no index field at all).
   • Tag = the 26 bits above bit 5. From 0001 1111 1000 0000, dropping the low 6 leaves 0001 1111 10, and padding the 16 unwritten high zeros gives the 26-bit value 00000000000000 0001111110 = $126$. Equivalently the tag is the block number $\lfloor A/B\rfloor =\lfloor 8064/64\rfloor =126$.

Figure s02 caption: (this figure serves Example 4; the bit walkthrough above is the s03-style split for Example 3 done in text). The key point to see here: the two scissor cuts of s01 collapse to one cut (offset only) because the index field has width zero — the whole left part is tag.

Verify: reassemble tag$\cdot B$ + offset $=126\cdot 64+0=8064=\text{0x1F80}$ ✓. Note the offset is 0 because 0x1F80 is a multiple of 64 (line-aligned). See Cache associativity & replacement policies for why fully associative needs a replacement policy but no index.

---

Example 4 — Cell D: the offset-boundary trap

Forecast: the index looks like it should be the 3rd-and-4th hex nibbles 0xBE. Bet against yourself: will it be?

Figure s02 (below) draws the low 16 bits of 0xDEADBEEF as a row of bit-cells. The low 6 (accent red) are the offset; the next 8 (black bracket) are the index. Watch how the index bracket starts in the middle of a hex nibble, not on a nibble boundary — that is the whole trap, made visible.

1. Offset $=6$, index $={\log }_{2}256=8$. So the low 14 bits are offset+index. Why this step? We must strip offset first; the index is bits 13..6, not bits 15..8.
2. 0xDEADBEEF low 16 bits = BEEF = 1011 1110 1110 1111. Low 14 bits = 11 1110 1110 1111. Why? 14 = 8 index + 6 offset.
3. Offset = low 6 = 101111 = 0x2F = byte $47$. Why? lowest ${\log }_{2}B$ bits.
4. Index = next 8 bits (bits 13..6) = 11111011 = 0xFB = set $251$. Why? 6 is not a multiple of 4, so the index straddles a hex boundary — the naive nibble read 10111011 is wrong.

Verify: naive-nibble answer 0xBE? No — bits 13..6 of 0xBEEF are 11111011 = 0xFB, confirming the trap. Numeric: $\lfloor \text{0xDEADBEEF}/64\rfloor \mathrm{mod}256=\lfloor 3735928559/64\rfloor \mathrm{mod}256=58373883\mathrm{mod}256=251$ ✓.

---

Example 5 — Cell E: zero and sub-line addresses (degenerate)

Forecast: which of these three lands in set 0? Which lands in set 1?

1. Offset $={\log }_{2}16=4$, index $={\log }_{2}64=6$, tag $=16-6-4=6$. Why? standard split, computed once for all three.
2. (i) $A=0$: every bit is zero ⇒ tag 0, index 0, offset 0. Why? the smallest address is the origin of line 0, byte 0.
3. (ii) $A=15$: 0000 0000 0000 1111. Offset = 1111 = $15$; index = $0$; tag = $0$. Why? $15<B=16$, so it's still inside line 0 — only the offset moved to the last byte.
4. (iii) $A=16$: 0000 0000 0001 0000. Offset = 0000 = $0$; index = 000001 = $1$; tag = $0$. Why? $16=B$ is the first byte of the next line, so we roll into set 1, offset 0.

Verify: block numbers $\lfloor 0/16\rfloor =0$, $\lfloor 15/16\rfloor =0$, $\lfloor 16/16\rfloor =1$; sets $=0,0,1$ ✓. Case (ii) shows the degenerate "sub-line" address never leaves set 0. This is exactly spatial locality at work — bytes 0–15 travel together.

---

Example 6 — Cell F: line-size sweep (offset moves, index reacts)

Forecast: bigger lines — does the index shrink or grow?

Figure s03 (below) stacks the two address splits ($B=16$ on top, $B=128$ below) as bit-width bars. The accent-red offset bar grows by 3 as we go to the fatter line, while the index bar shrinks by exactly 3 — the arrow shows that trade. The tag bar is the same width in both rows: that is the punchline.

1. Number of lines $L=\text{total bytes}/B$. For $B=16$: $L=16384/16=1024$; for $B=128$: $L=16384/128=128$. Why this step? total data is fixed, so a fatter line means fewer lines.
2. $B=16$: offset $={\log }_{2}16=4$; direct-mapped ⇒ $S=L=1024$, index $=10$; tag $=32-10-4=18$.
3. $B=128$: offset $={\log }_{2}128=7$; $S=L=128$, index $=7$; tag $=32-7-7=18$. Why? offset gained 3 bits, index lost 3 bits — they trade one-for-one when total bytes is fixed.
4. Observe: tag stayed 18 in both. Why? $\text{tag}=n-{\log }_2(\text{total bytes})$, and total bytes didn't change: $18=32-{\log }_{2}16384=32-14$.

Verify: $B=16$: $4+10+18=32$ ✓; $B=128$: $7+7+18=32$ ✓; both give ${\log }_2(\text{total data bytes})=\text{index}+\text{offset}=14$ ✓.

---

Example 7 — Cell G: 64-bit address (only tag grows)

Forecast: the cache geometry is identical — so which single field absorbs all 48 extra bits?

1. Offset $={\log }_{2}32=5$ — unchanged. Why? offset depends only on $B$.
2. Index $={\log }_{2}128=7$ — unchanged. Why? index depends only on $S$, and $S$ didn't change.
3. Tag $=n-7-5=64-12=52$. Why? all $64-16=48$ extra address bits pile into the tag.

Verify: $52+7+5=64$ ✓; compared to Example 1's 4-bit tag, the tag grew by exactly $64-16=48$ ✓. Real 64-bit machines often use fewer physical bits — see Virtual vs physical addressing (VIPT/PIPT) and TLB and page tables for why the tag is usually built from the physical address.

---

Example 8 — Cell H: word-problem, hits and misses on a loop

Forecast: how many of these 17 accesses actually go to DRAM?

1. Offset $={\log }_{2}64=6$. So a line covers 64 bytes = 16 floats. Why this step? we need the block boundary to see who shares a line.
2. Line of 0x1000: block $=\lfloor \text{0x1000}/64\rfloor =4096/64=64$. Addresses 0x1000 through 0x103F all have block $64$ ⇒ same line. Why? 0x103F = 4159, $\lfloor 4159/64\rfloor =64$; 0x1040 = 4160, $\lfloor 4160/64\rfloor =65$ — new line.
3. So 0x1000 misses (cold — fetches the whole line), and the next 15 reads 0x1004…0x103C hit. Then 0x1040 misses (new line 65). Why? first touch of a line is a compulsory miss; the rest of that line rides along for free — that's spatial locality paying off.

Verify: 17 accesses = addresses 0x1000 (off 0) up to 0x1040 (off 0 of next line), stride 4. Line-64 accesses: offsets $0,4,\dots ,60$ = 16 accesses, of which 1 miss + 15 hits. Then 0x1040 = 1 miss. Total misses $=2$, hits $=15$. Miss rate $=2/17\approx 11.8\%$ ✓. With a 100 ns miss vs ~1 ns hit (Memory hierarchy and latency numbers), the line fetch amortizes beautifully.

---

Recall check

Recall Rapid-fire (cover the answers)

Fully associative ⇒ how many index bits? ::: Zero, because $S=1$ and ${\log }_{2}1=0$. If total bytes is fixed, do tag bits change when line size changes? ::: No — tag $=n-{\log }_2(\text{total bytes})$, independent of $B$. Given tag $=22$, $n=32$, $B=64$, $L=1024$: what is $w$? ::: $64$-way (index $=4$, $S=16$, $w=L/S=64$). For 0xDEADBEEF, 6 offset + 8 index bits: which set? ::: $251$ (0xFB) — strip offset first, index is bits 13..6. Address 16 with $B=16$ lands in which set (direct-mapped)? ::: Set 1, offset 0 — first byte of the next line. Loop over 0x1000…0x1040 stride 4, $B=64$, empty cache: hits and misses? ::: 2 misses, 15 hits.

---

Back to the parent: Cache lines, tags, index, offset (index 4.1.10). Related depth: Cache associativity & replacement policies, Cache coherence (MESI).