Multicore coherence protocols — Hinglish notes

4.1.27 · Coding › Computer Architecture (Deep)

YEH problem exist kyun karti hai?

KYA HAI: Modern CPUs mein har core ke paas private L1/L2 caches hote hain taaki slow main memory (DRAM ≈ 100 ns vs L1 ≈ 1 ns) ko hide kiya ja sake.

YEH kyun break karta hai: Caches copies hote hain. Agar Core 0 ne x=5 cache kiya, phir x=7 sirf apne cache mein likha, toh Core 1 ke cache mein abhi bhi purana x=5 pada rahega. Coordination ke bina, do cores x padhne par alag-alag answers lenge → program logic bilkul collapse ho jayega.

Coherence ≠ consistency. Coherence ek location ke baare mein hai; memory consistency alag-alag locations mein ordering ke baare mein hai. Yeh note coherence ke baare mein hai.

Hum ise enforce kaise karte hain: snooping bus idea

BUS kyun? Early multicores ek broadcast medium share karte hain. Har cache har transaction ko snoop (sunta) karta hai. Jab Core 1 ek block likhta hai, Core 0 use sunता hai aur react karta hai.

Do broad strategies hain:

Strategy	Write par kya hota hai	Cost
Write-invalidate	Writer broadcast karta hai "invalidate"; baaki sabhi copies drop ho jaati hain	1 invalidate per write-burst
Write-update	Writer naya value har copy tak broadcast karta hai	har write par bus traffic

Practice mein Invalidate jeet jaata hai (ek core aksar kai baar likhta hai kisi aur ke padhne se pehle), isliye famous protocols invalidate-based hain.

MSI ko scratch se banana

Humein har cached block ko ek state se label karna hoga. Minimum zaroori states ko reasoning se derive karte hain:

Ek block jo mere paas hai hi nahi → I (Invalid).
Ek block jo mere paas hai aur doosron ke paas bhi ho sakta hai, par kisi ne likha nahi → read kar sakte hain par bina permission ke write nahi → S (Shared).
Ek block jo maine likha hai → sirf mera hi valid copy hai, read/write freely kar sakta hoon → M (Modified).

Yahi minimal trio hai: MSI.

State transitions (rules, derived)

Processor read (PrRd) par:

I → S: BusRd issue karo (read miss). Agar kisi doosre cache mein M hai, use data supply karna hoga aur downgrade karna hoga.
S/M → same rehta hai.

Processor write (PrWr) par:

I → M: BusRdX issue karo (read-exclusive) → baaki sab invalidate ho jaate hain.
S → M: BusUpgr issue karo (baaki invalidate karo), koi data fetch zaroori nahi.
M → same rehta hai.

Snooped bus event par:

Kisi ka BusRd jab main M mein hoon → main data supply karta hoon, S mein chala jaata hoon (ab shared, memory updated).
Kisi ka BusRdX/BusUpgr → main I mein chala jaata hoon (invalidated).

MESI: killer optimization

Toh read miss par, bus ek shared signal check karta hai:

Kisi aur cache mein nahi → E ke roop mein load karo.
Kisi cache mein hai → S ke roop mein load karo.

MESI hi hai jo real Intel/ARM chips use karte hain (extensions ke saath).

MOESI: 'O' (Owned) add karo

KYUN: MESI mein, jab koi doosra core ek M block padhta hai, toh woh memory mein write-back karta hai phir dono S mein chale jaate hain. O owner ko dirty copy rakhne aur use sharers ko directly supply karne deta hai (cache-to-cache), costly memory write-back ko defer karte hue. AMD use karta hai.

Worked examples

Common mistakes (steel-manned)

Flashcards

Cache coherence define karne wali do properties kya hain?

Write propagation (read most recent write dekhta hai) aur write serialization (sabhi cores ek location par writes same order mein dekhte hain).

Coherence aur consistency mein farq?

Coherence = ek location par accesses ki ordering; consistency = multiple locations mein ordering.

MSI states ka matlab kya hai?

M = sirf valid (dirty) copy, read/write; S = clean shared read-only copy; I = invalid/no data.

Write-invalidate practice mein write-update se behtar kyun hai?

Ek core aksar ek block kai baar likhta hai kisi doosre core ke padhne se pehle; ek invalidate puri burst amortize karta hai, per-write broadcasts avoid karte hue.

MESI mein E (Exclusive) state kya problem solve karta hai?

Ek solely-owned clean block ko write par bina kisi bus transaction ke M mein upgrade kiya ja sakta hai, wasted BusUpgr traffic eliminate karta hai.

E vs M state ka farq?

E clean hai (memory se match karta hai, eviction par write-back ki zaroorat nahi); M dirty hai (memory stale hai, write back karna zaroori hai).

False sharing kya hai?

Ek hi cache line mein independent variables ki wajah se line cores ke caches ke beech ping-pong karta rehta hai invalidations ki wajah se, chahe koi real data share nahi ho raha.

MOESI mein O (Owned) state kya add karta hai?

Ek core ko dirty block rakhne deta hai aur use cache-to-cache sharers ko supply karne deta hai, costly memory write-back defer karte hue.

MSI mein S state se PrWr par kaunsa bus transaction issue hota hai?

BusUpgr (doosre sharers ko invalidate karo); koi data fetch zaroori nahi kyunki block already present hai.

MSI mein M-state core ko doosre core ke read par kyun downgrade karna padta hai?

Ab ek doosra reader exist karta hai, isliye block ab exclusive nahi raha; owner data supply karta hai, write back karta hai, aur M→S move karta hai.

Recall Feynman: explain to a 12-year-old

Socho 4 bachche ek shared notebook se same page copy karte hain. Agar ek baccha apni copy par naya answer likh deta hai, toh baaki ke paas purana wala rehta hai. Toh woh ek rule banate hain: kuch bhi change karne se pehle chillao "sabhi log, woh page cross out karo!" Ab jab bhi koi use dobara chahega, use fresh version milega. Yeh chillana-aur-cross-out-karna wali rule hi coherence protocol hai. "E" wali fancy trick yeh hai: agar ek bacche ko pata hai sirf uske paas copy hai, toh woh chupchap change kar sakta hai bina chillaye.

Connections

Cache memory hierarchy — coherence yahan se cache lines par operate karta hai.
Memory consistency models — coherence ka "bada bhai" jo cross-address ordering handle karta hai.
False sharing and padding — line-granularity coherence ka performance pitfall.
Snooping vs Directory protocols — directories coherence ko shared bus se aage (NUMA tak) scale karti hain.
Atomic operations and fences — coherence + consistency ke upar built hain.
Bus arbitration — broadcast medium transactions ko kaise serialize karta hai.