Cache coherence at scale (directory-based): Exercises

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

Neeche use hone wala har term parent note mein build kiya gaya hai. Ye prerequisites open rakhna helpful ho sakta hai: Cache coherence protocols (MESI, MOESI) · NUMA architectures · Interconnect topologies · Memory consistency models · Cache line false sharing.

Definition Do coherence invariants ("valid" vs "stale")

Neeche sab kuch ek rule par tika hai — coherence invariant: har block ke liye, har instant mein, saare cached copies aur definitive copy ek single value par agree karte hain. Isse hume do phrases milte hain jo bar bar use hote hain:

Memory valid = main memory abhi the correct value hold kar rahi hai, toh koi reader seedha memory se data le sakta hai. Formally: koi cache memory se newer value nahi rakha. Uncached aur Shared mein yahi hota hai.
Memory stale = kisi cache ke paas memory se newer (dirty) value hai, toh memory definitive copy nahi hai — reader ko owning cache se serve karna hoga. Modified mein yahi hota hai. Stale memory ko write-back se theek kiya jaata hai. "Valid/stale" isliye batata hai ki definitive copy kahan hai: memory mein (valid) ya kisi cache mein (stale).

Definition Is page par notation aur states

HD = Home Directory: directory slice jo kisi given memory address ka malik hai. Yeh us block ki coherence ke liye single point of contact hai. Hum "Core 6 → HD" likhte hain matlab "core 6 us block ke home directory ko ek message bhejta hai".
Directory entry = $⟨ State, Sharers ⟩$ . Sharers field hamesha ek set hota hai (ek bit-vector). Hum koi alag owner field store nahi karte: Modified state mein set ek singleton hota hai, aur woh ek member hi owner hota hai. Toh " $⟨ Modified, {5}⟩$ " aur "owner = core 5" ek hi baat hai. Jab solutions "owner 5" kehte hain toh yeh Modified sharers set ke sole element ka shorthand hai.
Is page par States: Uncached (koi cache nahi rakhta, memory valid), Shared (≥1 read-only copies, memory valid), Modified (exactly 1 dirty copy, memory stale). Ek exercise (2.5) Exclusive bhi introduce karta hai — MESI ka ek clean single-owner state.

Recall Linked prerequisites ke liye one-paragraph refreshers (agar koi naam naya lage toh open karo)

MESI/MOESI ::: Per-cache-line state machines. Modified = dirty, sole owner, memory stale. Exclusive = clean, sole owner, memory valid — holder silently write kar sakta hai. Shared = clean, possibly many read-only copies. Invalid = present nahi. MOESI mein Owner add hota hai: ek dirty block shared for reading jabki ek cache write-back ke liye responsible rehti hai. NUMA ::: Non-Uniform Memory Access: memory sockets/nodes mein split hoti hai; ek core apna local node fast reach karta hai aur remote nodes slower. Addresses interleave hote hain toh consecutive blocks alag nodes par map hote hain (block ka "home"). Interconnect topologies ::: Cores/directories ke beech wiring — ring, mesh, crossbar. Determine karta hai kitne hops ek message leta hai; directory latency = home tak hops + owner tak hops. Memory consistency models ::: Rules ke liye ki ek core ke memory operations doosron ko across different addresses kab visible hote hain. Coherence se alag hai, jo per-address hoti hai. Cache line false sharing ::: Jab do independent variables ek cache line share karte hain, coherence unhe ek block maanta hai — writes ownership ping-pong karti hain bhaley hi koi real data shared na ho.

L1 — Recognition

(Kya aap machinery padh ke uske parts naam de sakte ho?)

Exercise 1.1 — Directory entry padhna

Ek directory entry $⟨ State, Sharers ⟩$ likhI jaati hai. Given entry: $Directory [0x1000] = ⟨ Shared, {1, 4, 7}⟩$ jawab do: (a) Abhi kitne caches yeh block hold karte hain? (b) Kya main memory ki copy valid hai? (c) Kya inn mein se koi cache home directory (HD) se contact kiye bina block write kar sakta hai?

Recall Solution

(a) Sharers set ${1, 4, 7}$ three caches list karta hai (cores 1, 4, 7). (b) Shared state mein saari copies read-only hain, toh invariant ke hisaab se memory valid hai (woh definitive value hold karta hai). (c) Nahi. Writing ke liye Modified mein transition karna padega, jo doosre sharers ko invalidate karna zaroori banata hai — woh zaroor home directory (HD) ke through jaana chahiye. Silent write karne se core 4 aur 7 mein stale copies reh jaayengi.

Exercise 1.2 — States classify karna

Har event ko resulting directory State se match karo (Uncached / Shared / Modified): (a) Kahin bhi koi cache block nahi rakhta. (b) Core 5 ke paas dirty, exclusive copy hai; memory stale hai. (c) Cores 2 aur 8 ke paas identical read-only copies hain.

Recall Solution

(a) Uncached — koi cache nahi karta, memory sole valid copy hai. Entry $⟨ Uncached, {}⟩$ . (b) Modified — sharers set ek singleton ${5}$ hai, toh core 5 hi owner hai; memory stale (core 5 ki copy definitive hai). Entry $⟨ Modified, {5}⟩$ . (c) Shared — multiple read-only copies, memory valid. Entry $⟨ Shared, {2, 8}⟩$ .

Exercise 1.3 — Metadata vs. data

Sach ya jhooth, ek sentence reason ke saath: "Directory har block ke data ki ek copy store karta hai taaki woh read misses ka jawab memory touch kiye bina de sake."

Recall Solution

Jhooth. Directory sirf metadata hold karta hai — state + sharers set. Read miss par Uncached/Shared state mein (memory valid), data main memory se aata hai; Modified state mein (memory stale) woh owning cache se aata hai (singleton sharer). Directory payload kabhi duplicate nahi karta.

Neeche message-flow figures dikhate hain exactly kaun se packets wire cross karte hain; trace check karte waqt inhe refer karo.

Figure — Cache coherence at scale (directory-based)

L2 — Application

(Kya aap protocol ko haath se chala sakte ho?)

Exercise 2.1 — Uncached par Read miss

Block $Y$ at 0xB000 Uncached hai, memory mein $Y = 7$ hai. Core 6 read issue karta hai. Messages order mein list karo aur final directory entry do.

Recall Solution

Core 6 → HD (home directory): Read-Req(0xB000) — message 1.
HD Uncached dekhta hai (memory valid) → memory se fetch karta hai, core 6 ko Data(Y=7) reply karta hai — message 2.
HD update karta hai: $⟨ Shared, {6}⟩$ .
Core 6 $Y = 7$ Shared ki tarah install karta hai. Final entry: $⟨ Shared, {6}⟩$ . Message count = 2 (Read-Req + Data reply). Read par koi ack exist nahi karta, toh end-to-end genuinely 2 hai.

Exercise 2.2 — Modified par Read miss (owner forward)

Block $Z$ at 0xC000 Modified hai, sharers ${3}$ (matlab core 3 owner hai), dirty value $Z = 88$ (memory ab bhi $Z = 10$ kehta hai). Core 9 read issue karta hai. Messages list karo aur final entry do.

Recall Solution

Core 9 → HD: Read-Req(0xC000) — message 1.
HD Modified dekhta hai (memory stale), sole sharer = core 3 → core 3 ko request forward karta hai — message 2.
Core 3 → Core 9: Data-Reply(Z=88) — message 3.
Core 3 → HD: Data-WriteBack(Z=88) (memory ab 88 ho jaati hai, valid ho jaati hai) — message 4.
HD update karta hai: $⟨ Shared, {3, 9}⟩$ . Final entry: $⟨ Shared, {3, 9}⟩$ ; memory $Z = 88$ . Purana owner sharer rehta hai — woh invalidate nahi hua, read-only mein downgrade ho gaya. Message count = 4 (Read-Req + Forward + Data-Reply + Write-Back — hamare ground rule ke mutabik har crossing count ki gayi).

Exercise 2.3 — Uncached block par Write miss (Uncached → Modified)

Block $V$ at 0xE000 Uncached hai, memory $V = 5$ . Core 2 write $V = 77$ issue karta hai. Messages list karo aur final entry do. Yeh Shared-case write se kaise different hai?

Recall Solution

Core 2 → HD: Write-Req(0xE000) — message 1.
HD Uncached dekhta hai → koi sharers exist nahi, toh invalidate karne ke liye kuch nahi aur koi acks wait karne ke liye nahi. HD Write-Ack(V=5) reply karta hai (core 2 ko current value memory se deta hai taaki woh merge/overwrite kar sake) — message 2.
HD update karta hai: $⟨ Modified, {2}⟩$ (core 2 ab sole owner hai; memory stale ho jaati hai jab core 2 write karta hai).
Core 2 $V = 77$ store karta hai, line Modified mark karta hai; memory 5 par stale rehti hai write-back tak. Final entry: $⟨ Modified, {2}⟩$ . Message count = 2 (Write-Req + Write-Ack). Shared write se difference: Uncached→Modified path poora invalidate-and-count-acks phase skip kar deta hai kyunki sharers set empty hai. Yeh cheapest write path hai — ownership turant grant karo.

Exercise 2.4 — Shared par Write miss (invalidation)

Block $W$ at 0xD000 Shared hai, sharers ${0, 2, 5, 8}$ . Core 5 (already ek sharer!) write karna chahta hai. Messages list karo aur count karo ki HD ko kitne invalidation acks collect karne honge.

Recall Solution

Core 5 ek sharer hai lekin sirf read-only copy rakhta hai, toh phir bhi upgrade chahiye (Shared → Modified).

Core 5 → HD: Write-Req(0xD000) (ek upgrade request).
HD doosre sharers ko Invalidate bhejta hai: cores 0, 2, 8 (core 5 ko nahi — woh naya owner banega).
Cores 0, 2, 8 har ek → HD: Inv-Ack. HD 3 acks collect karta hai.
Saare 3 acks ke baad, HD → Core 5: Write-Ack, phir $⟨ Modified, {5}⟩$ update karta hai. Final entry: $⟨ Modified, {5}⟩$ . Acks collected = 3. (Full message count end-to-end: 1 Write-Req + 3 Invalidate + 3 Inv-Ack + 1 Write-Ack = 8.)

Invalidation-and-ack handshake neeche dikhaya gaya hai — red invalidates aur white acks trace karo.

Exercise 2.5 — Exclusive state (MESI E)

MESI mein ek fourth state hai, Exclusive (E): exactly ek cache clean copy rakhta hai (memory valid hai, Modified se unlike). Maano directory core 4 ko block $⟨ Exclusive, {4}⟩$ grant karta hai ek otherwise-Uncached block ke lone read par. (a) Lone read par E kyun grant karein Shared ki jagah? (b) Core 4 kya kar sakta hai jo ek Shared holder nahi kar sakta? (c) Agar core 7 phir read issue kare, toh kya state banega aur kya memory update chahiye?

Recall Solution

(a) Jab read miss block Uncached paata hai (koi doosra sharer nahi), directory jaanta hai core 4 akela holder hai. Exclusive grant karne se core 4 baad mein silently write kar sakta hai (E→M bina kisi directory traffic ke), ek future upgrade round-trip avoid karte hue. Yeh ek pure latency optimization hai. (b) Shared holder ko Write-Req bhejna padta hai aur Write-Ack ka wait karna padta hai likhne se pehle. Exclusive holder E→M locally transition kar sakta hai — koi message nahi chahiye, kyunki directory pehle se jaanta hai kisi aur ke paas copy nahi hai. (c) Core 7 ka read HD tak pahuncha; HD dekhta hai block Exclusive at core 4 hai. Kyunki E clean hai (memory valid), core 4 sirf E→Shared downgrade karta hai aur data memory se aa sakta hai (ya core 4 se). Result: $⟨ Shared, {4, 7}⟩$ , aur memory update ki zaroorat NAHI — E kabhi dirty nahi tha. (Contrast Modified se, jo write-back force karta hai kyunki memory stale thi.)

L3 — Analysis

(Kya aap cost aur trade-offs ke baare mein reason kar sakte ho?)

Exercise 3.1 — Full-map storage (aur kyun State field 2 bits ka hai)

Full-map entry width $2 + N$ bits hai: sharers vector ke liye $N$ bits aur State ke liye 2 bits. Pehle "2" justify karo: field ko kitne distinct states encode karne hain, aur kyun 2 bits kaafi hain (aur kya Exclusive add hone par bhi kaafi hote)? Phir, $N = 128$ cores aur $M = 2^{25}$ (lagbhag 33.5 million) tracked blocks ke liye, directory size MB mein compute karo ( $1 MB = 2^{23}$ bits lo).

Recall Solution

Kyun 2 State bits. $b$ bits ka ek field $2^{b}$ distinct values naam de sakta hai. Humare base protocol mein 3 states hain (Uncached, Shared, Modified). Hume $b$ chahiye jahan $2^{b} \geq 3$ : $b = 1$ sirf $2^{1} = 2$ deta hai (kam hai), $b = 2$ deta hai $2^{2} = 4 \geq 3$ (kaafi, ek code spare). Toh 2 bits kaafi hain. Exclusive add karne se 4 states ho jaati hain, aur $2^{2} = 4$ exactly — abhi bhi 2 bits, pehle-spare code use karte hue. Ek 5th state (jaise MOESI ka Owner) ko $2^{3} = 8$ ⇒ 3 bits chahiye. Isliye parent ka formula 2 bake in karta hai. Storage. Full-map entry width $= 2 + N = 2 + 128 = 130$ bits. $Size = M \times (2 + N) = 2^{25} \times 130 bits .$ $2^{25} \times 130 = 33, 554, 432 \times 130 = 4, 362, 076, 160$ bits. MB mein: $\frac{4 , 362 , 076 , 160}{2 ^{23}} = \frac{4 , 362 , 076 , 160}{8 , 388 , 608} = 520$ MB. Jawab: 520 MB. Dhyan do yeh dono $M$ aur $N$ mein linearly scale karta hai — isliye full-map high core counts par fail hoti hai.

Exercise 3.2 — Broadcast vs. point-to-point traffic

Snooping ke under, ek miss baaki saare $N - 1$ cores ko broadcast karta hai. Directory ke under, ek miss home + zyada se zyada $k$ sharers ko touch karta hai. Humare ground-rule message definition use karte hue, $N = 64$ aur $k = 3$ ke liye: (a) ek snoop broadcast se reach hone wale cache-endpoints? (b) home + sharers ko directory fan-out (sirf requests, acks nahi)? (c) un dono fan-outs ka ratio. (d) Kaun si per-miss cost $O (N)$ hai aur kaun si $O (1)$ ?

Recall Solution

Like se like compare karne ke liye hum request-side fan-out count karte hain (kitne endpoints tak request pahunche) dono schemes ke liye; yeh explicitly state kiya gaya hai taaki end-to-end counts ke saath confusion na ho L2 ki tarah. (a) Snooping: 1 broadcast $N - 1 = 63$ caches tak pahuncha → 63 endpoints. (b) Directory: 1 request home ko + zyada se zyada $k = 3$ sharer messages → $1 + 3 = 4$ endpoints. (c) Ratio $= 63/4 \approx 15.75 \times$ kam. (d) Per miss, snooping $O (N)$ hai (broadcast saare $N - 1$ cores ko touch karta hai) jabki directory $O (1 + k) = O (1)$ hai ( $k$ se bounded, $N$ se independent). Famous $O (N^{2})$ aggregate hai: $N$ cores har ek $O (N)$ -fan-out misses generate karte hain ⇒ $O (N^{2})$ system-wide — yeh ek whole-system rate hai, per-miss cost nahi.

Exercise 3.3 — NUMA home lookup

Ek 4-socket server memory ko 256B chunks mein interleave karta hai. Address layout: [ tag | socket-select (2 bits) | 256B offset (8 bits) ], humare LSB-0 bit numbering use karte hue. Address 0x8300 ke liye home kaun sa socket hai?

Recall Solution

LSB-0 numbering ke under, bit 0 sabse daayaan bit hai. 256B offset bits 0–7 par occupy karta hai (kyunki $2^{8} = 256$ ); 2 socket-select bits thoda upar, bits 8–9 par hain. $0x8300 = 100000110000000 0_{2}$ . Low 8 bits (offset) $= 00000000$ . Bits 8–9: right shift by 8 → 0x8300 >> 8 = 0x83 = 1000\ 0011; uske low 2 bits $= 1 1_{2} = 3$ . Home = Socket 3. (Offset ke upar interleaving consecutive blocks ko sockets mein spread karta hai jabki har block ke bytes local rehte hain.)

L4 — Synthesis

(Kya aap states, ordering, aur consistency combine kar sakte ho?)

Exercise 4.1 — Full read-then-write trace with ack ordering

Block $X$ at 0xA000, initially Uncached, memory $X = 42$ . Sequence: (1) Core 0 reads, (2) Core 3 reads, (3) Core 1 writes $X = 99$ . Har step ke baad directory entry do aur exactly batao ki Core 1 apna store kab perform kar sakta hai.

Recall Solution

Step 1 — Core 0 read: Uncached → HD $X = 42$ reply karta hai, entry $⟨ Shared, {0}⟩$ ho jaati hai (memory valid). Step 2 — Core 3 read: Shared → HD core 3 add karta hai, $X = 42$ reply karta hai, entry $⟨ Shared, {0, 3}⟩$ . Step 3 — Core 1 write:

Core 1 → HD Write-Req. HD sharers ${0, 3}$ ko Invalidate bhejta hai (2 invalidations).
Core 0 → HD Inv-Ack; Core 3 → HD Inv-Ack. HD 2 acks collect karta hai.
Dono acks ke baad hi HD Core 1 ko Write-Ack bhejta hai aur $⟨ Modified, {1}⟩$ set karta hai.
Core 1 ab $X = 99$ store karta hai; memory baad mein write-back hone tak stale ho jaati hai. Core 1 kab store kar sakta hai? Write-Ack receive karne ke baad, yaani jab HD ne confirm kar diya ki dono stale readers gone hain. Pehle store karna core 0 ya 3 ko purana 42 nayi 99 ke saath concurrently padne deta — yeh coherence violation hoga.

Exercise 4.2 — Consistency ordering

Do cores har ek code run karte hain. Core A: store flag = 1. Core B: spins while(flag == 0); phir load data. Directory terms mein explain karo ki ack-before-write-ack rule hi kyun hai jo B ko kabhi stale flag nahi padne deta. Phir precisely batao ki coherence akele kya guarantee nahi karta, aur kaun sa mechanism woh supply karta hai. Memory consistency models se relate karo.

Recall Solution

Part 1 — kyun B purana flag nahi dekhta. Maano flag Shared start hota hai (dono cores ise read-only cache karte hain, value 0). Jab Core A store flag = 1 execute karta hai:

A Shared se write nahi kar sakta; woh HD ko Write-Req bhejta hai.
HD B ki flag copy ko Invalidate bhejta hai aur B ka Inv-Ack wait karta hai A ko write grant karne se pehle (Write-Ack), exactly Ex 4.1 ka rule.
B ka cached flag ab Invalid hai, toh B ki agli loop iteration miss karti hai aur re-fetch karna padta hai — woh physically stale 0 nahi padh sakta. Jab A ki write complete hoti hai, woh re-fetch 1 return karta hai aur spin exit ho jaata hai. Yeh handshake wahi hai jo per-block coherence invariant enforce karta hai: flag ki ek single agreed value sab ko visible. Part 2 — coherence kya guarantee nahi deta. Coherence operations ko ek address (flag) par order karta hai. Woh kuch nahi kehta ki A ka earlier store data B ko A ke store flag = 1 se pehle visible ho ya nahi. Agar hardware A ke do stores ko reorder kare, toh B flag == 1 dekh sakta hai phir bhi stale data load kare. Cross-address ordering fix karna memory consistency model ka kaam hai (jaise A ke store par release fence, B ke load par acquire). Dekho Memory consistency models. Takeaway: coherence (yeh note) + consistency model dono mil ke flag/data handshake correct banate hain; akele koi bhi kaafi nahi.

L5 — Mastery

(Kya aap design aur justify kar sakte ho?)

Exercise 5.1 — Protocol choose karna

Aap do chips architect kar rahe ho: (A) ek 8-core desktop CPU shared ring bus ke saath; (B) ek 96-core, 6-chiplet server bina shared bus ke. Har ek ke liye snooping ya directory choose karo aur scaling argument se justify karo.

Recall Solution

Chip A (8 cores, shared bus): snooping choose karo. Broadcast latency ek single low-latency hop hai; per-miss traffic sirf $O (N) = 7$ endpoints hai — sasta. Directory indirection ek hop add karega bina kisi bandwidth payoff ke. (Intel Core i7 se match karta hai.) Chip B (96 cores, 6 chiplets, no bus): directory choose karo. Physically koi shared bus nahi hai snoop karne ke liye, aur 95 caches ko broadcast interconnect saturate kar dega. Point-to-point (home + few sharers) per-miss traffic $O (1)$ rakhta hai. Directory ko chiplets mein distribute karo taaki koi single slice hot-spot na bane. (AMD EPYC se match karta hai.) Principle: protocol scale aur topology follow karta hai, "newness" nahi.

Exercise 5.2 — Limited-pointer directory design karna

$N = 256$ cores ke liye aap chahte ho ki har directory entry mein zyada se zyada $k = 4$ sharer IDs hon (full bit-vector nahi) plus 2 state bits. (a) Ek entry ka kitna bits cost aata hai? (b) Full-map per-entry width se compare karo. (c) Apne design mein correctness hazard ka naam batao.

Recall Solution

(a) Har sharer ID ko $⌈ lo g_{2} 256 ⌉ = 8$ bits chahiye. Chaar pointers $= 4 \times 8 = 32$ bits, plus 2 state bits $= 34$ bits per entry. (b) Full-map per entry $= 2 + N = 2 + 256 = 258$ bits. Limited-pointer $34$ bits hai — lagbhag $258/34 \approx 7.6 \times$ chhota. (c) Overflow hazard: agar 5th core share karna chahe, toh koi slot nahi hai. Ex 5.3 mein exactly yahi hota hai.

Exercise 5.3 — Sharer-set overflow: $k$ se aage kya hota hai

Ex 5.2 ka design continue karo ( $k = 4$ pointers). Block $P$ ke abhi sharers ${1, 6, 20, 44}$ hain — entry full hai. Ab core 100 $P$ ka read issue karta hai. (a) Entry core 100 record kyun nahi kar sakti? (b) Is overflow handle karne ke liye do standard hardware policies aur unka cost batao. (c) Jab core 200 baad mein $P$ write kare, toh har policy overflow ke liye kaise pay karta hai?

Recall Solution

(a) Entry exactly $k = 4$ pointer slots rakhti hai aur chaaro ${1, 6, 20, 44}$ se occupied hain. 5th distinct sharer ID ka koi encoding nahi — hardware ne maximum $k$ assume kiya tha. Toh core 100 simply add nahi ho sakta. (b) Do standard policies:

Broadcast fallback (coarse vector): entry ek special "bahut zyada sharers" mode mein flip ho jaati hai — woh individuals track karna band kar deti hai aur block ko "sab ke dwara shared (ya cores ke ek coarse group ke dwara)" mark kar deti hai. Cost: future invalidations us poore group ko broadcast karni padti hain, is block ke liye point-to-point win kho jaata hai.
Eviction / forced invalidation: directory ek current sharer choose karta hai (maano core 1), use Invalidate bhejta hai, ack collect karta hai, slot free karta hai, aur core 100 insert karta hai. Cost: ek false invalidation — core 1 ek perfectly valid read-only copy kho deta hai aur dobara $P$ padne par miss karega. (c) Jab core 200 $P$ write kare (Shared → Modified):
Broadcast fallback ke under, HD ko poore coarse group ko Invalidate bhejna padta hai aur saare unke acks collect karne padte hain — potentially dozens of messages, bhaley hi sirf 4–5 cores ne $P$ cache kiya ho.
Eviction ke under, sharer set kabhi 4 se zyada nahi hui, toh write sirf un ≤4 tracked cores ko invalidate karta hai — sasta invalidation, lekin koi earlier reader (core 1) false invalidation se pehle hi pay kar chuka tha. Design lesson: limited pointers storage trade karte hain (34 vs 258 bits, Ex 5.2) occasional traffic/false invalidations ke liye overflow par. $k$ chunno jo common sharing degree cover kare taaki overflow rare ho.

Cores 4 aur 7 alag-alag variables par write karte hain jo ek hi 64B cache block mein hoti hain. Directory har alternating write par kya karta hai trace karo, aur Cache line false sharing se connect karo. Yeh expensive kyun hai bhaley hi dono cores ek byte bhi share na karein?

Recall Solution

Directory coherence track karta hai block granularity par, variable granularity par nahi. Toh:

Core 4 apna var write karta hai → block Modified ho jaata hai, sharers ${4}$ ; core 7 ki copy invalidate ho jaati hai.
Core 7 apna var write karta hai → HD core 4 ko invalidate karta hai, ownership ping-pong hoti hai sharers ${7}$ par.
Repeat → block dono owners ke beech har write par bounce karta hai. Yeh false sharing hai: variables independent hain, lekin block shared hai, toh coherence protocol unhe serialize karta hai. Cost = repeated invalidations + owner-forwarding hops, bhaley hi koi true data dependence na ho. Fix (design mastery): dono variables ko alag cache lines mein pad karo taaki unke directory entries independent hon. Dekho Cache line false sharing.

Recall Self-test checklist (finish karne ke baad reveal karo)

$⟨ Shared, {1, 4, 7}⟩$ mein kitne caches hain? ::: Teen. Modified state mein "owner" kahan stored hota hai? ::: Woh Sharers set ka single element hai — koi alag owner field nahi. "Memory stale" ka matlab kya hai aur kaun si state mein hota hai? ::: Cache memory se newer value rakhta hai, toh memory definitive copy nahi — Modified mein sach. Modified block par read miss par data kaun supply karta hai? ::: Owning cache (forward + write-back ke zariye), directory nahi. Uncached block par read miss ke liye end-to-end messages? ::: 2 (Read-Req + Data reply; reads par koi acks nahi). Ek Exclusive holder kya kar sakta hai jo Shared holder nahi kar sakta? ::: Silently write karna (E→M) bina kisi directory messages ke. Sharers ${0, 2, 5, 8}$ ke saath sharer 5 ke write par invalidations? ::: 3 (writer ko chhodkar saare sharers). State field ko sirf 2 bits kyun chahiye (base protocol)? ::: 2 bits $2^{2} = 4$ codes encode karte hain, 3 (ya Exclusive ke saath 4) states ke liye kaafi. $N = 128$ , $M = 2^{25}$ blocks ke liye full-map directory size? ::: 520 MB. Per-miss request fan-out: snooping vs directory (big-O)? ::: $O (N)$ vs $O (1)$ ; $O (N^{2})$ aggregate hai, per-miss nahi. Jab limited ( $k$ -pointer) directory ka sharer set overflow ho toh kya hota hai? ::: Broadcast fallback (coarse vector) ya forced/false invalidation ke zariye ek sharer evict karo. Kaun sa per-line trap disjoint variables ko expensive banata hai? ::: False sharing.