Cache line size and tags: Visual walkthrough — Hardware deep dive

Before we start, one word we will use constantly:

Step 1 — A memory address is just a house number

WHAT. Main memory is one enormous row of numbered byte-boxes: box $0$ , box $1$ , box $2$ , … up to the last box. A memory address is simply the number written on a box.

WHY. Before we can split an address we must agree what it is. It is not a mysterious code — it is a plain house number on a very long street. If the CPU can produce addresses from $0$ up to $2^{N} - 1$ , we call it an $N$ -bit address space, because it takes exactly $N$ bits to write the biggest house number.

PICTURE. Look at the street of byte-boxes below. The amber box is the byte the CPU asked for; its number, written in binary underneath, is the address.

Step 2 — The cache brings a whole line, so the low bits name a byte inside the line

WHAT. The cache never fetches one byte; it fetches a fixed clump of $L$ neighbouring bytes called a cache line. Choose $L$ as a power of two — say $L = 64$ bytes. Once a whole line is in the cache, we still need to say which byte of the 64 the CPU wanted. That job goes to the lowest bits of the address: the offset.

WHY these bits, and why this many? The bytes inside one line are numbered $0, 1, \dots, L - 1$ . To count $L$ possibilities we need exactly the number of bits that satisfies " $2^{?} = L$ ". That question — what power gives me $L$ ? — is answered by $lo g_{2}$ . That is the whole reason $lo g_{2}$ appears: it is the inverse of " $n$ bits count $2^{n}$ things".

b = "what power of 2 is L ?" lo g_{2} bytes per line L

For $L = 64$ : $b = lo g_{2} 64 = 6$ , because $2^{6} = 64$ . So the bottom 6 bits of every address are the offset.

PICTURE. One cache line unrolled into its $64$ byte-slots, slot numbers written in $6$ -bit binary. The bottom bits of the address are those slot numbers.

Step 3 — Peel off the offset, and the rest is a line number

WHAT. Take any address and mentally shift the bottom $b$ bits away. What remains is a line number: it names which $L$ -byte clump this byte belongs to, out of all clumps in memory.

WHY. Two addresses in the same line share everything except the offset bits. So dropping those $b$ bits is the same as integer-dividing the address by $L$ . The result identifies the line, not the byte — and that is the number the cache will actually reason about.

PICTURE. The full address bar with a scissors cutting off the low $b$ bits; the amber remainder is labelled "line number".

Step 4 — The cache has only a few slots, so line numbers must wrap around

WHAT. The cache is small: in a direct-mapped cache it has some number of slots, call it $S$ slots (also a power of two). There are far more lines in memory than slots on the cache. So many different lines are forced to share the same slot. The rule for which slot a line lands in is: take the line number and keep only its low bits — that is the index.

WHY. "Keep the low bits of the line number" is the same as "line number mod $S$ " (remainder after dividing by $S$ ). Mod is chosen because it maps an unlimited range of line numbers onto a fixed set of $0 \dots S - 1$ slots, cheaply, using no arithmetic — you just read the bits. To count $S$ slots we again ask "what power of two is $S$ ?", so:

i = lo g_{2} S, S = \frac{C}{L \cdot A}

Here $C$ = total cache size in bytes, $L$ = line size, $A$ = associativity (how many lines share a slot; $A = 1$ for direct-mapped, more for set-associative). Dividing $C$ by $L$ gives the number of lines the cache holds; dividing again by $A$ groups them into slots (sets).

PICTURE. A long column of memory lines on the left, an arrow "mod $S$ " folding them onto a short column of $S$ cache slots on the right — several memory lines landing on the same slot.

Step 5 — Different lines landed on the same slot, so we need a tag to tell them apart

WHAT. Because many lines fold onto one slot (Step 4), knowing the slot is not enough — the CPU must confirm the line sitting there is the one it wanted. The tag is everything left over: the high bits of the address, above index and offset. The cache stores this tag beside the data, and on every access it compares.

WHY. Index tells you where to look; but "where" is ambiguous (Step 4's folding). The tag is the leftover bits that make the line number unique. Since address = tag-bits + index-bits + offset-bits and they must sum to $N$ :

t = total bits N - index i - offset b

PICTURE. The full $N$ -bit address bar coloured in three zones — amber Tag (high), cyan Index (middle), white Offset (low) — with a bracket showing $t + i + b = N$ .

Step 6 — Watch a lookup happen: hit vs miss

WHAT. Put the three fields to work. (1) Use the index to jump to a slot. (2) Read the tag stored there and compare it to the address's tag. (3) Also check the valid bit — a single bit meaning "this slot holds real data, not garbage from power-on". If tag matches and valid $= 1$ → hit; use the offset to return the byte. Otherwise → miss; go fetch the line from memory.

WHY. This is the whole payoff. Index makes the lookup $O (1)$ (one jump, no searching). Tag makes it correct (rejects the wrong line that folded onto the same slot). Valid makes it safe (a cold, empty cache never falsely reports a hit). Missing any one of these breaks the machine.

PICTURE. Two panels: top = HIT (stored tag $=$ address tag, valid $1$ , green check, byte returned). Bottom = MISS (tags differ, red cross, arrow back to memory).

Step 7 — Edge cases: the degenerate corners you must survive

WHAT / WHY / PICTURE. A formula you cannot break at the corners is a formula you understand. Four corners:

Line size $= 1$ byte ( $L = 1$ ). Then $b = lo g_{2} 1 = 0$ : no offset bits at all. Every byte is its own line. Legal, just wasteful — you lose all spatial locality.
Whole memory fits in cache ( $C =$ memory size, $A = 1$ ). Then $i$ grows until $t = 0$ : no tag bits. Every line has a permanent home, no folding, so no tag is needed to disambiguate.
Fully associative ( $A =$ number of lines, so $S = 1$ ). Then $i = lo g_{2} 1 = 0$ : no index bits. One giant slot; the line may sit anywhere, so the tag must carry all the line-number bits.
Byte-offset zero / line-aligned address. The bottom $b$ bits are all $0$ : the CPU asked for the first byte of the line. Nothing special breaks — offset just reads $0$ .

In every corner, one of $t, i, b$ shrinks to $0$ but the identity $t + i + b = N$ still holds. No case escapes it.

Step 8 — A full numeric run, matching Worked Example 2

WHAT. Take $C = 32 KiB = 32768$ B, $L = 64$ , $A = 1$ , $N = 32$ . Then $b = 6$ , lines $= 32768/64 = 512$ , so $i = lo g_{2} 512 = 9$ , and $t = 32 - 9 - 6 = 17$ . Now decode address 0x0012A40 $= 76352$ .

WHY. Numbers make the pictures concrete and let us machine-check the split. Slicing the $32$ -bit pattern from the top: Tag $=$ high $17$ bits $= 2$ , Index $=$ next $9$ bits $= 169$ , Offset $=$ low $6$ bits $= 0$ .

PICTURE. The $32$ -bit binary of $76352$ laid out with the $17∣9∣6$ cut lines drawn in, each slice's decimal value labelled underneath.

The one-picture summary

Everything above compressed into a single diagram: an address enters at the top; the low $b$ bits split off as Offset, the next $i$ bits fold (mod $S$ ) to pick the slot via Index, the top $t$ bits become the Tag that is compared against what the slot stores — hit or miss below.

Recall Feynman retelling — say it back in plain words

Memory is a mile-long street of numbered byte-boxes; an address is a box's number. The cache is greedy: instead of one box it grabs a whole neighbourhood of $L$ boxes — a line — because you usually want the next box soon. So the bottom $b = lo g_{2} L$ bits of the address just say which box in the neighbourhood you meant: the offset. Chop those off and the number that's left names the whole neighbourhood — the line number. But the cache has only $S$ parking slots, way fewer than there are neighbourhoods, so it folds line numbers onto slots by keeping their low $i = lo g_{2} S$ bits: the index — that's the parking rule. Many neighbourhoods park in the same slot, so when you arrive you must check a label to be sure the car in the slot is yours: the leftover high $t = N - i - b$ bits are that label, the tag, and there's a tiny valid flag saying the slot isn't empty. Lookup is three moves: index drives you to the slot, tag confirms it's the right line, offset grabs your byte. And no matter how you size the cache — tiny lines, huge associativity, memory that fits entirely — the three widths always add back up to $N$ .

Connections

Cache line size and tags (index 5.4.4) — the parent result this page derives from zero.
5.4.04 Cache line size and tags (Hinglish) — same content in Hinglish.
5.4.01-Cache-fundamentals — why caching exists at all.
5.4.02-Direct-mapped-caches — the $A = 1$ machine we walked through.
5.4.03-Set-associative-caches — index becomes a set index when $A > 1$ .
5.4.05-Cache-miss-types — what the miss branch of Step 6 leads to.
5.4.08-Write-policies — where the dirty bit joins the valid bit.
6.2.01-Virtual-memory-pages — the same tag/index/offset trick for pages.
3.1.04-Spatial-locality — the reason Step 2 fetches a whole line.