Cache line size and tags: Exercises — Hardware deep dive

This page is your training ground for the parent topic. Every problem below is fully solved inside a collapsible callout — try it first, then reveal. The levels climb from recognising the fields to designing a cache from scratch.

Before we start, one figure fixes the vocabulary so no symbol is ever unexplained.

Level 1 — Recognition

Exercise 1.1

A cache uses 128-byte lines. How many offset bits does each address need?

Recall Solution 1.1

Offset must name every byte inside one line. There are $L = 128$ byte-positions. $b = lo g_{2} 128 = lo g_{2} 2^{7} = 7 bits .$ Why $lo g_{2}$ ? 128 distinct positions need exactly enough bits to count $0$ through $127$ , and $2^{7} = 128$ . So 7 bits.

Exercise 1.2

A direct-mapped cache has $2048$ lines. How many index bits?

Recall Solution 1.2

Direct-mapped means $A = 1$ , so number of sets = number of lines = $2048$ . The index picks one slot out of $2048$ . $i = lo g_{2} 2048 = lo g_{2} 2^{11} = 11 bits .$ 11 bits.

Exercise 1.3

Given the field widths $t = 20$ , $i = 6$ , $b = 6$ , what is the total address width $N$ ?

Recall Solution 1.3

The three fields are the whole address, edge to edge — no bit is left over or shared. $N = t + i + b = 20 + 6 + 6 = 32 bits .$ 32-bit address space.

Level 2 — Application

Exercise 2.1

A 16 KiB direct-mapped cache uses 32-byte lines on a 32-bit machine. Find $b$ , $i$ , $t$ .

Recall Solution 2.1

Step 1 — offset. $L = 32 = 2^{5} \Rightarrow b = 5$ . (names each byte in the line) Step 2 — number of lines. $C = 16 KiB = 16384$ B. Lines $= \frac{C}{L} = \frac{16384}{32} = 512 = 2^{9}$ . Step 3 — index. $A = 1$ , so $i = lo g_{2} 512 = 9$ . (names each slot) Step 4 — tag. $t = N - i - b = 32 - 9 - 5 = 18$ . Answer: [18-bit Tag | 9-bit Index | 5-bit Offset].

Exercise 2.2

Same cache as 2.1. The CPU requests address 0x0000_2C64. Split it into Tag / Index / Offset.

Recall Solution 2.2

First, 0x2C64 = $2 \cdot 4096 + 12 \cdot 256 + 6 \cdot 16 + 4 = 8192 + 3072 + 96 + 4 = 11364$ (decimal).

In 32-bit binary: 0000 0000 0000 0000 0010 1100 0110 0100

Split from the top as [18 tag | 9 index | 5 offset]:

Offset = low 5 bits = 0 0100 = 4.
Index = next 9 bits = 011 0011 shifted... let's compute directly. Drop the offset: $⌊ 11364/32 ⌋ = 355$ is the line number. Index $= 355 mod 512 = 355$ .
Tag = high bits $= ⌊ 355/512 ⌋ = 0$ .

Answer: Tag $= 0$ , Index $= 355$ , Offset $= 4$ . Check: $Tag \cdot 2^{14} + Index \cdot 2^{5} + Offset = 0 + 355 \cdot 32 + 4 = 11360 + 4 = 11364$ ✓ (note $i + b = 14$ , so tag is multiplied by $2^{14}$ ).

Exercise 2.3

For the cache in 2.1, how many bits of tag storage does the whole cache use (tag + valid bit, no dirty bit)?

Recall Solution 2.3

Per line: tag $= 18$ bits, valid $= 1$ bit $\Rightarrow 19$ bits. There are $512$ lines. $512 \times 19 = 9728 bits = 1216 bytes \approx 1.19 KiB .$

Level 3 — Analysis

Exercise 3.1

Two engineers argue about a fixed 32 KiB, direct-mapped, 32-bit cache. Engineer A doubles the line size from 64 B to 128 B. What happens to (a) index bits, (b) tag bits, (c) total tag-storage bytes? Explain each direction.

Recall Solution 3.1

Cache size $C = 32768$ B stays fixed. $N = 32$ , $A = 1$ .

Case 64 B: $b = 6$ . Lines $= 32768/64 = 512 = 2^{9} \Rightarrow i = 9$ . $t = 32 - 9 - 6 = 17$ . Tag storage (tag + valid) $= 512 \times (17 + 1) = 512 \times 18 = 9216$ bits $= 1152$ B.

Case 128 B: $b = 7$ . Lines $= 32768/128 = 256 = 2^{8} \Rightarrow i = 8$ . $t = 32 - 8 - 7 = 17$ . Tag storage $= 256 \times (17 + 1) = 256 \times 18 = 4608$ bits $= 576$ B.

(a) Index: $9 \to 8$ — decreases by 1, because doubling line size halves the number of lines. (b) Tag: $17 \to 17$ — unchanged here. We lost 1 offset bit but also lost 1 index bit; they cancel ( $t = N - i - b$ , and $i + b$ stayed at 15). (c) Tag storage: $1152 \to 576$ B — halved, because there are half as many lines, each carrying the same 18 metadata bits.

Exercise 3.2

A cache designer keeps line size $L = 64$ B and address width $N = 32$ , but grows the cache from 16 KiB to 64 KiB (both direct-mapped). Show that tag bits shrink and by how much.

Recall Solution 3.2

$b = lo g_{2} 64 = 6$ throughout.

16 KiB: lines $= 16384/64 = 256 = 2^{8} \Rightarrow i = 8$ . $t = 32 - 8 - 6 = 18$ . 64 KiB: lines $= 65536/64 = 1024 = 2^{10} \Rightarrow i = 10$ . $t = 32 - 10 - 6 = 16$ .

Growing the cache $\times 4$ adds $lo g_{2} 4 = 2$ index bits, which steals 2 bits from the tag: $18 \to 16$ . Intuition: a bigger cache has more slots, so more of the address is spent saying which slot — leaving fewer bits to distinguish blocks that land in the same slot.

Level 4 — Synthesis

Exercise 4.1

Design task. A 64-bit machine needs a 4-way set-associative cache, total size $C = 256$ KiB, line size $L = 64$ B. Compute sets, $b$ , $i$ , $t$ , and the total metadata (tag + valid + dirty) in KiB.

Recall Solution 4.1

Step 1 — offset. $L = 64 = 2^{6} \Rightarrow b = 6$ . Step 2 — total lines. $C / L = 262144/64 = 4096$ lines. Step 3 — sets. Set-associative packs $A = 4$ lines per set: $sets = \frac{C}{L \cdot A} = \frac{262144}{64 \cdot 4} = \frac{4096}{4} = 1024 = 2^{10} .$ So $i = lo g_{2} 1024 = 10$ (the index now names a set, not a single line). Step 4 — tag. $t = N - i - b = 64 - 10 - 6 = 48$ bits. Step 5 — metadata. Each of the $4096$ lines carries tag (48) + valid (1) + dirty (1) $= 50$ bits. $4096 \times 50 = 204800 bits = 25600 B = 25 KiB .$ Answer: 1024 sets, $b = 6$ , $i = 10$ , $t = 48$ ; metadata $= 25$ KiB.

Exercise 4.2

Same as 4.1 but make it direct-mapped (A=1), everything else identical. Which changes — $b$ , $i$ , or $t$ — and why does the tag grow?

Recall Solution 4.2

$b = 6$ (line size unchanged). Now sets $=$ lines $= C / L = 4096 = 2^{12} \Rightarrow i = 12$ . $t = 64 - 12 - 6 = 46$ bits.

Compared to 4.1: index rose $10 \to 12$ (+2) and tag fell $48 \to 46$ (−2)... wait — the tag shrank, not grew. With the same $C, L, N$ , direct-mapped has more sets ( $4096$ vs $1024$ ), so it needs more index bits and fewer tag bits.

Lesson: raising associativity (fewer sets) grows the tag; lowering it shrinks the tag. The set-associative version (4.1, $t = 48$ ) has the larger tag.

Level 5 — Mastery

Exercise 5.1

Reverse-engineering. You are told an address splits as [Tag | Index | Offset] with the lookup circuit using $i = 7$ index bits and $b = 8$ offset bits on a 32-bit machine, and the cache is 2-way set-associative. Recover $L$ , number of sets, total cache size $C$ , and $t$ .

Recall Solution 5.1

Line size: $b = 8 \Rightarrow L = 2^{8} = 256$ B. Sets: $i = 7 \Rightarrow$ sets $= 2^{7} = 128$ . Cache size: $C = sets \times A \times L = 128 \times 2 \times 256 = 65536$ B $= 64$ KiB. Tag: $t = N - i - b = 32 - 7 - 8 = 17$ bits. Sanity check via formula: $i = lo g_{2} (C / (L \cdot A)) = lo g_{2} (65536/ (256 \cdot 2)) = lo g_{2} (128) = 7$ ✓. Answer: $L = 256$ B, 128 sets, $C = 64$ KiB, $t = 17$ .

Exercise 5.2

Capstone trade-off. Two designs, both 32-bit, 16 KiB, direct-mapped:

Design P: $L = 16$ B.
Design Q: $L = 128$ B. Compute the metadata overhead fraction (tag + valid + dirty per line, over data bytes) for each, and state which wins on overhead and what each sacrifices.

Recall Solution 5.2

$C = 16384$ B, $N = 32$ , $A = 1$ .

Design P ( $L = 16$ ): $b = 4$ . Lines $= 16384/16 = 1024 = 2^{10} \Rightarrow i = 10$ . $t = 32 - 10 - 4 = 18$ . Metadata/line $= 18 + 2 = 20$ bits $= 2.5$ B. Data/line $= 16$ B. Overhead fraction $= 2.5/16 = 0.15625 = 15.625%$ .

Design Q ( $L = 128$ ): $b = 7$ . Lines $= 16384/128 = 128 = 2^{7} \Rightarrow i = 7$ . $t = 32 - 7 - 7 = 18$ . Metadata/line $= 18 + 2 = 20$ bits $= 2.5$ B. Data/line $= 128$ B. Overhead fraction $= 2.5/128 = 0.01953 = 1.953%$ .

Winner on overhead: Design Q — big lines amortise the fixed 20-bit tag block over far more data (2.0% vs 15.6%). The sacrifice: Q has only 128 lines vs P's 1024, so Q suffers more conflict misses and a higher miss penalty (128 B transfers). P wastes chip area on metadata but keeps lots of distinct slots. This is exactly the spatial-locality trade-off that lands most real CPUs at 64 B — the middle ground.

Recall One-line field recovery cheat card

From widths: $L = 2^{b}$ ; sets $= 2^{i}$ ; $C = 2^{i} \cdot A \cdot 2^{b}$ ; $t = N - i - b$ . To split an address value: offset $= addr mod 2^{b}$ ; line# $= ⌊ addr / 2^{b} ⌋$ ; index $= line# mod 2^{i}$ ; tag $= ⌊ line# / 2^{i} ⌋$ .

Connections

Cache line size and tags — the parent theory these drills exercise.
5.4.02-Direct-mapped-caches — L1–L3 assume $A = 1$ .
5.4.03-Set-associative-caches — L4–L5 introduce sets and the $\div A$ step.
5.4.05-Cache-miss-types — the conflict-miss cost behind the L5 trade-off.
5.4.08-Write-policies — where the dirty bit in the metadata counts comes from.
3.1.04-Spatial-locality — why bigger lines help at all.

#flashcards/hardware