Cache organization — direct-mapped, n-way set associative, fully associative: Visual walkthrough

We only assume you can count in binary. Everything else is earned.

Step 1 — What a memory address even is

WHAT. We draw the whole memory as a numbered strip and pick one address, say $m = 8$ bits: 1011 0101.

WHY. Everything the cache does is decided by looking at the bits of this number. Before we chop it, we must agree it is literally just "which byte, counting from 0."

PICTURE. In the figure, the strip of boxes at the bottom is main memory. The arrow points to the single byte our 8-bit address selects. Nothing clever yet — just a number pointing at a box.

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

$address = m bits, one per position b_{m - 1} b_{m - 2} \dots b_{1} b_{0}$

$m$ ::: total address width — how many bits the whole house number has.
Each $b_{i}$ ::: a single 0/1 bit. $b_{0}$ is the cheapest (rightmost, worth 1); $b_{m - 1}$ the most significant.

Step 2 — Why memory moves in blocks, not single bytes

WHAT. We group the memory strip into chunks of $B$ bytes. In the figure $B = 4$ , so boxes 0,1,2,3 are block 0; boxes 4,5,6,7 are block 1; and so on.

WHY. Once memory is grouped, an address answers two questions at once: which block? and which byte inside it? Those two questions are exactly the first cut we will make in the bits.

PICTURE. Coloured brackets group the strip into blocks. The same address as Step 1 now lands "inside block $k$ , at position $j$ ."

$block number k = ⌊ \frac{address}{B} ⌋, byte inside block j = address mod B$

$⌊ \cdot ⌋$ ::: "throw away the fraction" — dividing by $B$ and rounding down tells you which chunk you're in.
$mod B$ ::: the remainder — how far into the chunk you are.

Step 3 — The offset: the lowest bits are already the byte-inside-block

WHAT. We slice off the bottom $b$ bits of the address. Those bits are the offset: the byte's position inside its block.

WHY. We use $lo g_{2}$ (and not, say, multiplication) precisely because it answers the question "how many bits do I need to name $B$ different things?" — $b$ bits name exactly $2^{b} = B$ positions, no more, no waste.

PICTURE. The address bar is split for the first time: the pink tail on the right is the offset. Below it, the arrow shows those same bits pointing at one byte inside the highlighted block.

$b = lo g_{2} B ⟹ upper bits [\dots block number \dots] b bits [offset]$

$b$ ::: offset width. Depends only on block size $B$ — never on how the cache is organised.
upper bits ::: everything left over is the block number $k$ from Step 2.

Step 4 — The index: which set of hooks does this block belong to?

WHAT. Take the block number (the upper bits from Step 3) and slice off its lowest $s$ bits, where $s = lo g_{2} S$ . Those are the index: the set number.

WHY use the low block bits (mod), not the high ones? Because consecutive blocks $k, k + 1, k + 2$ then fall into different sets. That spreads a marching scan across many shelves instead of piling it on one — again serving spatial locality. Using $mod S$ (a power-of-two modulus) is once more just "keep the low $s$ bits."

PICTURE. Second cut appears: the blue middle field is the index, and its arrow points at one shelf (set) in the cache drawn above. The pink offset still points inside the block; the blue index picks the shelf.

$s = lo g_{2} S, set index = k mod S = (low s bits of the block number)$

$s$ ::: index width — counts sets, not ways. Fewer sets ⇒ fewer index bits.
$S = N / E$ ::: sets = total blocks divided by ways. Turn the "ways" knob $E$ up, $S$ goes down.

Step 5 — The tag: the leftover bits that prove identity

WHAT. Whatever bits are left after offset ( $b$ ) and index ( $s$ ) form the tag, of width $t = m - s - b$ .

WHY store a tag at all? Because the index alone is ambiguous — it names a set, not a block. Without the tag, two different memory blocks in the same set would look identical. The tag is the block's fingerprint.

PICTURE. The address bar is now fully cut into three coloured fields — yellow tag, blue index, pink offset — and $t + s + b = m$ is shown as the three widths summing to the full bar. Above, the chosen set's stored tag is compared to the address tag.

$t = m - s - b [tag] s = l o g_{2} S [index] b = l o g_{2} B [offset], t + s + b = m$

$t$ ::: tag width — "everything left over." Grows when index shrinks.
The whole bar ::: always exactly $m$ bits. The three pieces are a partition — no bit is used twice, none is lost.

Step 6 — The lookup, watched in slow motion

WHAT. We trace one access all the way through the hardware.

WHY compare in parallel across all $E$ ways? Because a block could be on any of the shelf's $E$ hooks, and we cannot afford to check them one at a time. That parallel bank of comparators is the hardware cost of associativity: exactly $E$ comparators fire per access.

PICTURE. The index arrow lights one shelf; $E$ little comparators each check one hook's tag against the yellow address tag; the AND-gate with the valid bit outputs HIT or MISS; on hit, the pink offset selects the byte.

valid bit ::: says "this hook actually holds real data" (not leftover garbage from power-on). Without it, a random stored tag could falsely match.
$E$ comparators ::: one per way. $E = 1$ ⇒ one comparator (cheap, direct-mapped). $E = N$ ⇒ $N$ comparators (dear, fully associative).

Step 7 — Edge case A: turn the knob to $E = 1$ (direct-mapped)

WHAT. The middle (index) field swells; the tag shrinks; each shelf shows a single hook.

WHY show this? It's the cheapest, fastest extreme — but blocks that share an index fight over the one hook, producing conflict misses even when the rest of the cache is empty.

PICTURE. Same 8-bit bar re-cut for $E = 1$ : fat blue index, thin yellow tag, one-hook shelves.

Step 8 — Edge case B: turn the knob to $S = 1$ (fully associative)

WHAT. The blue field vanishes; the bar is just tag + offset; the cache is one long shelf with $N$ hooks.

WHY the biggest tag here? A common trap: "anything goes anywhere, so nothing to identify." Wrong — precisely because a block can sit anywhere, nothing about its position tells you its identity, so the tag alone must carry it. This is the mirror image of Step 7.

PICTURE. 8-bit bar with no index: wide yellow tag, pink offset; one shelf of $N$ hooks, $N$ comparators lit.

Step 9 — The knob in between: $n$ -way, and the conflict it kills

WHAT. We replay the parent's Example 4 trace $0, 4, 0, 4, \dots$ with $B = 1$ , $N = 4$ lines.

WHY this is the whole point of associativity. In direct-mapped ( $E = 1$ , so 4 sets), blocks $0$ and $4$ both map to set $0$ (since $0 mod 4 = 0$ and, in the 2-set case, $0 mod 2 = 4 mod 2 = 0$ ) and evict each other every access → 100% miss. In 2-way (2 sets, 2 hooks each) they both fit on set 0's two hooks → 2 cold misses then all hits.

PICTURE. Left panel: 1-way, the two blocks ping-ponging on one hook (all red = misses). Right panel: 2-way, both resting on the shared shelf (green = hits after warm-up).

The one-picture summary

$t + s + b = m; s = lo g_{2} S, b = lo g_{2} B, S = \frac{N}{E}, N = S \cdot E$

Recall Feynman retelling — explain the whole walkthrough to a 12-year-old

An address is just a box number in a huge row of boxes (Step 1). We deliver boxes in small bundles called blocks, because neighbours travel together (Step 2). The last few digits of the number say which box inside the bundle — that's the offset, and it only depends on bundle size (Step 3). The next few digits pick which shelf the bundle is allowed to land on — the index (Step 4). The digits left over are a name tag we stick on the bundle so we know it's really ours (Step 5). To look something up: the index lights one shelf, we check every hook on it at once against the name tag plus a "this hook is real" light, and a match means found (Step 6). If every shelf has just one hook, delivery is fast but two bundles with the same shelf number keep bumping each other (Step 7, direct-mapped). If there's one huge shelf with every hook on it, nobody ever gets bumped but a worker must scan every hook and the name tags get long (Step 8, fully associative). In between, small shelves with a few hooks let friends share without bumping — killing the ping-pong misses (Step 9). It's all one slider: how wide the "shelf-picking" middle field is decides everything else.

Recall Why is the offset the same in Steps 7, 8, and 9?

Offset $b = lo g_{2} B$ depends only on block size $B$ , which was 64 bytes in every example. Organisation ( $E$ , $S$ ) never touches it.

Recall What happens to tag and index as you turn

$E$ from 1 up to $N$ ? Fixed $N = S \cdot E$ : raising $E$ shrinks $S = N / E$ , so index $s = lo g_{2} S$ shrinks and tag $t = m - s - b$ grows by the same amount. At $E = N$ the index vanishes and the tag is largest.