Cache coherence at scale (directory-based) — Hinglish notes

6.1.6 · Hardware › Parallelism & Multicore

Directory-based protocol kya hota hai?

Yeh design kyun?

Broadcast = O(N²) bandwidth: N cores mein se har ek traffic generate karta hai, aur har message N-1 cores ko jaata hai.
Directory = O(N) bandwidth: Har request 1 directory + sharers (typically 1-3 caches) ko jaata hai.
Physical constraint: Modern multi-chip systems (e.g., AMD EPYC, AWS Graviton) mein koi shared bus nahi hoti—directories alag chips ke beech coherence enable karti hain.

Figure — Cache coherence at scale (directory-based)

Directory protocols kaise kaam karte hain

Directory structure

Formula Directory entry format

Address $A$ par har memory block $B$ ke liye: $Directory [A] = ⟨ State, Owner/Sharers ⟩$ Note: Directory sirf metadata hold karti hai—actual block data main memory mein rehta hai (ya owning cache mein agar Modified ho). Directory kabhi bhi data payload duplicate nahi karti.

State ∈ {Uncached, Shared, Modified}:

Uncached: Koi bhi cache $B$ hold nahi karta (memory mein data valid hai)
Shared: ≥1 caches ke paas read-only copies hain (memory mein data valid hai)
Modified: Exactly 1 cache ke paas exclusive dirty copy hai (memory stale hai)

Owner/Sharers:

Modified → Owner = woh single cache jo dirty block hold karta hai (full-map vector mein, yeh woh ek set bit hai)
Shared → Sharers = bit-vector ya pointer list of cache IDs Sharers ko exactly kyun track karein? Write par, hume sab shared copies invalidate karni padti hain. List ke bina, hume broadcast karna padta (scalability khatam ho jaati).

Message flow: Read miss

Scenario: Core 2 address 0x1000 read karta hai, jo uski cache mein nahi hai.

Core 2 → Home directory (HD): Read-Request(0x1000)
HD state check karta hai:
- Uncached: HD memory se data ke saath reply karta hai, State=Shared set karta hai, Sharers={2}
- Shared: HD Core 2 ko Sharers mein add karta hai, data ke saath reply karta hai
- Modified (Owner=Core 5): HD request Core 5 ko forward karta hai
Agar Modified: Core 5 → Core 2: Data-Reply(0x1000, data) + Core 5 → HD: Data-WriteBack(data) (HD memory update karta hai, State=Shared, Sharers={2,5})
Core 2 block ko cache mein Shared ke roop mein install karta hai

Yeh path kyun?

Sirf Core 2, HD, aur (agar zaroorat ho) owner ko messages milte hain—koi broadcast nahi.
Write-back on sharing: Modified owner ko data supply karna padta hai kyunki memory stale hai (directory ne khud kabhi data hold nahi kiya—usay sirf pata tha ki Core 5 owner tha).

Message flow: Write miss

Scenario: Core 3 0x2000 par write karta hai, current State=Shared, Sharers={1,7,9}.

Core 3 → HD: Write-Request(0x2000)
HD state check karta hai:
- Shared: HD har sharer {1,7,9} ko Invalidate bhejta hai
- Modified (Owner=Core 4): HD Core 4 ko Invalidate-Forward bhejta hai
Sharers apni copies invalidate karte hain, HD ko Invalidate-Ack reply karte hain
HD sab acks ka wait karta hai, phir Core 3 ko reply karta hai: Write-Ack(data)
HD update karta hai: State=Modified, Owner=3

Write se pehle invalidate kyun?

Sequential consistency: Core 3 tab tak write nahi kar sakta jab tak sab purane readers invalidation na dekh lein—warna ek stale reader coherence invariant violate kar sakta hai (multiple caches mein inconsistent values).

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

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

Step 1: Core 0 X read karta hai

Core 0 → HD: Read-Req(0xA000)
HD: State=Uncached → Data(X=42) reply karta hai (memory se fetch kiya), State=Shared set karta hai, Sharers={0}
Core 0 X=42 ko Shared ke roop mein cache karta hai Step 2: Core 2 X read karta hai
Core 2 → HD: Read-Req(0xA000)
HD: State=Shared, Sharers={0} → Data(X=42) reply karta hai, Sharers={0,2}
Core 2 X=42 ko Shared ke roop mein cache karta hai Step 3: Core 1 X=99 write karta hai
Core 1 → HD: Write-Req(0xA000)
HD: State=Shared, Sharers={0,2} → Cores 0,2 ko Invalidate bhejta hai
Core 0 → HD: Inv-Ack (local copy invalidate karta hai)
Core 2 → HD: Inv-Ack (local copy invalidate karta hai)
HD → Core 1: Write-Ack(X=42) 2 acks receive karne ke baad
HD update karta hai: State=Modified, Owner=1
Core 1 X=99 likhta hai, Modified mark karta hai Ack-counting kyun? Agar HD sab acks se pehle reply karta, toh Core 0 ke paas abhi bhi X=42 ho sakta tha jab Core 1 likhta—coherence violate ho jaati.

Directory organization trade-offs

Full-map directory

Optimization: Sparse directories pointers use karte hain (sirf active sharers store karo) ya limited pointers (up to $k$ sharers track karo, extras evict karo). False invalidations ki cost par size kam karta hai.

Distributed vs. centralized

Distributed directory: Har memory "home" node (e.g., NUMA region) ke paas apne addresses ke liye ek directory slice hoti hai
- Pro: Parallelism—koi single bottleneck nahi
- Con: Complex routing (home dhundhne ke liye multi-hop)
- Used in: AMD EPYC (chiplets mein distributed), SGI Origin
Centralized directory: Sab addresses ke liye ek directory
- Pro: Simple lookup
- Con: High contention par hot-spot ban jaata hai
- Used in: Chhote 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 (koi state tracking nahi)	Complex (directory storage + protocols)
Best for	≤16 cores, shared bus	≥16 cores, multi-chip systems

Latency difference kyun?

Snooping: Request seedha sab caches ko parallel mein jaata hai.
Directory: Request pehle home directory tak pahunchna chahiye, phir forward hona chahiye—1-2 network hops add hote hain.

Performance implications

Invalidation overhead

Optimization: Coarse sharer tracking (individuals ki jagah groups track karo) ack-counting kam karta hai lekin false invalidations cause karta hai.

Snooping ki tarah hi: Agar Cores 0,1 ek hi cache line mein alag words access karte hain, toh directory unhe ek hi block access karte hua dekhti hai—Core 0 ka write Core 1 ke unrelated data ko invalidate kar deta hai.

Directory advantage: Kam se kam invalidation point-to-point hai (sirf Core 1 notify hota hai), na ki broadcast.

Connections

Cache coherence protocols (MESI, MOESI): Directory protocols yeh states implement karte hain, lekin snooping ki jagah directory tracking ke saath
NUMA architectures: Directory distribution NUMA memory ownership follow karta hai—har node ki directory apni local memory ki coherence manage karti hai
Interconnect topologies: Directory efficiency network topology par depend karti hai (mesh vs. ring vs. crossbar)—multi-hop paths latency badhate hain
Memory consistency models: Directory ack-counting sequential consistency enforce karta hai—relaxed models invalidations overlap kar sakte hain
Cache line false sharing: Directory protocols ko snooping jaisi hi false-sharing penalties hoti hain—mitigation ke liye software/compiler alignment chahiye

Recall Ek 12-saal ke bacche ko explain karo

Socho tum aur 63 dost ek group project par kaam kar rahe ho, aur sabke paas notebooks hain (caches). Jab koi kuch likhna chahta hai, use ensure karna padta hai ki kisi aur ke paas conflicting copy nahi hai.

Snooping method: Tum har baar sab 63 doston ko chillate ho—"Hey sab, main yeh page erase kar raha hoon!" Sab sab kuch sunte hain. Bahut shor ho jaata hai.

Directory method: Tum class monitor (directory) se poochte ho—"Page 42 kiske paas hai?" Monitor kehta hai, "Alice aur Bob ke paas." Tum sirf Alice aur Bob ko note bhejte ho—"Page 42 erase karo." Jab woh confirm kar dein, monitor tumhe bolta hai, "Theek hai, ab tum likh sakte ho." Note: monitor sirf ek list rakhta hai ki kiske paas kya hai—pages ki copies nahi.

Yeh better kyun hai? Ek chhoti class (8 dost) mein, chillana theek hai. Ek bade auditorium (100 dost) mein, chillana chaos create karta hai—monitor system isko organized rakhta hai.

#flashcards/hardware

Directory-based coherence ka snooping par key scalability advantage kya hai? :: Directory protocols point-to-point messages (O(N) traffic) use karte hain broadcast (O(N²) traffic) ki jagah, jo unhe interconnect saturate kiye bina hundreds of cores tak scale karne deta hai.

Ek directory entry har memory block ke liye kya information track karta hai?

Sirf coherence metadata: State (Uncached/Shared/Modified) aur Sharers/Owner (cache IDs jo block hold karte hain). Directory data payload store nahi karta—woh memory mein rehta hai (ya owning cache mein agar Modified ho).

Directory protocol mein, home directory ko write grant karne se pehle sab invalidation acknowledgments ka wait kyun karna padta hai? :: Sequential consistency enforce karne ke liye—agar writer sab sharers ke invalidate karne se pehle proceed kare, toh ek stale reader purana data dekh sakta hai, coherence invariant violate ho jaati hai (zyada se zyada ek writer YA multiple readers).

Snooping ki tulna mein directory protocols ka main latency disadvantage kya hai?

Directory protocols mein 2-3 network hops chahiye (requester→directory→owner→requester) vs. snooping ke single broadcast, typical systems mein 10-50ns indirection latency add hoti hai.

64-core system mein 16 million cache blocks ke saath, ek full-map directory approximately kitna bada hota hai?

Lagbhag 132 MB (16M blocks × 66 bits per entry: 2 state bits + 64 sharer bits; owner bit-vector mein implicit hai, isliye koi alag owner field nahi chahiye).

Distributed directories memory addresses ko NUMA nodes mein interleave kyun karte hain?

Directory lookup traffic evenly spread karne ke liye—socket-select bits block-offset bits ke thoda upar baithe hain, isliye consecutive blocks alag home nodes par map hote hain, kisi bhi single directory ko hot-spot banne se rokta hai.