Visual walkthrough — Cache coherence at scale (directory-based)
We will also see why we need those bits at all: what breaks if we throw the sharer list away.
Step 1 — What are we even tracking? Blocks and cores
WHAT. Draw the machine as two rows of boxes. The bottom row is memory, sliced into equal chunks called cache blocks (also "cache lines"): the smallest unit of data a cache moves around, typically 64 bytes. The top row is the cores, each with its own small cache.
WHY. Before we can count bits, we need to name the two things the directory size depends on. Everything scales with how many blocks exist and how many cores could want them.
PICTURE. Look at the figure. Each memory block is a lavender tile. We label the count of blocks and the count of cores .
is the number of what?
is the number of what?
Step 2 — One entry per block: what must a single entry answer?
WHAT. Zoom into one memory block . Ask: to keep everyone's copies consistent, what does the hardware need to know about right now?
WHY. The entire cost is (one entry) × M. So the design problem shrinks to designing one entry. If we design it too fat, we pay times the fat. This is why we obsess over single bits.
PICTURE. The figure shows one block and two questions floating above it: "What state?" and "Who has it?" These are the only two facts a coherence protocol ever acts on.
Step 3 — Encoding the "What state?" answer: 2 bits
WHAT. The state has exactly three possibilities. Enumerate them, then count the bits needed to name one of three things.
WHY. To store one of distinct labels you need bits, because each bit doubles how many labels you can distinguish (1 bit → 2 labels, 2 bits → 4 labels). We use and not anything else because bits are binary: the question "how many yes/no switches name this many options?" is .
PICTURE. Three coral chips — Uncached, Shared, Modified — and a 2-bit code on each. Two bits give four codes; three states fit (one code spare).
Why not 1 bit for state?
Step 4 — Encoding the "Who has it?" answer: try the naive way first
WHAT. First attempt: store the IDs of the sharers as a list. Each core ID needs bits (name one of cores). If up to all cores can share, a full list costs bits.
WHY. We try this because it feels compact when few cores share. Watching it fail teaches us why the real design (Step 5) exists.
PICTURE. The figure shows a Shared block with 3 IDs stored as numbers (001, 111, 1001), and a warning: when all 64 cores share, the list explodes to bits — worse than a plain bit per core.
Step 5 — Encoding "Who has it?" the winning way: one bit per core
WHAT. Replace the list with a sharer bit-vector: a row of bits, bit = 1 if core holds a copy, 0 otherwise.
WHY. Fixed width ( bits, always), and it answers every protocol question in one look: "who to invalidate?" = "which bits are 1?". No length surprises. This is why real full-map directories use it.
PICTURE. A 64-slot ribbon. Cores 0, 2 lit (bits set) → Shared with Sharers . Below, the same ribbon with a single bit lit → Modified, and that one set bit is the owner.
In a full-map vector, where is the owner stored when Modified?
Step 6 — Assemble one entry, then multiply by
WHAT. Stack Step 3 and Step 5: one entry = 2 state bits + N vector bits = bits. There is one entry per block, and there are blocks.
WHY. This is the final composition. The directory is just identical rows, each wide — a rectangle of bits. Its area is width × height.
PICTURE. A grid: rows tall, each row split into a 2-bit coral state chunk and an -bit lavender vector chunk. Total area annotated as .
Step 7 — Plug in the parent's numbers (and feel the scale)
WHAT. Use , blocks.
WHY. A formula you cannot evaluate is a fog. We land it on the 132 MB the parent claims, and see where the megabytes come from.
PICTURE. A bar: the 2 state bits are a sliver; the 64 vector bits dominate each entry. The overhead is almost entirely "one bit per core, per block."
Where do ~97% of the directory bits go?
Step 8 — The degenerate cases (never leave a scenario undrawn)
WHAT. Push the formula to its edges so nothing surprises the reader.
WHY. A formula must survive its own extremes; each extreme reveals why a bit is present.
PICTURE. Three mini-panels: , Uncached row, all-shared row.
The one-picture summary
Everything above, compressed: from " blocks, cores" to the bit rectangle to the 132 MB number, with each contribution colour-coded.
Recall Feynman retelling — say it back in plain words
Imagine memory is a huge wall of little cubbies (each one cache-block sized), and you have roommates (cores), each with a pocket where they can carry a copy of any cubby's contents. To avoid chaos when someone changes a copy, we keep a clipboard with one line per cubby. Each line writes down just two things: (1) a tiny 3-way status — empty / shared-read-only / one-person-changed-it — which needs 2 boxes to check because two yes/no boxes can label up to four things and we only have three; and (2) a row of tick-boxes, one per roommate, ticked if that roommate is holding a copy. We chose tick-boxes over writing down names because names get long and variable, but tick-boxes are always the same width and instantly tell us everyone to notify on a change. Notice the changer's identity comes free: if only one box is ticked in "changed-it" mode, that ticked box is the changer. So one line = boxes, and there are lines, giving boxes total. Put in 16 million cubbies and 64 roommates and each line is 66 bits, and the whole clipboard weighs 132 MB — nearly all of it those roommate tick-boxes. That heaviness is exactly why real machines cheat: split the clipboard across NUMA homes, or only keep lines for cubbies someone actually holds.
See also: Cache coherence protocols (MESI, MOESI) · NUMA architectures · Interconnect topologies · Memory consistency models · Cache line false sharing · back to the parent topic.