5.4.14 · D3Cache coherence problem
Tumne coherence ka problem parent note Cache coherence problem mein dekha hai. Wahaan tumne ek failure table aur teen example sketches dekhe the. Yeh page sketching ka ulta karta hai: yeh har tarah ki situation list karta hai jo coherence problem tumhare saamne rakh sakti hai, phir har ek ko last message count tak work out karta hai — taaki koi bhi case aisa na rahe jo tumne pehle na dekha ho.
Shuru karne se pehle, vocabulary dobara seedhi kar lete hain taaki koi bhi symbol bina explanation ke andar na ghus aaye.
Definition Jo words hum use karenge (sab yahan re-define hain)
Line (ya block) — memory ka ek fixed-size chunk (maano 64 bytes) jo ek cache ek unit ke roop mein store karta hai. Cache kabhi "sirf variable X" hold nahi karta; woh poori line hold karta hai jisme X rehta hai.Valid copy — ek cached line jiska stored value abhi bhi true logical value ke barabar hai. Agar yeh drift kar gayi, toh yeh stale hai.Dirty line — ek line jis par kisi core ne likha, isliye uski cache mein main memory se zyada naya value hai. (Yeh word sirf write-back caches ke liye matter karta hai, jo writes ko memory tak push karne mein delay karte hain.)Bus event — ek message jo shared wire par travel karna padta hai jo cores ko connect karta hai: ek invalidate, ek update broadcast, ek read-miss fetch, ya ek write-back flush. Hum inhe count karte hain kyunki yahi coherence ki cost hai — dekho Bus Traffic & Scalability .Write-invalidate — write ke baad, baaki sabhi caches ko batao "is line ki tumhari copy ab invalid hai."Write-update — write ke baad, har us doosri cache ko naya value bhejo jo woh line hold kar rahi hai.
Neeche sab kuch bas yahi words hain jo alag-alag starting conditions par apply hote hain.
Coherence ke outcomes depend karte hain line kiske paas hai , kya operation ho raha hai , kaunsa protocol coherence enforce karta hai, aur memory kab refresh hoti hai (write-through vs write-back). Yeh hai us case-classes ka poora grid jo yeh topic produce kar sakta hai:
#
Case class
Jis variable par stress hai
Covered by
C1
Single writer, doosri caches stale, koi protocol nahi
baseline bug
Ex 1
C2
Write-invalidate coherence restore karta hai
invalidate ka ilaaj
Ex 2
C3
Write-update coherence restore karta hai
update ka ilaaj
Ex 3
C4
Repeated writes , ek writer (invalidate favoured)write-run length
Ex 4
C5
Producer/consumer , har write ke baad read (update favoured)sharing tightness
Ex 5
C6
Write-through vs write-back : kya memory correct hai?memory kab refresh hoti hai
Ex 6
C7
Degenerate: sirf ek core line cache karta hai (koi sharer nahi)zero other copies
Ex 7
C8
Degenerate: dono cores sirf read karte hain , koi nahi likhtazero writes
Ex 8
C9
Limiting case: N sharers , ek write — traffic kaisa scale karta haiN ke saath scaling
Ex 9
C10
Real-world word problem + exam twist (false sharing)alag addresses, same line
Ex 10
Matrix ko aise padho: rows C1–C3 teen protocol behaviours hain; C4–C5 batate hain kab kaunsa protocol jeetta hai; C6 memory-freshness axis ko isolate karta hai; C7–C8 degenerate (kuch fix nahi karna) cases hain; C9 sharer count ko limit tak push karta hai; C10 woh sneaky wala hai.
Poore note mein base scenario hai: variable X memory mein 5 se shuru hota hai , cores hain Core A aur Core B (plus zyada jab stated ho), caches write-back hain jab tak row kuch aur na kahe.
Worked example Example 1 — C1: koi protocol nahi, raw bugCore A aur B dono X=5 cache karte hain. A X=10 execute karta hai (write-back). Phir B X read karta hai. B kya value dekhta hai?
Forecast: B ki value aur memory fresh hai ya nahi, yeh guess karo, aage padhne se pehle .
A sirf apni line mein X=10 likhta hai. Yeh step kyun? Koi protocol na hone par write sirf ek cache ko touch karta hai — A ka. Kuch B ko nahi batata.A ki line ab dirty hai; memory abhi bhi 5 hold karti hai. Yeh step kyun? write-back matlab naya value A ki cache mein rehta hai jab tak eviction nahi hoti; usne flush nahi kiya.B reads X → B ki copy abhi bhi valid mark hai → apna 5 return karta hai. Yeh step kyun? ek read local copy use karta hai jab bhi woh sochta hai ki woh valid hai, aur kisi ne use invalidate nahi kiya.
Answer: B reads 5 (stale); memory = 5 (A ke comparison mein bhi stale).
Verify: Do bugs, jaise parent ne promise kiya tha — cache-vs-cache (B ka 5 ≠ A ka 10) aur memory-vs-cache (memory ka 5 ≠ A ka 10). Parent ke forecast box se consistent. ✅
Worked example Example 2 — C2: write-invalidate ise theek karta haiSame start. Ab system write-invalidate chalata hai. A X=10 likhta hai, phir B read karta hai.
Forecast: kitne bus events, aur B aakhir mein kya read karta hai?
A writes X=10 → ek invalidate broadcast karta hai. Yeh step kyun? invalidate ka rule: write par, har doosri copy ko khatam karo. Yeh hai 1 bus event.B apni line Invalid mark karta hai. Yeh step kyun? invalidated line par ab trust nahi kar sakte; future read fetch karne jaayegi.B reads X → uski line Invalid hai → read miss → fresh value (10) fetch karta hai. Yeh step kyun? forced miss hi poora trick hai — silent staleness ek loud fetch ban gayi. Yeh hai 2nd bus event.
Answer: B reads 10 (coherent). Bus events = 2 (1 invalidate + 1 read miss).
Verify: Parent ke Example 1 (coherent) aur Example 2 ke 2 ke count se match karta hai ek single write ke liye. ✅
Worked example Example 3 — C3: write-update ise theek karta haiSame start. Ab write-update . A X=10 likhta hai, phir B read karta hai.
Forecast: message count aur B ki value?
A writes X=10 → naya value 10 sabhi sharers ko broadcast karta hai. Yeh step kyun? update ka rule: copies ko khatam mat karo, unhe refresh karo. 1 bus event.B ki line in-place 10 se overwrite hoti hai, valid rehti hai. Yeh step kyun? update copy ko zinda rakhta hai, isliye future miss ki zarurat nahi.B reads X → local hit → 10 return karta hai. Yeh step kyun? copy already fresh hai; read 0 bus events lagata hai.
Answer: B reads 10 (coherent). Bus events = 1 (1 update, read ek free hit hai).
Verify: Ek single write-then-read ke liye, update (1) invalidate (2) ko beat karta hai. Yahi producer/consumer advantage hai jo parent ne hint kiya tha, apne smallest form mein. ✅
Worked example Example 4 — C4: repeated writes, invalidate jeetta haiEk sharer (B). Core A teen baar ek ke baad ek X likhta hai, phir B ek baar read karta hai. Har protocol ke liye bus events count karo.
Forecast: kaunsa protocol sasta hai, aur kitne se?
Invalidate, write #1: A ek invalidate broadcast karta hai → B invalid, A ab line exclusively ke paas hai. 1 event.Invalidate, writes #2 aur #3: A already akela owner hai → kill karne ke liye koi aur copy nahi → 0 events. Yeh step kyun? jab tum akele owner ho, notify karne ke liye koi nahi — isliye runs saste hote hain. (Dekho MESI Protocol "Exclusive/Modified" states ke liye jo ownership record karte hain.)Invalidate, B ki read: B invalid hai → read miss → 1 event. Invalidate total = 2. Update, writes #1–#3: har write ko newest value broadcast karna padta hai → 3 events. B ke paas already line hai, isliye uski read = 0. Update total = 3.
Answer: Invalidate = 2 events, Update = 3 events. Invalidate jeetha.
Verify: Parent ke Example 2 se match karta hai (2 vs 3). Gap write-run length ke saath badhta hai — dekho Bus Traffic & Scalability . ✅
Worked example Example 5 — C5: producer/consumer, update jeetha haiA ek baar X likhta hai, phir B use turant read karta hai, aur yeh ping-pong repeat hota hai. Ek write-then-read round ke events count karo.
Forecast: Example 4 ka winner paltega?
Update: A likhta hai → 1 update broadcast → B ki copy ab fresh hai. B reads → local hit, 0. Update total = 1. Invalidate: A likhta hai → 1 invalidate → B invalid. B reads → miss → fetch, 1. Invalidate total = 2.
Answer: Update = 1, Invalidate = 2. Update jeetha.
Verify: Parent ke Example 3 se same numbers. Saath mein Ex 4 aur Ex 5 prove karte hain ki koi bhi protocol universally best nahi — traffic pattern decide karta hai. ✅
Worked example Example 6 — C6: kyamemory correct hai? Write-through vs write-back
Memory-freshness axis ko isolate karo. A X=10 likhta hai. Turant baad (koi eviction nahi, memory par abhi koi protocol nahi), pucho: har write policy ke under main memory mein kya hai? Dekho Write-through vs Write-back .
Forecast: kaunsi policy memory ko fresh rakhti hai?
Write-through: har write memory mein turant push hoti hai → memory = 10 immediately. Yeh step kyun? yahi write-through ki definition hai.Write-back: write A ki cache mein dirty line ke roop mein rehti hai; eviction tak memory untouched hai → memory = 5. Yeh step kyun? write-back freshness ki trade-off leta hai kam memory trips ke liye.Lekin kya doosri caches update hoti hain? Dono policies mein, B ki cached copy untouched rehti hai jab tak koi coherence protocol act nahi karta. Yeh step kyun? write policy memory-vs-cache gap ke baare mein hai; coherence cache-vs-cache gap ke baare mein hai — do independent axes.
Answer: write-through → memory = 10; write-back → memory = 5. Koi bhi B ki stale copy fix nahi karta.
Verify: Yeh parent ka steel-man numeric ban gaya: write-through memory fix karta hai (5→10) lekin B abhi bhi apni stale copy read karta hai. ✅
Worked example Example 7 — C7 (degenerate): sirf ek core line cache karta haiCore A akela core hai jiske paas X cached hai. A X=10 likhta hai. Invalidate ke under kitne coherence bus events?
Forecast: zero other sharers ke saath, kya koi coherence traffic zaroori hai?
A likhta hai → protocol doosre sharers dhundta hai → koi nahi milta. Yeh step kyun? invariant tabhi threaten hota hai jab koi doosri valid copy exist kare; yahan nahi hai.Koi invalidate nahi bheja jaata. Coherence bus events = 0.
Answer: 0 coherence events. (A ka memory write-back baad mein eviction par ho sakta hai, lekin yeh write-policy axis hai, coherence nahi.)
Verify: Invalidate cost formula "invalidate cost = 1 if N ≥ 1 else 0" mein N (doosre sharers ki sankhya) = 0 set karo. N=0 → 0. Degenerate case invariant ki prediction ke anusaar behave karta hai. ✅
Worked example Example 8 — C8 (degenerate): sirf reads, koi write nahiA aur B dono X cache karte hain aur sirf read karte hain. Kabhi bhi kitne coherence events?
Forecast: kya do read-only copies kabhi incoherent ho sakti hain?
Koi write nahi hota → koi copy kabhi change nahi hoti. Yeh step kyun? incoherence sirf write se create hoti hai (cache_i(X) := new). Koi write nahi, koi drift nahi.Dono copies hamesha valid aur equal rehti hain. Coherence events = 0.
Answer: 0 events; shared read-only data trivially coherent hai.
Verify: Yeh MESI Protocol mein safe "Shared" state hai — multiple readers zero traffic ke saath coexist karte hain. Confirm karta hai ki writes hi akele trigger hain. ✅
Worked example Example 9 — C9 (limiting): N sharers tak scalingEk line N cores ke paas cached (valid) hai. Unme se ek ek baar likhta hai. Har protocol ke liye N ke function ke roop mein coherence events do, phir N = 1, 4, 64 plug in karo.
Forecast: kaunse protocol ki cost N ke saath badhti hai?
Invalidate: writer ek broadcast invalidate bhejta hai; har doosra sharer apni copy drop karta hai. Snooping ke saath (ek shared bus, dekho Snooping vs Directory Coherence ) yeh N se independent 1 event hai. Yeh step kyun? ek bus broadcast sabhi ek saath sunते hain.Update: writer ko (N−1) doosre sharers mein se har ek ko value deliver karni padti hai. Cost N−1 ke roop mein badhti hai. Yeh step kyun? har sharer ko actual bytes chahiye, sirf "you're stale" flag nahi.Plug in: invalidate → 1, 1, 1. Update → N−1 = 0, 3, 63.
Answer: invalidate = 1 sabhi N ke liye; update = 0 (N=1), 3 (N=4), 63 (N=64).
Verify: N→large hone par, update traffic → ∞ jabki invalidate flat rehta hai — isliye bade multicores invalidate use karte hain. Dekho Bus Traffic & Scalability . ✅
Worked example Example 10 — C10: real-world word problem + exam twist (false sharing)Word problem: Ek line mein do independent 4-byte counters packed hain: hitsA bytes 0–3 par aur hitsB bytes 4–7 par — ek 8-byte line . Core A sirf hitsA likhta hai; Core B sirf hitsB likhta hai. Yeh ek doosre ke counter ko kabhi nahi touch karte. Dono line cached rakhte hain, write-invalidate protocol. Core A hitsA 10 baar likhta hai; interleaved, Core B hitsB 10 baar likhta hai, alternating A,B,A,B,… Invalidate events count karo.
Forecast: kyunki A aur B alag counters touch karte hain, guess karo "0 conflicts." Phir aage padho — yahi twist hai.
Coherence poori lines track karta hai, bytes nahi. Yeh step kyun? valid/invalid flag line per rehta hai. Kisi bhi byte par write poori line ko doosri caches mein invalidate karta hai.A writes hitsA → B ki line ki copy invalidate karta hai (chahe B sirf hitsB ki parwah karta ho). 1 event. Yeh step kyun? protocol nahi bata sakta ki writes disjoint bytes par hain.B phir hitsB likhta hai → lekin B ki line ab Invalid hai → read-for-ownership miss (1) → write → A ki copy invalidate karta hai (1). A ki agli write cycle repeat karti hai. Alternating 20 writes mein se har ek coherence traffic trigger karta hai jo "karni nahi chahiye thi."Count: pehla A-write B ko invalidate karta hai (1). Har subsequent write line ko stolen pata hai, isliye ek miss + ek invalidate lagta hai. Roughly 2 events per write pehle ke baad , ≈ 1 + 2·19 = 39 events — jabki 0 hote agar dono counters alag lines mein hote.
Answer: ≈39 bus events aisi data se jo kabhi truly conflict nahi karti. Yeh hai False Sharing — exam twist. Fix: counters ko alag cache lines mein pad karo → traffic ~0 ho jaata hai.
Verify: Sanity: A aur B alag lines mein hone par, har core apni line exclusively own karta hai (Ex 7 logic) → 0 coherence events. 39-vs-0 gap poori tarah line granularity ka artifact hai, real sharing nahi. ✅
Figure ek write ke liye coherence traffic plot karta hai jaise sharers ki sankhya N Pale-yellow flat line write-invalidate hai (hamesha 1 broadcast). Chalk-pink rising line write-update hai (N − 1 N = 2 N = 64 Wahi crossing poora argument hai ki real CPUs invalidate-based kyun hote hain.
Recall Kaunsa protocol jeetha hai — quick self-testEk tight producer/consumer loop (write, phir doosra core turant read karta hai, repeat) — invalidate ya update? ::: Update — yeh read miss avoid karta hai (Ex 5).
Ek akela core same line 100 baar likhta hai pehle koi read kare — kaunsa sasta hai? ::: Invalidate — ek invalidate phir silent ownership; update 100 baar broadcast karta (Ex 4).
Ek line mein do counters, dono cores likhte hain — kya problem hai, aur kya iska real data conflict se koi lena dena hai? ::: False sharing; koi real conflict nahi — coherence poori lines track karta hai, bytes nahi (Ex 10).
Write-back ke saath koi protocol nahi, A writes X=10 phir B reads: B ki value aur memory ki value? ::: B reads stale 5; memory bhi 5 hai (Ex 1).
Mnemonic Matrix ek breath mein"Writes coherence cause karte hain; reads aur akele owners free hain; invalidate scale karta hai, update ping-pong karta hai, aur lines — bytes nahi — unit hain."
