Cache coherence at scale (directory-based)

What is a directory-based protocol?

Why this design?

Broadcast = O(N²) bandwidth: Each of N cores generates traffic, and each message goes to N-1 cores.
Directory = O(N) bandwidth: Each request goes to 1 directory + sharers (typically 1-3 caches).
Physical constraint: Modern multi-chip systems (e.g., AMD EPYC, AWS Graviton) have no shared bus—directories enable coherence across separate chips.

Figure — Cache coherence at scale (directory-based)

For each memory block $B$ at address $A$ : $\text{Directory}[A] = \langle \text{State}, \text{Owner/Sharers} \rangle$ Note: The directory holds only metadata—the actual block data resides in main memory (or in the owning cache if Modified). The directory never duplicates the data payload.

State ∈ {Uncached, Shared, Modified}:

Uncached: No cache holds $B$ (data in memory is valid)
Shared: ≥1 caches have read-only copies (data in memory valid)
Modified: Exactly 1 cache has exclusive dirty copy (memory stale)

Owner/Sharers:

Modified → Owner = the single cache holding the dirty block (in a full-map vector, this is the one set bit)
Shared → Sharers = bit-vector or pointer list of cache IDs Why track sharers exactly? On a write, we must invalidate all shared copies. Without a list, we'd have to broadcast (defeating scalability).

Message flow: Read miss

Scenario: Core 2 reads address 0x1000, not in its cache.

Core 2 → Home directory (HD): Read-Request(0x1000)
HD checks state:
- Uncached: HD replies with data from memory, sets State=Shared, Sharers={2}
- Shared: HD adds Core 2 to Sharers, replies with data
- Modified (Owner=Core 5): HD forwards request to Core 5
If Modified: Core 5 → Core 2: Data-Reply(0x1000, data) + Core 5 → HD: Data-WriteBack(data) (HD updates memory, State=Shared, Sharers={2,5})
Core 2 installs block in cache as Shared

Why this path?

Only Core 2, HD, and (if needed) the owner receive messages—no broadcast.
Write-back on sharing: Modified owner must supply data because memory is stale (the directory itself never held the data—it only knew Core 5 was the owner).

Message flow: Write miss

Scenario: Core 3 writes to 0x2000, current State=Shared, Sharers={1,7,9}.

Core 3 → HD: Write-Request(0x2000)
HD checks state:
- Shared: HD sends Invalidate to each sharer {1,7,9}
- Modified (Owner=Core 4): HD sends Invalidate-Forward to Core 4
Sharers invalidate their copies, reply Invalidate-Ack to HD
HD waits for all acks, then replies to Core 3: Write-Ack(data)
HD updates: State=Modified, Owner=3

Why invalidate before granting write?

Sequential consistency: Core 3 cannot write until all old readers see invalidation—otherwise a stale reader could violate the coherence invariant (multiple caches with inconsistent values).

Worked example Worked example: 4-core read-then-write

Setup: Memory block X at address 0xA000, initially Uncached.

Step 1: Core 0 reads X

Core 0 → HD: Read-Req(0xA000)
HD: State=Uncached → reply Data(X=42) (fetched from memory), set State=Shared, Sharers={0}
Core 0 caches X=42 as Shared Step 2: Core 2 reads X
Core 2 → HD: Read-Req(0xA000)
HD: State=Shared, Sharers={0} → reply Data(X=42), Sharers={0,2}
Core 2 caches X=42 as Shared Step 3: Core 1 writes X=99
Core 1 → HD: Write-Req(0xA000)
HD: State=Shared, Sharers={0,2} → send Invalidate to Cores 0,2
Core 0 → HD: Inv-Ack (invalidates local copy)
Core 2 → HD: Inv-Ack (invalidates local copy)
HD → Core 1: Write-Ack(X=42) after receiving 2 acks
HD updates: State=Modified, Owner=1
Core 1 writes X=99, marks Modified Why the ack-counting? If HD replied before all acks, Core 0 might still have X=42 when Core 1 writes—violating coherence.

Directory organization trade-offs

Full-map directory

Formula Full-map storage cost

For $N$ cores, $M$ memory blocks: $\text{Directory size} = M \times \left(2 + N\right) \text{ bits}$

$2$ bits: State (Uncached/Shared/Modified)
$N$ bits: Sharer bit-vector (1 bit per core)

Why no separate owner field? In a full-map bit-vector, the owner in the Modified state is implicit—it is simply the single core whose bit is set. A dedicated $\log_2 N$ -bit owner ID would double-count information already present in the vector.

Example: 64 cores, 1 GB of cache-block memory (16 million 64B blocks): $\text{Dir size} = 16M \times (2 + 64) = 16M \times 66 \text{ bits} = 132 \text{ MB}$

Why so large? We're tracking sharing at cache-block granularity across all memory—directory scales with memory size × core count.

Optimization: Sparse directories use pointers (store only active sharers) or limited pointers (track up to $k$ sharers, evict extras). Reduces size at the cost of false invalidations.

Distributed vs. centralized

Distributed directory: Each memory "home" node (e.g., NUMA region) has a directory slice for its addresses
- Pro: Parallelism—no single bottleneck
- Con: Complex routing (multi-hop to find home)
- Used in: AMD EPYC (distributed across chiplets), SGI Origin
Centralized directory: One directory for all addresses
- Pro: Simple lookup
- Con: Hot-spot under high contention
- Used in: Smaller systems (<16 cores)

Comparison: Snooping vs. Directory

Aspect	Snooping (broadcast)	Directory (point-to-point)
Scalability	O(N²) traffic	O(N) traffic
Latency	Low (1 broadcast)	Moderate (2-3 hops: requester→dir→owner)
Complexity	Simple (no state tracking)	Complex (directory storage + protocols)
Best for	≤16 cores, shared bus	≥16 cores, multi-chip systems

Why the latency difference?

Snooping: Request goes directly to all caches in parallel.
Directory: Request must first reach home directory, then be forwarded—adds 1-2 network hops.

Performance implications

Invalidation overhead

Optimization: Coarse sharer tracking (track groups instead of individuals) reduces ack-counting but causes false invalidations.

Same as snooping: If Cores 0,1 access different words in the same cache line, directory sees them as accessing the same block—write by Core 0 invalidates Core 1's unrelated data.

Directory advantage: At least the invalidation is point-to-point (only Core 1 notified), not broadcast.

Connections

Cache coherence protocols (MESI, MOESI): Directory protocols implement these states, but with directory tracking instead of snooping
NUMA architectures: Directory distribution follows NUMA memory ownership—each node's directory manages its local memory's coherence
Interconnect topologies: Directory efficiency depends on network topology (mesh vs. ring vs. crossbar)—multi-hop paths increase latency
Memory consistency models: Directory ack-counting enforces sequential consistency—relaxed models can overlap invalidations
Cache line false sharing: Directory protocols suffer the same false-sharing penalties as snooping—mitigation requires software/compiler alignment

Recall Explain to a 12-year-old

Imagine you and 63 friends are working on a group project, and everyone has notebooks (caches). When someone wants to write something, they need to make sure nobody else has a conflicting copy.

Snooping method: You shout to all 63 friends every time—"Hey everyone, I'm erasing this page!" Everyone hears everything. Gets really noisy.

Directory method: You ask the class monitor (directory)—"Who has page 42?" Monitor says, "Alice and Bob." You send a note only to Alice and Bob—"Erase page 42." Once they confirm, monitor tells you, "Okay, you can write now." Note: the monitor only keeps a list of who has what—not copies of the pages themselves.

Why is this better? In a small class (8 friends), shouting is fine. In a huge auditorium (100 friends), shouting creates chaos—the monitor system keeps it organized.

#flashcards/hardware

What is the key scalability advantage of directory-based coherence over snooping? :: Directory protocols use point-to-point messages (O(N) traffic) instead of broadcast (O(N²) traffic), allowing them to scale to hundreds of cores without saturating the interconnect.

What information does a directory entry track for each memory block?

Only coherence metadata: the State (Uncached/Shared/Modified) and the Sharers/Owner (cache IDs holding the block). The directory does NOT store the data payload—that stays in memory (or the owning cache if Modified).

In a directory protocol, why must the home directory wait for all invalidation acknowledgments before granting a write? :: To enforce sequential consistency—if the writer proceeds before all sharers invalidate, a stale reader could see old data, violating the coherence invariant (at most one writer OR multiple readers).

What is the main latency disadvantage of directory protocols compared to snooping?

Directory protocols require 2-3 network hops (requester→directory→owner→requester) vs. snooping's single broadcast, adding 10-50ns of indirection latency in typical systems.

For a 64-core system with 16 million cache blocks, approximately how large is a full-map directory?

About 132 MB (16M blocks × 66 bits per entry: 2 state bits + 64 sharer bits; the owner is implicit in the bit-vector, so no separate owner field is needed).

Why do distributed directories interleave memory addresses across NUMA nodes?

To spread directory lookup traffic evenly—the socket-select bits sit just above the block-offset bits, so consecutive blocks map to different home nodes, preventing any single directory from becoming a hot-spot.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab hamare paas 64 ya usse zyada cores hote hain ek system mein, toh cache coherence maintain karna bada challenge ban jaata hai. Purana tareeka jaise snooping protocol mein, jab bhi kisi core ko cache miss hota hai, woh apna message baaki sabhi cores ko broadcast karta hai — matlab ek group chat jaisa jahan har koi har message dekhta hai. Problem yeh hai ki yeh O(N²) traffic paida karta hai, aur itne saare messages se interconnect saturate ho jaata hai. Isiliye directory-based protocol aaya. Ismein ek central directory hoti hai jo track karti hai ki kaunse cache ke paas kaunsa memory block hai aur kis state mein hai. Toh ab broadcast ki jagah sirf relevant cores ko point-to-point message jaata hai — bilkul direct message jaisa, sirf involved logon ko hi pata chalta hai.

Ab ek important baat samajhna: yeh directory sirf metadata store karti hai — matlab state (Uncached, Shared, ya Modified) aur sharers ki list — actual data nahi. Data toh main memory mein hi rehta hai, ya agar koi cache usko Modified state mein hold kar raha hai toh us cache mein. Jab koi core read miss karta hai, toh woh home directory se poochta hai, aur directory dekh ke decide karti hai — agar Uncached hai toh memory se data de deti hai, agar Shared hai toh sharer list mein naam add karke data bhej deti hai, aur agar Modified hai toh us owner core ko forward kar deti hai jiske paas latest dirty copy hai. Isi tarah write miss mein, pehle saare purane sharers ko Invalidate message jaata hai, unke acknowledgement ka wait hota hai, phir jaake write allow hoti hai.

Yeh baat isliye matter karti hai kyunki aaj ke real-world multi-chip systems jaise AMD EPYC ya AWS Graviton mein koi single shared bus hi nahi hoti, toh snooping kaam hi nahi kar sakta. Directory-based approach O(N) bandwidth pe kaam karti hai kyunki har request sirf ek directory aur thode se sharers tak jaati hai, na ki saare N cores tak. Aur yeh invalidate-before-write wala rule sequential consistency ensure karta hai — matlab jab tak saare purane readers ko pata na chal jaaye ki data invalid ho gaya, tab tak naya writer likh nahi sakta, warna koi core stale purana data padh leta. Isiliye bade scale pe correct aur efficient coherence ke liye directory-based protocol foundation hai.

What is a directory-based protocol?

How directory protocols work

The directory structure

Message flow: Read miss

Message flow: Write miss

Directory organization trade-offs

Full-map directory

Distributed vs. centralized

Comparison: Snooping vs. Directory

Performance implications

Invalidation overhead

Connections

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Parallelism & Multicore

Connections