Cache coherence at scale (directory-based): Foundations

Before you can read the parent note Cache coherence at scale (directory-based), you need to understand every word and symbol it throws at you. We build each one from nothing — a picture first, then the meaning, then why the topic needs it.

1. A core, and why it has a private cache

In figure s01, follow the violet boxes on top — those are the cores. Directly under each hangs its own orange cache; notice there are four separate orange boxes, not one shared one. That separateness is the whole point: trace the magenta arrow and you'll see the same address copied into two different orange caches at once. All of them connect down to the single navy bar — the shared main memory.

2. Memory blocks, addresses, and the symbols $A$ , $B$ , $N$ , $M$

The parent note writes things like "block $B$ at address $A$ ". Let's earn every letter.

Recall

What does one block represent, physically? ::: A fixed-size chunk of memory (e.g. 64 bytes) that caches move and track as a single unit. How do you get block number $B$ from byte address $A$ ? ::: $B = ⌊ A / BlockSize ⌋$ — divide by the block size and round down; the remainder (offset) is discarded. In $M \times (2 + N)$ , what is the $N$ counting? ::: One bit for each of the $N$ cores — the sharer bit-vector.

3. State: the words Uncached, Shared, Modified — and the " $2$ " bits

Every copy of a block is in some state. The parent uses three. Think of a block as a shared library book.

In figure s03 the three coloured boxes are the three states side by side; read the small navy caption under each to see what it says about main memory (valid vs. stale).

4. Sharers, the bit-vector, and the symbol $⟨ \cdot, \cdot ⟩$

In figure s04, each square is one core's bit; the magenta squares are 1 (has a copy) and the pale ones are 0. Count the magenta squares — that's the size of the sharers set. The caption reads off which cores those are.

5. The Home node / Home Directory (HD)

6. Snooping, messages, hops, and O(N) vs O(N²)

The protocol works by cores mailing each other. Let's name the mail and the counting — but first the old approach directories replace.

Intuition Where each bound actually comes from (per operation, worst case)

Count the messages for one cache miss:

Snooping: one miss forces a broadcast that every other core must receive — that's $N - 1$ messages for a single operation. If all $N$ cores are missing, total traffic is $N \times (N - 1) \approx N^{2}$ . This is the worst case and also the typical case, because a broadcast always reaches everyone regardless of who actually cares.
Directory: one miss sends 1 message to the home, then the home messages only the sharers. In the average case a block has just 1–3 sharers, so that's a small constant — roughly $O (1)$ per operation, and $O (N)$ across $N$ simultaneously-missing cores. The worst case is a block shared by all $N$ cores being written: the home must send $N - 1$ invalidates — but this is rare, whereas broadcast pays the full price every single time. At $N = 64$ a broadcast round is ~4000 messages where the directory typically sends a handful. This gap is the entire reason directories exist.

7. Invalidate, Ack, and Write-Back

The prerequisite map

Read it top-down: cores with private caches create duplicate copies (the problem); state (2 bits) + sharers ( $N$ bits) describe each copy; the home directory stores those in an entry; messages act on entries; the traffic count (snooping vs directory) justifies the whole design.

Equipment checklist

Cover the right side and answer aloud. If you can, you're ready for the parent note.

What is a core, and why does each having its own cache create a problem?

A core is an independent instruction-runner; because each has a private cache, one address can live in several caches at once and their copies can disagree.

How do you turn a byte address

A

into a block number

B

B = ⌊ A / BlockSize ⌋

— divide by the block size and round down; the leftover offset bits are discarded.

Why does the state field cost exactly 2 bits?

Three states (Uncached/Shared/Modified) need at least 2 bits, since 1 bit gives only 2 patterns and 2 bits give 4 (three used, one spare).

What does a directory entry hold when the block is Uncached?

State bits

= 00

and the sharer bit-vector is all zeros — nobody holds a copy.

In a bit-vector 0101 for 4 cores, who holds copies?

Cores 0 and 2 (rightmost bit = core 0).

What does

⟨ State, Owner/Sharers ⟩

mean?

A directory entry: a paired bundle of the block's state and either its single owner (Modified) or its set of sharers (Shared).

What is snooping, and how does it differ from a directory?

Snooping is broadcast coherence where all cores listen to a shared bus and every miss is heard by everyone; a directory instead records who has each block and messages only them.

What is the home node (HD) and why is it needed?

The fixed place that stores a given address's directory row — a known desk every core can ask "who has this block?"

Why is broadcast

O (N^{2})

but directory

O (N)

Broadcast: each of

N

cores messages all

N - 1

others → ~

N^{2}

, every time. Directory: each request goes to 1 home + a few sharers (avg 1–3) → grows with

N

Why does the directory count Invalidate-Acks before granting a write?

To guarantee every old reader has killed its copy first, so no two caches hold different values for one address.