Visual walkthrough — Cache coherence problem

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

---

Step 1 — Kuch bhi galat hone se pehle machine draw karo

WHAT. Do chhote computers ("cores") side by side baithe hain. Har ek ke paas apna ek chota fast notebook hai jise cache kehte hain. Unke neeche ek bada slow book hai jise main memory kehte hain. Memory ke andar ek single box hai jis par X likha hai — ise ek ek number jo ek address par stored hai samjho. Abhi us box mein number 5 hai.

WHY. Copies ke disagree karne ki baat karne se pehle humein woh layout dekhna hai jo copies ko exist karne deta hai: har core ke paas ek private notebook hai. Yahi privacy poori problem ka beej hai. Caches speed ke liye hain — apna notebook padhna fast hai; bade book tak jaana slow hai.

PICTURE. Do white boxes (caches) dekho — dono abhi khali hain. Sirf memory mein amber box mein value hai.

---

Step 2 — Dono cores read karte hain: ab teen copies hain

WHAT. Core A X read karta hai. Uske paas abhi X nahi hai, toh woh memory tak jaata hai, 5 dhundhta hai, aur use Cache A mein copy kar leta hai. Phir Core B bhi yahi karta hai. Ab X = 5 teen jagah ek saath hain: Cache A, Cache B, aur memory.

WHY. Reading ek copy ko private cache mein upar kheench leti hai taaki agla read fast ho. Yeh normal, correct, desirable behaviour hai — aur yahi woh kaam hai jo danger create karta hai. Ek address ki kai valid copies ab exist karti hain.

PICTURE. Do cyan arrows follow karo jo memory se upar dono caches mein ja rahe hain. Teeno X boxes mein same amber 5 dikhta hai — sab agree kar rahe hain. Yahi agreement hai jo hum abhi todne wale hain.

---

Step 3 — Core A write karta hai. Bug janam leta hai.

WHAT. Core A X ko 10 mein change karta hai. Kyunki yeh write-back caches hain (parent note ka setup), A naya value sirf apne notebook mein likhta hai — woh memory ya Cache B ko immediately nahi batata. Toh: Cache A mein 10 hai; Cache B mein abhi bhi 5 hai; memory mein abhi bhi 5 hai.

WHY. Write-back ek speed trick hai: har write par memory tak slow trip mat karo; bas locally scribble karo aur baad mein flush karo. Lekin ek local scribble ek copy ko touch karti hai. Baaki do copies ko kabhi inform nahi kiya gaya. Yahi woh exact moment hai jab coherence mar jaati hai.

PICTURE. Cache A par amber flash naya 10 dikhata hai. Do red ❌ marks Cache B aur memory par hain — dono ab stale hain (ek purani value hold kar rahe hain jo ab sach nahi hai).

---

Step 4 — Woh invariant likho jo hum CHAHTE the, aur dekhte hain kaise toota

WHAT. Aao symbols mein woh single rule state karte hain jo hamesha hold karna chahiye tha. Hum teen notations introduce karte hain — har ek earned:

$\underset{\begin{array}{c}\text{woh number jo core }i\\ \text{ke paas address }X\text{ ke liye hai}\end{array}}{\underbrace{{\text{cache}}_i(X)}}\underset{\begin{array}{c}\text{true/false: kya core }i\text{ ki}\\ \text{copy abhi bhi trustworthy hai?}\end{array}}{\underbrace{{\text{Valid}}_i(X)}}\underset{\begin{array}{c}\text{"har pair ke liye}\\ \text{cores }i\text{ aur }j\text{ ke"}\end{array}}{\underbrace{\forall i,j}}$

Woh rule jo hum chahte hain:

$\forall i,j:\underset{\text{A ki copy trusted}}{\underbrace{{\text{Valid}}_i(X)}}\wedge \underset{\text{B ki copy trusted}}{\underbrace{{\text{Valid}}_j(X)}}\Rightarrow \underset{\text{...toh woh equal hone chahiye}}{\underbrace{{\text{cache}}_i(X)={\text{cache}}_j(X)}}$

Zor se padho: "Agar do cores dono apni X ki copy par trust karte hain, toh un copies mein same number hona chahiye." Symbol $\wedge$ matlab aur; $\Rightarrow$ matlab toh.

WHY. Hum rule isliye likhte hain taaki hum precise moment point kar sakein jab woh toot jaata hai. Step 3 par, dono copies abhi bhi valid mark thi (${\text{Valid}}_A={\text{Valid}}_B=\text{true}$), phir bhi ${\text{cache}}_A(X)=10\ne 5={\text{cache}}_B(X)$. Left side ka and true hai; right side ka equal false hai. Invariant violate ho gaya.

PICTURE. Green invariant upar hai; neeche term-by-term breakdown mein offending clause red mein highlight hai — "dono valid, phir bhi equal nahi."

---

Step 5 — Core B apni stale copy read karta hai (the crash)

WHAT. Core B ab X read karta hai. Uska notebook 5 kehta hai aur valid marked hai, isliye B use trust karta hai aur 5 return karta hai — kabhi memory tak nahi jaata. Lekin sach value 10 hai. B ab confidently galat hai.

WHY. Yahi bug ka payoff hai. B ne apne rules ke hisaab se kuch galat nahi kiya — ek valid cached copy ko memory trip ke bina use karna supposed hai. Poori failure yeh hai ki "valid" ne jhooth bola. Note karo ki memory bhi abhi bhi 5 kehti hai, isliye memory se fetch karna bhi B ko bachata nahi (yeh alag write-back-timing bug hai).

PICTURE. Red arrow dikhata hai B ka read apne cache ke andar hi ruk jaata hai — kabhi memory tak nahi pahuncha. Returned value 5 ko red mein true value 10 ke against circle kiya gaya hai.

---

Step 6 — Fix forced hai: stale copies khatam karo. Sirf do tarike hain.

WHAT. Broken invariant par wapas jao. Ek write ne sirf core $i$ par ${\text{cache}}_i(X):=\text{new}$ set kiya. Rule ko restore karne ke liye, humein mismatch destroy karna hoga. Logically exactly do moves hain:

$\text{Invalidate: }\forall j\ne i:\underset{\text{baaki sabki copy "not trusted" mark karo}}{\underbrace{{\text{Valid}}_j(X)\leftarrow \text{false}}}$

$\text{Update: }\forall j\ne i:\underset{\text{naya number baaki sab mein push karo}}{\underbrace{{\text{cache}}_j(X)\leftarrow \text{new}}}$

Yahan $j\ne i$ matlab "writer ke alaawa har core," aur $\leftarrow$ matlab "gets set to."

WHY. Invariant sirf ${\text{Valid}}_i\wedge {\text{Valid}}_j\Rightarrow \text{equal}$ clause ke through toot ta hai. Ek broken implication ko dobara true banane ke liye ya toh left side false karo (invalidate — kisi Valid ko off karo) ya right side true karo (update — numbers ko force equal karo). Koi teesra lever nahi hai. Isliye yahi do protocol families hain jo exist kar sakti hain — humne inhe guess nahi kiya, logic ne inhe squeeze out kiya.

PICTURE. Left panel: invalidate move Cache B ko grey karta hai aur INVALID stamp lagata hai. Right panel: update move Cache B mein 10 flash karta hai. Dono trusted copies ko agree kara dete hain.

---

Step 7 — Kaun sa fix jeetta hai? Arrows gino (repeated-write case)

WHAT. Core A X ko teen baar lagaatar likhta hai, phir Core B ek baar read karta hai, B single sharer hai.

• Invalidate: pehla write 1 invalidate bhejta hai; uske baad A line exclusively own karta hai, toh writes 2 aur 3 kuch nahi bhejtein. B ka read phir miss hoga ⇒ 1 fetch. Total = 2 bus events.
• Update: 3 writes mein se har ek naya value broadcast karta hai ⇒ 3 updates; B ke paas already hai, toh uska read free hai. Total = 3 bus events.

WHY. Bus (woh shared wire jise sab caches sunti hain) scarce resource hai — zyada messages matlab worse scaling. Update har write par pay karta hai even jab koi read nahi kar raha. Isliye real CPUs (MESI Protocol) invalidate-based hain.

PICTURE. Do message-timelines stacked: invalidate ek baar fire karta hai phir quiet ho jaata hai (2 amber ticks); update har write par fire karta hai (3 amber ticks).

---

Step 8 — Woh edge case jo answer flip kar deta hai (producer/consumer)

WHAT. Ab A X ko ek baar likhta hai, aur B use immediately, repeatedly read karta hai (tight sharing).

• Update: 1 write ⇒ 1 update; B ki copy refresh ho gayi, baad ke har read free hain ⇒ 1 event.
• Invalidate: 1 write ⇒ 1 invalidate; B ka agla hi read ab miss ho jaata hai ⇒ 1 extra fetch ⇒ 2 events.

WHY. Jab reader har write ke turant baad value chahta hai, invalidate ka "forced miss" pure waste hai — value anyway chahiye thi. Isliye na koi protocol universally best hai; traffic pattern decide karta hai. Yahi "kaun kya kab touch karta hai" reasoning hai jis par Snooping vs Directory Coherence aur False Sharing build karte hain.

PICTURE. Step 7 ka mirror: yahan update short timeline hai (1 tick) aur invalidate lambi hai (invalidate + miss = 2 ticks) — winner flip ho gaya.

---

Ek picture mein summary

Upar sab kuch ek single flow mein compress: teen copies janam leti hain → ek write → invariant snap → do (aur sirf do) cures → traffic decide karta hai kaun sa cure.

Recall Feynman retelling — poora walk plain words mein

Tum aur ek dost dono scoreboard number 5 apne notebook mein copy karte ho — ab number teen jagah hai aur sab agree kar rahe hain. Tum score karte ho aur apna notebook 10 kar lete ho, lekin kisi ko nahi batate. Tumhara notebook, dost ka notebook, aur bada board ab teen... well, do alag numbers hold kar rahe hain, phir bhi tumhara dost apne 5 par trust karta hai. Jab woh apna notebook padhta hai toh confidently kehta hai "5" — galat. "Agar do log dono apni copy par trust karte hain, toh copies match karni chahiye" wala rule abhi toot gaya, aur woh uss clause mein toota jo dono ke trusted hone ke baare mein tha. Ek broken "if-both-trusted-then-equal" rule fix karne ke liye exactly do moves hain: ek side ko not trusted banao (chillao "apna number kaato!" — invalidate) ya unhe equal banao (chillao "apna 10 karo!" — update). Agar tum baar baar score karte raho, "kaato" ek baar bolna sasta hai. Agar tumhare dost ko naya score jaise hi tum likhte ho chahiye, naya number bolna sasta hai. Woh trade-off — magic nahi — isliye real chips invalidate choose karte hain lekin choice free nahi hai.

Connections

• Parent: Cache coherence problem · Hinglish: 5.4.14 Cache coherence problem (Hinglish)
• Write-through vs Write-back · MESI Protocol · Snooping vs Directory Coherence
• Memory Consistency Models · False Sharing · Bus Traffic & Scalability