Cache coherence problem — Hinglish notes

5.4.14 · Hardware › Memory Hierarchy & Caches

YE problem exist hi kyun karti hai?

KYA chahiye humein: har core ko memory aise dikhni chahiye jaise har address ki ek hi, up-to-date copy ho. Is illusion ko coherent memory system kehte hain.

KYUN toot jaata hai: caches speed ke liye hote hain. Har core hot data ki ek private copy rakhta hai taaki use baar baar slow main memory tak jaana na pade. Lekin jaise hi ek se zyada private copies hoti hain, ek copy pe write automatically doosri copies ko update nahi karta. Ab do cores address X pe kya hai is baat mein disagree kar sakte hain.

Concrete scenario

Setup: Core A aur Core B dono ke paas private cache hai. Shared variable X = 5 main memory mein hai.

Step	Action	Cache A	Cache B	Memory
0	initial	—	—	X=5
1	A reads X	X=5	—	X=5
2	B reads X	X=5	X=5	X=5
3	A writes X=10 (write-back)	X=10	X=5 ❌	X=5 ❌
4	B reads X	X=10	X=5 (stale!)	X=5

Step 4 par, B apni cached copy padhta hai aur 5 milta hai, lekin true logical value 10 hai. Yahi incoherence hai.

Coherence ko precisely define karna

Hum bug detect kaise karte hain? (ek mini "derivation")

Hum failure condition ko first principles se derive kar sakte hain instead of memorise karne ke.

Maan lo ek cached line valid hai agar cache_value == true_logical_value. Read tab cache value return karta hai jab valid ho, warna memory se fetch karta hai.

Ek invariant define karo jo hum CHAHTE hain: $\forall cores i, j : Valid_{i} (X) \land Valid_{j} (X) \Rightarrow cache_{i} (X) = cache_{j} (X)$

Ab core $i$ pe ek write consider karo: cache_i(X) := new. Ye assignment sirf $i$ ki copy badalta hai. Jab tak protocol ye bhi nahi karta ek mein se kuch:

$Valid_{j} (X) := false$ (doosri copies ko invalidate karo), ya
$cache_{j} (X) := n e w$ sabhi $j$ ke liye (doosri copies ko update karo),

invariant violate hota hai jab bhi koi doosri valid copy exist karti thi. Isse hume do protocol families milti hain:

Worked examples

Forecast-then-verify

Recall Answer

B stale 5 padhta hai (apne cache se). 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. Protocol pehle ko fix karne ke liye zaroori hai; write-back timing doosre ko control karti hai.

Flashcards

Cache coherence problem kya hai?

Jab multiple private caches ek hi address ki copies rakhte hain, ek copy pe write doosre caches (aur/ya memory) ko stale values hold karta chhor sakta hai, toh cores value pe disagree karte hain.

Coherence ki 3 conditions batao.

(1) Ek processor apna last write khud padhta hai (program order), (2) write propagation — ek write eventually doosron ko dikh jaata hai, (3) write serialization — saare cores ek location pe writes ko same order mein dekhte hain.

Kya write-through coherence solve karta hai?

Nahi. Ye memory fresh rakhta hai lekin doosre caches ko update ya invalidate nahi karta; woh abhi bhi apni stale copies padhte hain.

Coherence vs consistency?

Coherence = caches ke across ek single address ka behaviour; consistency = alag-alag addresses ke across operations ki ordering.

Write ke baad coherence enforce karne ke do tarike?

Write-invalidate (doosri copies invalid mark karo) ya write-update/broadcast (doosri copies ko nai value push karo).

Write-invalidate usually write-update se better kyun hai?

Ek hi line pe repeated writes sirf ek invalidation generate karte hain lekin kai update broadcasts, toh invalidate kam bus traffic produce karta hai.

Write-update, write-invalidate ko kab beat kar sakta hai?

Tight producer/consumer sharing mein jahan reader ko value turant chahiye har write ke baad, update ek subsequent read miss avoid karta hai.

Core i pe write ke baad coherence invariant kya restore karta hai?

Kahin bhi stale valid copies eliminate karo — ya toh unhe invalidate karo ya unhe nai value se update karo.

Recall Feynman: ek 12-saal ke bachhe ko explain karo

Socho tum aur tumhara dost dono apne team ka score bade scoreboard se copy karke ek personal notebook mein rakhte ho. Tum ek point score karte ho aur apni notebook mein naya number likh dete ho — lekin tumhare dost ki notebook aur bada board dono purana number hi dikhate hain. Ab koi agree nahi karta. Fix karne ke liye, ya toh tum chillate ho "apna number kaat do!" (invalidate) ya "sabhi naye number mein badlo!" (update). Exactly yehi CPU caches ko karna hota hai taaki saare cores agree karein ki actually kya stored hai.

Connections

Write-through vs Write-back — memory-vs-cache gap control karta hai (coherence se alag gap).
MESI Protocol — standard write-invalidate state machine jo ye solve karta hai.
Snooping vs Directory Coherence — invalidations kaise broadcast/track hoti hain.
Memory Consistency Models — alag-alag addresses ke across ordering.
False Sharing — line-granular coherence ka ek performance side effect.
Bus Traffic & Scalability — kyun update protocols scale nahi karte.