MESI - MOESI coherence protocols: Exercises — Hinglish deep dive

5.4.15 · D4 · Hardware › Memory Hierarchy & Caches › MESI - MOESI coherence protocols

Poore note mein actors hain cores C0, C1, C2, …, har ek ke paas ek private cache hai, aur sab ek shared bus watch kar rahe hain (dekho Snooping vs Directory-based protocols). Bus messages hain:

Paanch state letters (MESI mein chaar, MOESI mein paanch): Modified (sirf ek copy, dirty), Exclusive (sirf ek copy, clean), Shared (clean, doosre bhi rakh sakte hain), Invalid (koi valid data nahi), aur Owned (dirty aur possibly shared — sirf MOESI mein).

Level 1 — Recognition

Exercise 1.1

Har situation ke liye, woh ek MESI state batao jo match karti ho: (a) Line memory se match karti hai aur koi doosra cache isko nahi rakhta. (b) Line memory se alag hai aur yeh iska ek hi copy hai. (c) Line read-only hai aur kai caches mein ho sakti hai. (d) Line mein koi valid data nahi hai.

Recall Solution

(a) E — Exclusive: sirf ek copy + clean. (b) M — Modified: sirf ek copy + dirty. (c) S — Shared: clean + possibly-shared. (d) I — Invalid.

Trick yeh hai: do yes/no questions sab decide karti hain — Kya main akela copy hoon? aur Kya main dirty hoon? Table:

	Only copy	Others may hold
Clean	E	S
Dirty	M	(MOESI ka O chahiye)

Exercise 1.2

MOESI mein, kaun sa ek state hai jiska matlab hai dirty aur doosre caches ke saath shared ho sakta hai?

Recall Solution

O — Owned. Yeh woh empty "dirty + shared" cell fill karta hai jo MESI express nahi kar sakta. Owner dirty data rakhta hai, ise readers ko cache-to-cache forward karta hai, aur memory mein sirf tab write back karta hai jab finally evict hota hai. Dekho MOESI in AMD.

Level 2 — Application

Exercise 2.1

Line C0 mein E state mein hai. C0 ek store (write) karta hai. Bus par kaun sa message jaayega, aur naya state kya hoga?

Recall Solution

Koi message nahi (zero bus traffic). Naya state M. C0 ek clean line ka sole holder hai, isliye kisi doosre cache ko invalidate karne ki zaroorat nahi — SWMR already satisfy hai. Yeh silent E→M upgrade hi E state rakhne ka fayda hai.

Exercise 2.2

Line C0 mein S state mein hai. C0 ek store karta hai. Kaun sa message, aur naya state kya hoga?

Recall Solution

Message BusRdX (Read-for-Ownership). Naya state M. Kyunki S ka matlab hai doosre bhi clean copies rakh sakte hain, C0 ko unhe invalidate karna hoga (sab → I ho jaate hain) before it becomes the single writer. Phir S→M.

Exercise 2.3

Line C0 mein M state mein hai (MESI). C0 C1 se ek BusRd snoop karta hai. C0 ko kya karna chahiye, aur C0 aur C1 kahan end up karenge?

Recall Solution

C0 ko dirty data memory mein write back karna hoga, value supply karni hogi, aur M→S transition karna hoga. C1 S mein end hoga. Write back kyun? BusRd ka matlab hai C1 bhi ek copy rakhega, isliye C0 ab exclusive owner nahi reh sakta — lekin memory stale hai, isliye do clean sharers exist hone se pehle fresh value push down karni hogi.

Exercise 2.4

Exercise 2.3 jaisa hi lekin MOESI mein. Kya badlega?

Recall Solution

C0 M→O transition karta hai (M→S nahi), data directly C1 ko forward karta hai (cache-to-cache), aur memory nahi likhta. C1 S mein end hota hai. C0 owner rehta hai aur eventual write-back ke liye responsible akela cache hota hai. O ka yahi poora point hai: memory round-trip skip karo.

Level 3 — Analysis

Exercise 3.1 (MESI full trace)

Address X, memory mein initial value = 5. Sab caches I se shuru hote hain. Har step ke baad states trace karo:

C0 reads X
C1 reads X
C2 reads X
C1 writes X = 9
C0 reads X

Har step ke baad (C0, C1, C2) report karo aur issue hue BusRdX messages count karo.

Recall Solution

Step	Action	Bus msg	C0	C1	C2
1	C0 read	BusRd	E	I	I
2	C1 read	BusRd	S	S	I
3	C2 read	BusRd	S	S	S
4	C1 write	BusRdX	I	M	I
5	C0 read	BusRd	S	S	I

Step 1: koi doosra holder nahi → C0 E mein land karta hai.
Step 2: ek aur copy aati hai → dono S ho jaate hain (C0 E→S karta hai).
Step 3: teen clean sharers, sab S.
Step 4: C1 S se store karta hai → BusRdX, C0 aur C2 invalidate, phir S→M.
Step 5: C0 read-miss → BusRd; C1 (M mein) ko write back karke M→S jaana hoga; C0 S mein land karta hai.

BusRdX count = 1 (sirf step 4).

Exercise 3.2 (MOESI same trace)

Exercise 3.1 ko MOESI mein repeat karo. Step 5 ke baad states kya hain, aur poore trace mein kitne memory writes hote hain? MESI se compare karo.

Recall Solution

Steps 1–4 same hain (C1 = M, C0 = C2 = I). Step 5: C0 read-miss → BusRd. C1 M mein hai → M→O jaata hai, value 9 forward karta hai C0 ko, memory write nahi hota. C0 S mein land karta hai. Final: C0 = S, C1 = O, C2 = I.

MOESI mein memory writes = 0 (data C1 ke O state mein dirty rehta hai jab tak evict na ho). MESI mein memory writes = 1 (step 5 ka M→S write-back). MOESI ne cache-to-cache forwarding se ek memory round-trip bachaya. Dekho Write-back vs Write-through caches — memory writes avoid karna hi poora game hai.

Level 4 — Synthesis

Exercise 4.1

Do threads aise counters increment karte hain jo same cache line mein hote hain (dekho False Sharing). C0 counter A likhta hai, C1 counter B likhta hai, alternating 4 baar each (C0, C1, C0, C1, …), sab I se shuru hokar. MESI use karte hue, in 8 writes mein total kitne BusRdX messages fire hote hain? Assume karo line uncached se shuru hoti hai.

Recall Solution

Bhale hi A aur B alag variables hain, woh ek line mein rehte hain, isliye writes ownership ping-pong karti hain.

Write 1 (C0): line I hai → BusRdX (fetch + own) → C0 = M. (1)
Write 2 (C1): C0 M mein hai → C1 BusRdX issue karta hai, C0 write back + →I, C1 = M. (2)
Write 3 (C0): BusRdX → C1 write back + →I, C0 = M. (3)
… pattern repeat hota hai: 8 mein se har ek write ek BusRdX issue karta hai.

Total BusRdX = 8.

Yeh false sharing hai: logically koi data share nahi ho raha, phir bhi line har write par bounce karti hai. Fix yeh hai ki A aur B ko alag cache lines par pad karo taaki har ek privately M/E mein rahe.

Exercise 4.2

Exercise 4.1 ke 8-write ping-pong lo. MESI mein har ownership transfer ek memory write-back force karta hai (losing M cache ko flush karna hota hai). MOESI mein, dirty data cache-to-cache forward hota hai. Lekin yahan requester writes (BusRdX) karta hai, reads (BusRd) nahi. Kya MOESI ka O state is false-sharing pattern mein help karta hai? Explain karo.

Recall Solution

Nahi — O yahan help nahi karta. O state sirf BusRd (read) requests ke liye faydemand hai, jahan owner dirty data forward karke owner bana reh sakta hai. Lekin yeh pattern pure BusRdX (writes) ka hai, aur ek BusRdX pichle owner ko completely invalidate kar deta hai — koi "shared dirty" outcome preserve karne ko nahi bachta. Har write phir bhi exclusive ownership transfer karta hai.

MOESI phir bhi dirty bytes memory ke bajaye cache-to-cache forward kar sakta hai, latency bachata hai, lekin ownership transfers ki sankhya unchanged rehti hai aur line phir bhi 8 baar bounce karti hai. Asli ilaaj structural hai (padding), protocol choice nahi.

Level 5 — Mastery

Exercise 5.1 (state counting)

MESI ko apni states encode karne ke liye har line mein enough bits chahiye; MOESI ek aur state add karta hai. (a) MESI aur (b) MOESI ke liye minimum bits per cache line compute karo, aur jump explain karo.

Recall Solution

State field ko $N$ states ke liye $⌈ lo g_{2} N ⌉$ bits chahiye. (a) MESI: $N = 4 \Rightarrow ⌈ lo g_{2} 4 ⌉ = 2$ bits. (b) MOESI: $N = 5 \Rightarrow ⌈ lo g_{2} 5 ⌉ = 3$ bits. 4 se 5 states jaane par ek power-of-two boundary cross hoti hai ( $2^{2} = 4 < 5 \leq 8 = 2^{3}$ ), isliye sirf ek state add hone par bhi ek extra bit force hoti hai. 3 bits se tum 8 tak states encode kar sakte ho (MESIF-style extras ke liye bhi jagah hai).

Exercise 5.2 (amortised cost argument)

Ek shared, mostly-read counter $R$ baar read hota hai aur $W$ baar kuch cores ke dwara likha jaata hai, hamesha MOESI mein. Maano har remote owner se read ki cost $c$ (cache-to-cache) hai aur har memory write-back (sirf eviction par) ki cost $m$ hai, jahan $m > c$ . Agar owning line exactly ek baar bilkul end mein evict hoti hai, total data-movement cost ko $R$ ke function ke roop mein likho, aur ek hypothetical write-through scheme se compare karo jahan har $W$ writes mein har ek ko memory mein $m$ cost aati hai.

Recall Solution

MOESI: owner $R$ readers mein se har ek ko cache-to-cache forward karta hai ( $R \cdot c$ ) aur final eviction par ek write-back karta hai ( $m$ ). Cores ke beech writes locally owner ki dirty copy update karti hain (owned rehte hue koi memory cost nahi). Total: $Cost_{MOESI} = R c + m .$ Write-through: har write memory tak pahunchti hai: $Cost_{WT} = W m (+ R c reads ke liye) .$ Kyunki $m > c$ aur typically $W ≫ 1$ , MOESI ka single deferred write-back savings dominate karta hai: yeh $W$ memory writes ko 1 se replace kar deta hai. Forwarding term $R c$ dono mein common hai, isliye net MOESI advantage hai $Δ = W m - m = (W - 1) m .$ Yahi reason hai kyun write-back + ownership write-heavy sharing mein write-through ko beat karta hai — dekho Write-back vs Write-through caches.

Exercise 5.3 (design synthesis)

Tumhe bataya jaata hai ki ek workload mein (i) bohot saare uncontended per-core locks hain aur (ii) cores ke beech forward hone wala hot read-shared dirty data hai. Kaun se do state letters is workload ke liye sabse zyada valuable hain, aur kyun? Kaun sa real vendor lineage best match karta hai?

Recall Solution

E lock case handle karta hai: ek uncontended lock read hoti hai (→ E) phir likhti hai (E→M silently, zero bus traffic). E ke bina, har lock acquisition broadcast karta.
O hot-dirty-shared case handle karta hai: owner har BusRd par dirty data cache-to-cache forward karta hai, memory writes avoid karke. Dono matter karte hain, isliye MOESI design best fit hai — AMD ke lineage se match karta hai. (Intel ka MESIF iske bajaye Forward add karta hai taaki clean sharers mein se ek single responder choose ho sake — yeh ek alag optimisation hai jo dirty forwarding ke bajaye redundant clean-copy responses reduce karne par focused hai.)

Wrap-up recall

Recall One-line answers (cover them!)

Bits per line: MESI vs MOESI? ::: 2 vs 3.
Kaun sa state free (silent) writes deta hai? ::: E, E→M ke through.
Kaun sa message doosron ko invalidate karta hai? ::: BusRdX.
Kya MOESI false sharing fix karta hai? ::: Nahi — yeh ek data-layout problem hai.
MOESI mein BusRd par, ek M line __ ban jaati hai aur data forward karti hai. ::: O (Owned).
Ex 3.1 (MESI) vs Ex 3.2 (MOESI) mein memory writes? ::: 1 vs 0.