Cache coherence problem: Exercises — Hinglish deep dive

5.4.14 · D4 · Hardware › Memory Hierarchy & Caches › Cache coherence problem

Yeh page Cache Coherence Problem ke liye ek self-test ladder hai. Har problem ko pehle khud solve karo, tab solution dekho. Difficulty badhti hai L1 Recognition → L2 Application → L3 Analysis → L4 Synthesis → L5 Mastery. Har solution complete hai, isliye tum khud grade kar sakte ho.

Do words jo hum poore time use karte hain, ek baar define karte hain taaki koi symbol unexplained na rahe:

Level 1 — Recognition

Exercise 1.1

Ek sentence mein batao ki cache coherence problem kya hai.

Recall Solution

Jab multiple private caches same memory address ki copies rakhte hain, toh ek core ka write doosre caches ko (aur possibly main memory ko) stale values ke saath chhod sakta hai, isliye alag-alag cores ek hi address ke liye alag-alag numbers padhte hain.

Exercise 1.2

Inme se kaun sa coherence concern hai aur kaun sa consistency concern? (a) Sabhi cores ko address X pe writes ek hi order mein observe karne chahiye. (b) Alag-alag addresses X aur Y ke operations ke allowed orderings.

Recall Solution

(a) coherence hai — yeh ek single address ke baare mein hai across caches (yeh write-serialization rule hai).
(b) consistency hai — yeh alag-alag addresses ke across ordering ke baare mein hai. (b) ke liye dekho Memory Consistency Models. Coherence = kya value; consistency = kab/kis order mein across locations.

Exercise 1.3

True ya False: "Write-through caches main memory ko hamesha fresh rakhte hain, isliye yeh cache coherence solve kar deta hai."

Recall Solution

False. Write-through memory ko fresh rakhta hai, lekin yeh doosre core ke cache ko touch nahi karta. Woh doosra cache phir bhi apni stale copy return kar sakta hai. Write-through memory-vs-cache gap band karta hai; coherence cache-vs-cache gap hai. Dekho Write-through vs Write-back.

Level 2 — Application

Exercise 2.1

Setup: X = 5 memory mein. Core A aur Core B dono write-back caches use karte hain, koi coherence protocol nahi. Copies trace karo:

A reads X, 2. B reads X, 3. A writes X = 20, 4. B reads X.

Cache A, Cache B, Memory ko har step ke baad fill karo, aur batao B step 4 pe kya read karta hai.

Recall Solution

Step	Cache A	Cache B	Memory
1 A reads	X=5	—	X=5
2 B reads	X=5	X=5	X=5
3 A writes 20	X=20	X=5 ❌	X=5 ❌
4 B reads	X=20	X=5 (stale)	X=5

B reads 5. Yeh galat hai; true value 20 hai. Memory bhi abhi bhi 5 hai kyunki write-back ne A ki dirty line abhi flush nahi ki. Do independent bugs — cache-vs-cache aur memory-vs-cache.

Exercise 2.2

Ab Exercise 2.1 ko write-invalidate protocol ke saath repeat karo. Step 3 pe kya hota hai aur B step 4 pe kya read karta hai?

Recall Solution

Step 3: A writes X=20 → A ek invalidate broadcast karta hai → Cache B apni X copy ko Invalid mark kar deta hai.
Step 4: B reads X → uski copy Invalid hai → yeh ek forced miss hai → B fresh value fetch karta hai → 20 milta hai. ✅

Invalidate ne B ki silent staleness ko loud miss mein convert kar diya, aur yahi miss correct value khinchta hai. Dekho MESI Protocol.

Exercise 2.3

Write-update (broadcast) ke under, step 3 ke baad B ke cache mein kya hoga, aur kya B ka step-4 read ek miss cause karega?

Recall Solution

Step 3 ke baad, A new value 20 broadcast karta hai; B ki copy in place update ho jaati hai X=20 (abhi bhi valid).
Step 4 read ek hit hai jo 20 return karta hai — koi miss nahi. ✅

Update write ke time ek broadcast spend karta hai taaki reader baad mein miss se bache. Yeh trade jeetega ya nahi yeh sharing pattern pe depend karta hai (agla level).

Level 3 — Analysis

Exercise 3.1

Core A X ko chaar baar row mein write karta hai, phir Core B (ek single doosra sharer) X ko ek baar read karta hai. Write-invalidate vs write-update ke liye bus events count karo. (Ek "event" = ek invalidate broadcast, ek update broadcast, ya ek read miss serviced.)

Recall Solution

Write-invalidate:

Write 1: A ke paas abhi exclusive ownership nahi → B ko knock out karne ke liye 1 invalidate. Ab A ke paas exclusive ownership hai.
Writes 2, 3, 4: A already exclusive owner hai → 0 events each.
B ka read: B ki copy invalid → 1 read miss.
Total $= 1 + 0 + 0 + 0 + 1 = 2$ events.

Write-update:

Writes 1–4: har ek B ko new value push karta hai → 4 update broadcasts.
B ka read: copy already fresh → 0.
Total $= 4 + 0 = 4$ events.

Invalidate jeetता hai 2 vs 4. Ek core ke ek line pe repeated writes, update ke liye killer case hai.

Exercise 3.2

Ab reverse pattern: A X ko ek baar write karta hai, phir B X ko paanch baar back-to-back read karta hai (aur koi write nahi). Har protocol ke liye bus events count karo.

Recall Solution

Write-update:

Write: 1 update broadcast (B ki copy ab fresh).
Reads 1–5: sabhi hits → 0 events.
Total $= 1$ .

Write-invalidate:

Write: 1 invalidate.
Read 1: B ki copy invalid → 1 miss (fresh 20 fetch karta hai; ab valid phir se).
Reads 2–5: hits → 0.
Total $= 1 + 1 = 2$ .

Update jeetता hai 1 vs 2. Jab reader ko har write ke baad turant value chahiye, update miss se bachata hai.

Exercise 3.3

Woh coherence invariant derive karo jo write violate karta hai, phir usse restore karne ke do tarike batao.

Recall Solution

Invariant jo chahiye — koi bhi do cores jo dono sochte hain unki copy valid hai, unhe agree karna chahiye: $\forall i, j : Valid_{i} (X) \land Valid_{j} (X) \Rightarrow cache_{i} (X) = cache_{j} (X)$ Core $i$ pe write karne se $cache_{i} (X) := new$ hota hai, sirf $i$ ki copy badlती hai. Agar koi doosri valid copy $j$ purani value ke saath thi, toh equation ke dono sides ab alag hain — invariant toot gaya.

Do repairs (stale valid copy eliminate karo): $Write-Invalidate: \forall j \neq = i : Valid_{j} (X) \leftarrow false$ $Write-Update: \forall j \neq = i : cache_{j} (X) \leftarrow new$

Level 4 — Synthesis

Exercise 4.1

Tumhe ek workload mix diya gaya hai. Har pattern ke liye invalidate ya update choose karo aur ek line mein justify karo. (a) Ek lock/flag jo ek core ke beech reads ke beech kai baar write hota hai. (b) Ek tight producer/consumer jahan B har value jo A produce karta hai exactly ek baar, turant consume karta hai. (c) Ek widely-shared read-mostly config value jo A ek ghante mein ek baar rewrite karta hai.

Recall Solution

(a) Invalidate. Ek owner ke kai writes → pehle invalidate ke baad writer line ka owner ban jaata hai aur baad ke writes free hain. Update har write pe broadcast karta.
(b) Update. Har cycle mein ek write phir turant read → update B ki copy fresh rakhta hai aur read miss se bachata hai (Exercise 3.2 logic).
(c) Dono saste hain, invalidate preferred. Ek ghante mein ek write negligible traffic hai; kai sharers ke saath, ek update unhe sabko broadcast karta, jabki invalidate ek invalidation bhejtا hai aur sharers ko lazily re-fetch karne deta hai sirf agar unhe ab bhi zarurat ho.

Exercise 4.2

Ek cache line mein do independent variables X (sirf A use karta hai) aur Y (sirf B use karta hai) hain, same line mein packed. A repeatedly X write karta hai; B repeatedly Y write karta hai. Write-invalidate ke under kya pathology hoti hai aur ise kya kehte hain?

Recall Solution

Jab bhi A, X write karta hai toh woh B ki poori line ki copy invalidate kar deta hai (coherence lines track karta hai, individual variables nahi), isliye B ka Y pe next access miss hota hai aur re-fetch karta hai. Phir B, Y write karta hai aur A ki line invalidate karta hai, A ko X touch karne ke liye re-fetch karne par majboor karta hai. Line caches ke beech "ping-pong" karta hai, haalaanki cores kabhi real data share nahi karte.

Yeh ==false sharing== hai. Fix yeh hai ki X aur Y ko alag cache lines pe rakh dein (padding/alignment). Dekho False Sharing.

Exercise 4.3

Explain karo kyun ek snooping bus protocol core count badhne pe struggle karta hai, aur kaun sa alternative scale karta hai.

Recall Solution

Snooping mein, har cache ek shared broadcast medium sunti hai; har coherence action (invalidate/update/miss) sabhi caches ko dikhti hai. Bus bandwidth fixed hai, isliye jaise cores badhte hain, total broadcast traffic badhta hai aur single bus saturate ho jaata hai — ek scalability wall (dekho Bus Traffic & Scalability).

Alternative ek directory protocol hai: ek directory record karta hai kaun se caches har line hold karte hain, isliye ek write messages sirf actual sharers ko bhejtа hai (point-to-point over a scalable interconnect) sabko broadcast karne ke bajaaye. Dekho Snooping vs Directory Coherence.

Level 5 — Mastery

Exercise 5.1

Design decision. Ek 32-core server ek workload run karta hai jo 90% single-writer bursts hai (ek core ek line pe hammer karta hai, doosre rarely read karte hain) with occasional wide sharing. Ek coherence design end-to-end choose karo: invalidate vs update, snoop vs directory. Upar ke exercises se har choice justify karo.

Recall Solution

Write-invalidate, kyunki dominant pattern single-writer bursts hai. Exercise 3.1 ne dikhaya ki invalidate N writes ko 1 event tak collapse karta hai; update N broadcasts pay karta. Overwhelmingly sahi base policy.
Directory-based, kyunki 32 cores shared broadcast bus pe saturate ho jaate (Exercise 4.3). Ek directory point-to-point interconnect pe sirf actual sharers ko invalidations bhejtی hai, sharing degree ke saath scale karti hai, core count ke saath nahi.
Net: ek invalidate + directory design (real many-core coherence ki shape). Yeh cheap-burst policy ko scalable delivery mechanism ke saath pair karta hai.

Exercise 5.2

Full trace + count. Teen cores A, B, C. Line uncached start hoti hai, X=5, write-invalidate protocol. Events: (1) A reads, (2) B reads, (3) C reads, (4) A writes X=9, (5) B reads, (6) C reads. Har event ka outcome list karo aur total bus events (miss ya invalidate = 1 event each).

Recall Solution

(1) A reads → miss, fetch → A valid. (1)
(2) B reads → miss, fetch → A,B valid. (1)
(3) C reads → miss, fetch → A,B,C valid (shared). (1)
(4) A writes 9 → 1 invalidate broadcast → B aur C dono Invalid mark hote hain; A ab exclusive/modified. (1)
(5) B reads → copy invalid → miss, fresh 9 fetch karo (A supply karta hai) → B valid, 9 hold karta hai. (1)
(6) C reads → copy invalid → miss, fresh 9 fetch karo → C valid, 9 hold karta hai. (1)

Total $= 3 + 1 + 1 + 1 = 6$ bus events. Note: ek invalidate dono sharers ko cover kiya (snoop bus pe single broadcast); baad ke do read misses unhe invalidate karne ki kimat hain.

Exercise 5.3

Prove karo ki teeno coherence conditions "no-protocol write-back" system mein fail hoti hain, har ek ke liye ek-line counterexample do.

Recall Solution

Maan lo X=5, A aur B dono ise cache karte hain.

Program order (self-read): A apne cache mein 7 write karta hai; agar A ka cache silently evict ho jaaye aur baad mein A-read stale memory (abhi bhi 5) pe miss kare, toh A apna khud ka write read karne mein fail hota hai. Violated without write propagation to memory.
Write propagation: A, 7 write karta hai; B hamesha ke liye apna cached 5 read karta rehta hai — A ka write kabhi B ko dikhta nahi. Violated.
Write serialization: A, 7 write karta hai, B, 8 write karta hai, koi serializing point nahi, C observe kar sakta hai 7-then-8 jabki D observe karta hai 8-then-7. Violated — us line ke liye koi agreed global order nahi. Har condition exactly woh guarantee hai jo ek coherence protocol restore karta hai.