Cache coherence — MESI protocol in multicore

4.1.13 · Coding › Computer Architecture (Deep)

YEH problem exist kyun karti hai?

Hum sab kuch seedha DRAM par kyun nahi likhte (write-through, no caching)? Kyunki writes bahut zyada frequent hote hain; har baar DRAM jaana ek multi-GHz core ko almost apna poora time stalling mein bita dega. Hum private caches chahte hain. Toh humein ek rule set chahiye jo private caches ko behave karaaye jaise ek shared memory ho.

Chaar states (HAR EK ka matlab)

HOW it works: bus snooping mechanism

Figure — Cache coherence — MESI protocol in multicore

Transition table (iska dil)

IS core ki request par:

Current	Read hit	Write hit	Read miss →	Write miss →
I	—	—	BusRd issue karo → E (agar koi sharer nahi) ya S	BusRdX issue karo → M
S	S rahega	BusUpgr issue karo → M	—	—
E	E rahega	silent → M	—	—
M	M rahega	M rahega	—	—

DOOSRE core ki request snoop karne par (yeh core ek bystander hai):

Meri state	Mujhe BusRd dikha	Mujhe BusRdX/Invalidate dikha
M	dirty data flush karo, → S	dirty data flush karo, → I
E	→ S	→ I
S	S rahega	→ I
I	—	—

Worked example 1 — classic counter race, MESI ke through

Do cores; initially X=0 sirf DRAM mein hai. Dono caches: I.

Core0 X padhta hai. Miss → BusRd. Kisi doosre cache ke paas nahi → Core0 ko E milta hai (clean, sole owner). E kyun, S kyun nahi? Kyunki snoop response ne kaha "koi sharers nahi," toh sole-owner optimization apply hoti hai.
Core0 X=1 likhta hai. E mein hit → silent upgrade to M. Yeh step kyun? E mein hum jaante hain hum akele hain, toh koi invalidation nahi chahiye — zero bus traffic. Memory ab stale hai (abhi bhi 0), lekin theek hai; M sach ka owner hai.
Core1 X padhta hai. Miss → BusRd. Core0 snoop karta hai, dekhta hai uske paas M hai → value 1 flush karta hai (cache-to-cache, memory bhi update hoti hai), S par aa jaata hai. Core1 value 1 ke saath S install karta hai. Yeh step kyun? Flush mandatory hai; warna Core1 stale DRAM 0 padhta. SWMR "single writer" se "multiple reader" par shift hota hai.
Core1 X=2 likhta hai. S mein hit → BusUpgr/Invalidate issue karo → M. Core0 invalidate snoop karta hai, uski S copy → I. Yeh step kyun? Likhne ke liye, aapko single writer banna padega; baaqi sab ko pehle invalidate karna hoga.

Result: har step par exactly ek writer ya many readers — kabhi dono nahi. Reads hamesha latest value return karte hain.

Cost derive karna (back-of-envelope first principles)

Common mistakes (Steel-manned)

Recall Feynman: 12-saal ke bachche ko explain karo

Socho chaar bachche, har ek ke paas apna personal whiteboard hai, ek bade chalkboard (DRAM) se same number copy karke. Agar ek bachcha apna number badal le lekin chalkboard aur doosre bachche ko pata na chale, toh sab argue karenge. Toh woh sticky notes ke saath rules banate hain:

M = "Maine ise badla hai aur SIRF mere paas nayi number hai — chalkboard outdated hai, mujhse pooch!"
E = "Main akela hun jisne ise copy kiya aur maine abhi change nahi kiya."
S = "Hamme se kai logo ne copy kiya hai, lekin kisi ne change nahi kiya — hum sab agree karte hain."
I = "Mera whiteboard blank/galat hai, isko ignore karo." Rule: kisi bhi bachche ke number change karne se pehle, woh chillata hai "sablog apna mita lo!" taaki kabhi aisa na ho ki ek bachcha edit kare aur doosre purani cheez padhen. Woh chillana hai bus broadcast, aur poora game MESI hai.

Active-recall flashcards

#flashcards/coding

Cache coherence har memory line ke liye kaun sa invariant enforce karta hai?

Single-Writer / Multiple-Reader (SWMR): kisi bhi instant par ek writable copy YA kai read-only copies, kabhi dono nahi.

M, E, S, I letters kiske liye stand karte hain?

Modified, Exclusive, Shared, Invalid.

M aur E mein kya fark hai?

Dono sole copies hain; M dirty hai (memory stale, write-back needed), E clean hai (memory se match karta hai, koi write-back nahi, silently M mein upgrade ho sakta hai).

E state kyun exist karta hai (performance reason)?

Yeh ek sole clean line ke write ko silently M mein upgrade karne deta hai zero bus traffic ke saath, kyunki cache pehle se jaanta hai koi doosra sharer nahi hai.

Write miss ya write-to-Shared par kaun sa bus message bheja jaata hai?

BusRdX / Read-For-Ownership (RFO) — write ke iraade ke saath read, jo doosri copies invalidate karta hai.

M state mein ek cache doosre core ka BusRd snoop karta hai. Kya hota hai?

Woh dirty data flush karta hai (cache-to-cache + memory update) aur M → S transition karta hai.

M state mein ek cache BusRdX snoop karta hai. Kya hota hai?

Woh data flush karta hai aur M → I transition karta hai.

Coherence vs consistency — kya fark hai?

Coherence = sab cores ek single address ki value timeline par agree karte hain. Consistency = alag-alag addresses par operations ki ordering; memory model/fences ki zaroorat hai.

False sharing kya hai?

Alag cores alag variables likhte hain jo ek hi cache line share karte hain, line ko ping-pong karaate hain (M-invalidate cycles) bhaley hi koi real data sharing nahi hai. Fix: alag lines par pad/align karo.

Coherence miss kya hota hai?

Ek miss jo isliye hoti hai kyunki doosre core ke write ne is core ki copy invalidate kar di (state I ho gayi), capacity/conflict ki wajah se nahi.

Kisi doosre sharer ke bina read miss par, kaun si state enter hoti hai, aur kyun?

E (Exclusive), kyunki snoop response indicate karta hai koi doosra cache line hold nahi kar raha.

S-state write: kaun sa transition aur message?

BusUpgr/Invalidate issue karo, S → M transition karo, baaki sab S copies I ho jaati hain.

Connections

Cache basics — tags, sets, lines (line granularity hi wajah hai false sharing ki)
Memory consistency models (coherence ≠ consistency; fences, std::atomic)
Write-back vs write-through caches (M-state dirty data ko write-back chahiye)
Directory-based coherence (kai cores ke liye snooping ka scalable alternative)
Bus snooping and interconnects (woh broadcast medium jis par MESI rely karta hai)
MOESI and MESIF extensions (sharing optimize karne ke liye Owned/Forward states add karna)
Atomics, locks, and the LL-SC / cmpxchg (RFO + coherence ke upar banaya gaya)