Foundations — Cache coherence problem

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

Parent note ko padhne se pehle bhi, tumhare paas kuch ideas ka chhota stack hona chahiye. Neeche, har ek ko zero se build kiya gaya hai: plain meaning → picture → topic ko yeh kyun chahiye. Inhe is tarah order kiya gaya hai ki har ek pichle pe rest kare.

1. Main memory — ek akela shared source

Ise picture karo ek lambi numbered boxes ki shelf ke roop mein. Sab usi shelf ko point karte hain.

Topic ko yeh kyun chahiye: coherence ek box ki copies ke baare mein hai. Agar copy karne ke liye koi shared shelf hi na hoti, to disagree karne ki koi baat hi na hoti.

2. Address X — ek box ka label

Ise picture karo: ek specific box par chipka hua sticky label X likha; andar number 5 baitha hai.

Topic ko yeh kyun chahiye: poora coherence problem per address define hota hai. Do caches ka X ke baare mein disagree karna hi saara bug hai. X woh cheez hai jisi ki sabke paas copy hoti hai.

3. Core — ek worker jo reads aur writes karta hai

Ise picture karo: do log shared shelf ke paas khade hain, dono peek ya scribble karne ke liye free hain.

Topic ko yeh kyun chahiye: ek core ke saath sab cheez ka sirf ek copy hota hai aur koi disagreement possible nahi hai. Coherence problems us waqt janam leti hain jab tumhare paas do ya zyada cores hote hain.

4. Cache — private photocopy

Ise picture karo (upar ki figure): har core apna chhota notebook rakhta hai. Red box shared shelf dikhata hai; black notebooks private copies hain. Notice karo ki dono notebooks usi box X ki copy rakh sakti hain.

Topic ko yeh kyun chahiye: "private" hi poora villain hai. Agar caches shared hote, to sab ek hi copy padhte aur hamesha agree karte. Kyunki har ek private hai, ek mein ki gayi change doosron ko invisible rahti hai.

5. Cache line — woh unit jo copy hoti hai

Ise picture karo: ek word photocopy karne ki jagah, tum poora page photocopy karte ho. X us page par kahin rehta hai.

Topic ko yeh kyun chahiye: parent "the line" ko invalidate karne ki baat karta hai, aur baad ke topics jaise False Sharing tabhi sense karte hain jab tumhe pata ho ki copy ek chunk hai, single box nahi.

6. Read aur Write — do actions

Ise picture karo: read = tumhari aankhein ek number tumhare notebook mein copy karti hain. Write = tumhara pen ek naya number scribble karta hai.

Topic ko yeh kyun chahiye: coherence bugs specifically tab appear hote hain jab ek core ka write baad mein doosre core ke read ko nahi dikhai deta. Poori problem ek write/read mismatch hai.

7. Stale data — ek copy jo ab truth se match nahi karti

Ise picture karo: tumhara notebook 5 kehta hai, lekin real current answer 10 hai. Tumhara 5 stale hai.

Topic ko yeh kyun chahiye: "stale" failure ka ek-word naam hai. Coherence exist karta hai taaki reads stale copies return karne se bache.

8. Valid — kya meri copy trustworthy hai?

Ise picture karo: tumhare notebook page par ek chhota tick ✓ matlab "tum ise trust kar sakte ho," ya cross ✗ matlab "trust mat karo — jaao shelf se re-copy karo."

Topic ko yeh kyun chahiye: parent ka mini-derivation poora ${\text{Valid}}_i(X)$ ke terms mein likha gaya hai. Yeh woh switch bhi hai jo ek protocol flip karta hai: staleness fix karne ke liye tum ${\text{Valid}}_j(X)\leftarrow \text{false}$ set karte ho.

9. Notation cache_i(X) aur symbols $\forall$, $\wedge$, $\Rightarrow$

Parent apna invariant shorthand mein likhta hai. Yahan har symbol, words mein.

Topic ko yeh kyun chahiye: coherence invariant $\forall i,j:{\text{Valid}}_i(X)\wedge {\text{Valid}}_j(X)\Rightarrow {\text{cache}}_i(X)={\text{cache}}_j(X)$ ab plain English mein padhta hai: "Cores ke har pair ke liye, agar dono X ki trusted copy rakhte hain, woh copies equal honi chahiye." Yahan koi bhi symbol un-earned nahi hai.

10. Write-back vs write-through — write kahan jaati hai

Ise picture karo (figure): write-through har write par shelf ko seedha arrow bhejta hai; write-back change ko notebook mein trapped rakhta hai (dirty mark, red) baad ke liye.

Topic ko yeh kyun chahiye: parent ka steel-man argument ("kya write-through ise fix nahi karta?") isi distinction par turn karta hai. Write-through memory ko fresh rakhta hai lekin doosre core ke cache ko kabhi touch nahi karta — toh coherence phir bhi break hoti hai. Detail Write-through vs Write-back mein hai.

11. Bus — shared wire jis par cores baat karte hain

Ise picture karo (figure): ek single red horizontal wire; saare notebooks aur shelf us par lage hain. Jab Core A "invalidate X!" chillata hai, har doosra core use sun leta hai.

Topic ko yeh kyun chahiye: har coherence cure ek message hai. "Invalidate" aur "update" woh cheezein hain jo ek core bus par kehta hai taaki doosre react kar sakein. Kyunki sab sab kuch sunte hain, ise snooping kehte hain — dekho Snooping vs Directory Coherence. In messages ko count karna exactly Bus Traffic & Scalability hai.

12. Invalidate vs Update — do cures

Ise picture karo: invalidate = "apna number cross out karo." Update = "sablog apna number 10 kar lo."

Topic ko yeh kyun chahiye: yeh do protocol families hain jinhe poora parent note build karta hai, aur MESI Protocol ka seed hai.

Prerequisite map

Equipment checklist

Self-test: kya tum bina dekhhe har ek ka jawab de sakte ho?

Connections

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