Cache coherence at scale (directory-based): Worked examples

6.1.6 · D3 · Hardware › Parallelism & Multicore › Cache coherence at scale (directory-based)

Yeh page drill floor hai. Parent note ne tumhe bataya tha ki directory protocols kaise kaam karte hain; yahan hum machine ko har us situation se guzarte hain jo use mil sakti hai — har starting state, har degenerate corner, ek real word problem, aur ek exam trap — aur har ek ka arithmetic check karte hain.

Koi example touch karne se pehle, ek promise: hum koi bhi aisa symbol use nahi karenge jo tumne pehle nahi dekha. Aao hum teen cheezein phir se samjhein jo baar baar aati hain.

Scenario matrix

Har woh case jo ek directory protocol face kar sakta hai, woh (starting state) × (operation) ka combination hota hai, saath mein degenerate aur real-world corners. Yeh pura grid hai; har cell us example ka naam batati hai jo use cover karta hai.

#	Starting state	Operation	Degenerate / twist	Covered by
1	Uncached	Read	pehli baar touch (base case)	Ex 1
2	Shared	Read	ek sharer add karo, koi data movement nahi	Ex 2
3	Modified (other owner)	Read	owner ko write back karna hoga	Ex 3
4	Shared (many sharers)	Write	sab invalidate + ack-count	Ex 4
5	Modified (other owner)	Write	invalidate-forward, ownership transfer	Ex 5
6	Shared, tum already hold kar rahe ho	Write (upgrade)	zero data transfer, self invalidate nahi	Ex 6
7	koi bhi	—	storage cost limiting cases ( $N = 1$ , bada $M$ )	Ex 7
8	koi bhi	—	NUMA home routing address bits se (word problem)	Ex 8
9	Shared	Write	exam twist: race — do writers ek saath	Ex 9

Nau cells, nau examples. "Forecast:" line padho aur steps unfold karne se pehle guess karo.

Worked examples

Worked example Ex 1 — Cell 1: Uncached + Read (base case)

Statement. Block X at 0xA000 Uncached hai, memory mein X=42 hai. Core 0 read issue karta hai. Forecast: Data kahan se aayega, aur ending state kya hogi?

Core 0 → HD: Read-Req(0xA000). Yeh step kyun? Read miss hamesha pehle home directory ko jaati hai — requester ko pata nahi koi block hold kar raha hai ya nahi; HD ek single source of truth hai.
HD apni state padhta hai = Uncached. Koi cache X hold nahi kar raha, toh memory authoritative hai. HD X=42 memory se fetch karta hai aur Data-Reply(X=42) bhejta hai. Yeh step kyun? Uncached mein kisi ko forward karna nahi hai; HD seedha data serve karta hai.
HD update karta hai: State → Shared, Sharers = {0} (sirf bit 0 on). Yeh step kyun? Core 0 ab read-only copy rakhta hai aur memory abhi bhi valid hai — yahi Shared ki definition hai.

Verify: Ending state Shared, sharers = {0}, value deliver hui = 42, memory unchanged = 42. Ek copy bahar, koi write nahi, toh memory 42 hi rehni chahiye. ✔

Worked example Ex 3 — Cell 3: Modified (other owner) + Read (owner writes back)

Statement. Block Y at 0xB000. State=Modified, Owner=Core 5, aur Core 5 ki cached value Y=77 hai jabki memory stale hai (holds Y=10). Core 2 reads Y. Forecast: Data kaun supply karta hai — memory ya core 5? Memory ke baad kya hoga?

Core 2 → HD: Read-Req(0xB000).
HD Modified dekhta hai, Owner=5. Memory (10) galat hai; sirf Core 5 ke paas sach hai (77). HD request Core 5 ko forward karta hai. Yeh step kyun? Directory kabhi data store nahi karti — use sirf pata tha Core 5 owner hai. Toh owner, HD nahi, fresh bytes supply karega.
Core 5 → Core 2: Data-Reply(Y=77), aur Core 5 → HD: Write-Back(Y=77). Yeh step kyun? Core 2 ko abhi current value chahiye; write-back memory bhi repair karta hai taaki future Uncached reads sahi hon.
HD update karta hai: memory = 77, State → Shared, Sharers = {2, 5}. Yeh step kyun? Do caches ab read-only copies rakhte hain aur memory finally match karti hai — yahi Shared hai.

Verify: Data deliver hua = 77 (owner se aaya, stale 10 se nahi); memory repaired 10 \to 77; sharers = {2,5}, count 2; state Modified → Shared. Stale memory value 10 kabhi deliver nahi hui. ✔

Worked example Ex 4 — Cell 4: Shared (many) + Write (sab invalidate, ack-count)

Statement. Block Z at 0xC000. State=Shared, Sharers={1,7,9}, Z=5. Core 3 writes Z=88. Forecast: Write grant karne se pehle HD ko kitne Inv-Ack messages ka wait karna hoga?

Core 3 → HD: Write-Req(0xC000).
HD Shared dekhta hai, Sharers={1,7,9}. Woh har sharer ko Invalidate bhejta hai: cores 1, 7, 9 — teen messages, point-to-point (broadcast nahi). Yeh step kyun? Write ke baad exactly ek valid copy rehni chahiye. Jaise hi Core 3 write karega, har existing read-only copy stale ho jayegi, toh sab pehle destroy hone chahiye.
Cores 1, 7, 9 apni copies drop karte hain aur har ek Inv-Ack reply karta hai. HD 3 acks count karta hai. Yeh step kyun? Agar HD sirf 2 acks ke baad write grant kar deta, toh teesra core abhi bhi purana Z=5 kisi ko serve kar sakta — do alag live values = coherence violation.
HD → Core 3: Write-Ack. HD update karta hai: State → Modified, Owner={3}.
Core 3 writes Z=88, apni line Modified mark karta hai. Memory ab stale (abhi bhi 5).

Verify: Invalidates sent = 3; acks awaited = 3 (sharers ki sankhya ke barabar honi chahiye); ending sharer count = 1 (sirf Core 3); state Shared → Modified; memory = 5 (stale, sahi behaviour — abhi write-back nahi). ✔

Worked example Ex 5 — Cell 5: Modified (other owner) + Write (invalidate-forward)

Statement. Block W at 0xD000. State=Modified, Owner=Core 4, Core 4 holds W=200, memory stale. Core 6 writes W=1. Forecast: End mein kitne caches valid copy rakhenge? Kaun?

Core 6 → HD: Write-Req(0xD000).
HD Modified dekhta hai, Owner=4. Woh Core 4 ko Invalidate-Forward bhejta hai. Yeh step kyun? Sirf Core 4 ke paas ek copy hai (modified). Hume uska latest data lena bhi hai aur uski copy bhi khatam karni hai, kyunki Core 6 sole owner banne wala hai.
Core 4 apni line invalidate karta hai aur current data (W=200) transaction mein forward karta hai, phir HD ko ack karta hai. Yeh step kyun? Core 6 value overwrite karega, lekin protocol phir bhi block transfer karta hai taaki Core 6 ki cache line store se pehle populate ho jaye.
HD → Core 6: Write-Ack. HD update karta hai: State Modified hi rehta hai, Owner={6}.
Core 6 writes W=1.

Verify: End mein exactly 1 valid copy, Core 6 ke paas; previous owner count 1 \to 0; state Modified → Modified (owner 4 → 6 badla); final cached value = 1. ✔

Worked example Ex 6 — Cell 6: Shared + Write by a current sharer (upgrade, degenerate)

Statement. Block V at 0xE000. State=Shared, Sharers={2,5,8}, V=30. Core 5 — already ek sharer — writes V=31. Forecast: Kya Core 5 invalidate hoga? Kya data Core 5 ko move karna padega?

Core 5 → HD: Write-Req(0xE000) (ek upgrade: Core 5 ke paas read-only data pehle se hai).
HD Shared dekhta hai, Sharers={2,5,8}. Woh sirf doosre sharers invalidate karta hai: cores 2 aur 8. Core 5 invalidate nahi hota — woh apni copy upgrade ke liye rakhta hai. Yeh step kyun? Core 5 ke paas already valid bytes hain; unhe destroy karke dobara bhejna waste hoga. Sirf doosri copies coherence ke liye threat hain.
Cores 2, 8 Inv-Ack bhejte hain; HD 2 acks count karta hai (3 nahi — writer khud ko invalidate nahi karta).
HD → Core 5: Write-Ack bina data payload ke (Core 5 ke paas already V=30 tha). State → Modified, Owner={5}.
Core 5 writes V=31.

Verify: Invalidates sent = 2 (sharers minus writer, $3 - 1 = 2$ ); data bytes writer ko transfer hue = 0; ending owner = {5}; final value = 31. Yeh degenerate "tum already photocopy rakhte ho" case hai. ✔

Worked example Ex 7 — Cell 7: Full-map storage cost, limiting inputs

Statement. Yaad karo $Directory size = M \times (2 + N)$ bits, jahan $M$ = memory blocks ki sankhya, $N$ = cores ki sankhya. Teen points compute karo: (a) $N = 1$ , $M = 1$ ; (b) $N = 64$ , $M = 16, 000, 000$ ; (c) limit jab $N \to \infty$ . Forecast: (a) mein, kya directory block se choti hai ya badi? (c) mein, size $N$ ke saath badhti hai ya $N^{2}$ ke saath?

(a) Ek core, ek block: size $= 1 \times (2 + 1) = 3$ bits. Yeh step kyun? Yeh sabse chhotа degenerate directory hai. 64-byte block $512$ bits ka hota hai, toh directory metadata ( $3$ bits) data ke saamne ek rounding error hai — is scale par overhead negligible hai.
(b) Parent ka headline case: $16, 000, 000 \times (2 + 64) = 16, 000, 000 \times 66 = 1, 056, 000, 000$ bits $= 132$ MB. Yeh step kyun? Yeh dikhata hai kyun full-map "itna bada" hai — $+ N$ bit-vector per block dominate karta hai jab $N$ aur $M$ bade hon.
(c) Limit $N \to \infty$ : size $\approx M \cdot N$ bits — linear $N$ mein, kyunki constant $2$ negligible ho jaata hai. Yeh $N^{2}$ nahi hai. Yeh step kyun? Yahi directories vs. snooping ka pura point hai: storage $N$ ki tarah badhta hai, aur traffic $N$ ki tarah badhta hai, kabhi $N^{2}$ nahi.

Verify: (a) $= 3$ bits; (b) $= 1, 056, 000, 000$ bits, aur $1, 056, 000, 000/8/1, 048, 576 = 125.9 \dots$ MB (≈132 MB parent ke $16 M \times 66$ rounding se); (c) leading term linear in $N$ . ✔

Worked example Ex 8 — Cell 8: NUMA home routing (real-world word problem)

Statement. Ek 4-socket server memory ko 256-byte chunks mein interleave karta hai. Ek address aise split hota hai: [ tag | socket-select (2 bits) | 256B offset (8 bits) ]. 0x7F00 ka home kaun sa socket hai? 0x7E00 ka? Forecast: Kya 0x100 apart do addresses ek hi socket par land karte hain ya alag sockets par?

Offset bits dhundo. $256 = 2^{8}$ , toh low 8 bits ek block ke andar byte offset hain. Yeh socket select nahi karte. Yeh step kyun? Interleaving ko ensure karna chahiye ki ek block ke saare 256 bytes ek socket par hon (locality), isliye offset field socket-select field ke neeche hota hai.
0x7F00 binary mein: $0x7F00 = 0111111100000000$ . Low 8 bits (0000 0000) hata do, agle 2 bits (bits 8–9) 11 = 3 hain. → Socket 3.
0x7E00 = $0111111000000000$ . Low 8 bits 0000 0000; bits 8–9 10 = 2 hain. → Socket 2. Yeh step kyun? 0x7F00 aur 0x7E00 mein fark 0x100 = 256 = exactly ek block hai, toh yeh consecutive blocks hain aur sahi tarah se alag sockets par land karte hain — directory load spread karte hain.

Verify: 0x7F00 >> 8 = 0x7F = 127; $127 mod 4 = 3$ → Socket 3. 0x7E00 >> 8 = 0x7E = 126; $126 mod 4 = 2$ → Socket 2. Consecutive blocks, alag sockets. ✔

Worked example Ex 9 — Cell 9: Exam twist — do writers Shared block par race karte hain

Statement. Block Q at 0xF000. State=Shared, Sharers={0,1}. Core 0 aur Core 1 dono "simultaneously" Write-Req issue karte hain. HD coherence kaise maintain karta hai, aur final owner kaun hoga? Forecast: Kya dono writes grant ho sakti hain? Kaun jeetega?

Dono requests HD tak pahunchti hain. HD ek single point of serialization hai — woh ek diye gaye address ke liye ek waqt mein ek Write-Req process karta hai, toh dono requests ordered ho jaati hain (maan lo Core 0 pehle, Core 1 doosre). Yeh step kyun? Coherence ke liye ek location par writes ka total order chahiye; home directory single arbiter banke yeh provide karta hai.
Core 0 ki request pehle handle hoti hai: HD doosre sharer, Core 1, ko invalidate karta hai, uska Inv-Ack wait karta hai, Core 0 ko write grant karta hai. State → Modified, Owner={0}. Yeh step kyun? Upgrade case (Ex 6) jaisa hi — winner ke alaawa sab invalidate karo, acks count karo, phir grant karo.
Core 1 ki request doosre handle hoti hai: block ab Modified/Owner=0 hai. Yeh Modified + Write ban jaata hai (Ex 5!): HD Core 0 ko Invalidate-Forward bhejta hai, ownership transfer karta hai. State Modified hi rehta hai, Owner={1}. Yeh step kyun? Core 1 ki write queue mein thi; doosre number ka writer pehle waale se ownership chheenna chahta hai, exactly Cell 5 ki tarah.
Final state: Modified, Owner={1} (woh request jise HD ne last order kiya).

Verify: Ek saath granted writers ki sankhya = 1 (kabhi 2 nahi); Core 0 ki request ke liye acks awaited = 1 (sirf doosra sharer, Core 1); final owner = {1} (last serialized); ending sharer count = 1. HD par serialization do simultaneous owners ko rokta hai. ✔

Recall Quick self-test

Ex 3: Modified block par read ke time, data kaun supply karta hai — memory ya owner? ::: Owner (memory stale hoti hai write-back tak). Ex 4: HD ke paas 3 sharers ke saath Shared hai; ek write aati hai — use kitne Inv-Ack collect karne hain? ::: Saare 3, write grant karne se pehle. Ex 6: ek current sharer write ke liye upgrade karta hai — usse kitne bytes of data move hote hain? ::: Zero; uske paas already valid copy hai, toh sirf ack (koi payload nahi). Ex 7: full-map directory storage $N$ ki tarah badhti hai ya $N^{2}$ ki tarah? ::: Linear in $N$ (woh $+ N$ bit-vector), kabhi $N^{2}$ nahi. Ex 8: interleaving mein consecutive 256B blocks same socket ya alag sockets par land karte hain? ::: Alag sockets par, by design, load spread karne ke liye. Ex 9: do simultaneous writers ko dono block own karne se kaun rokta hai? ::: Home directory ek address ke liye requests serialize karta hai — ek arbiter, ek order.

See also: Cache coherence protocols (MESI, MOESI) · NUMA architectures · Interconnect topologies · Memory consistency models · Cache line false sharing · back to the parent topic.