Cache coherence at scale (directory-based): Visual walkthrough

6.1.6 · D2 · Hardware › Parallelism & Multicore › Cache coherence at scale (directory-based)

Hum yeh bhi dekhenge ki un bits ki zaroorat kyun hai: agar hum sharer list hata dein, toh kya toot jaata hai.

Step 1 — Hum track kya kar rahe hain? Blocks aur cores

KYA. Machine ko do rows of boxes ki tarah draw karo. Neeche ki row memory hai, jo equal chunks mein split hai jinhein cache blocks (ya "cache lines") kehte hain: yeh sabse chhoti unit of data hai jo ek cache move karta hai, typically 64 bytes. Upar ki row cores hain, har ek ke paas apna chhota cache hai.

KYUN. Bits count karne se pehle humein un do cheezein name karni hain jinpar directory size depend karti hai. Har cheez scale hoti hai kitne blocks exist hain aur kitne cores unhe chahh sakte hain — inn dono se.

PICTURE. Figure dekho. Har memory block ek lavender tile hai. Blocks ki count ko $M$ aur cores ki count ko $N$ label karte hain.

M

kya hai?

Memory mein cache blocks ki count (memory size ÷ block size).

N

kya hai?

Cores ki count, jinmein se har ek ke paas ek private cache hai.

Step 2 — Har block ke liye ek entry: ek single entry ko kya answer karna chahiye?

KYA. Ek memory block $B$ ko zoom in karo. Pucho: sabke copies ko consistent rakhne ke liye, hardware ko $B$ ke baare mein abhi kya jaanna chahiye?

KYUN. Poori cost hai (ek entry) × M. Toh design problem shrink ho jaati hai ek entry design karne tak. Agar hum ise bahut bada banate hain, toh $M$ times woh bhaari cost pay karni padegi. Isliye hum single bits ke upar itna focus karte hain.

PICTURE. Figure ek block dikhata hai aur uske upar do questions float kar rahe hain: "What state?" aur "Who has it?" Yeh wohi do facts hain jinpar coherence protocol kabhi bhi kaam karta hai.

Step 3 — "What state?" ka answer encode karna: 2 bits

KYA. State ke exactly teen possibilities hain. Unhe enumerate karo, phir count karo ki teen cheezein naam karne ke liye kitne bits chahiye.

KYUN. $k$ distinct labels mein se ek store karne ke liye $⌈ lo g_{2} k ⌉$ bits chahiye, kyunki har bit labels ki count double kar deta hai (1 bit → 2 labels, 2 bits → 4 labels). Hum $lo g_{2}$ use karte hain aur kuch nahi kyunki bits binary hain: sawaal "kitne yes/no switches itne saare options naam kar sakte hain?" wahi $lo g_{2}$ hai.

PICTURE. Teen coral chips — Uncached, Shared, Modified — aur har ek par ek 2-bit code. Do bits se char codes milte hain; teen states fit ho jaati hain (ek code spare rehta hai).

State ke liye 1 bit kyun nahi?

1 bit sirf 2 cheezein naam kar sakta hai; hamare paas 3 states hain, isliye

lo g_{2} 3

ko round up karke 2 karte hain.

Step 4 — "Who has it?" ka answer encode karna: pehle naive tarika try karo

KYA. Pehli koshish: sharers ke IDs ek list ke roop mein store karo. Har core ID ko $lo g_{2} N$ bits chahiye ( $N$ cores mein se ek ko naam do). Agar saare $N$ cores share kar sakte hain, toh ek poori list ki cost $N \times lo g_{2} N$ bits hai.

KYUN. Hum yeh isliye try karte hain kyunki jab few cores share karte hain toh yeh compact lagta hai. Isse fail hote dekhna sikhata hai ki real design (Step 5) kyun exist karta hai.

PICTURE. Figure ek Shared block dikhata hai jisme 3 IDs numbers ke roop mein stored hain (001, 111, 1001), aur ek warning: jab saare 64 cores share karte hain, toh list $64 \times 6$ bits tak explode ho jaati hai — plain bit per core se bhi worse.

Step 5 — "Who has it?" encode karne ka winning tarika: har core ke liye ek bit

KYA. List ko ek sharer bit-vector se replace karo: $N$ bits ki ek row, bit $i$ = 1 agar core $i$ ek copy rakhta hai, 0 otherwise.

KYUN. Fixed width ( $N$ bits, hamesha), aur yeh har protocol question ka ek nazar mein jawab deta hai: "invalidate kise karna hai?" = "kaunse bits 1 hain?". Koi length surprise nahi. Isliye real full-map directories ise use karti hain.

PICTURE. Ek 64-slot ribbon. Cores 0, 2 lit (bits set) → Shared with Sharers ${0, 2}$ . Neeche, wohi ribbon ek single bit lit ke saath → Modified, aur woh ek set bit wahi owner hai.

Modified hone par full-map vector mein owner kahan stored hota hai?

Kahin extra nahi — woh single set bit hi owner hai.

Step 6 — Ek entry assemble karo, phir $M$ se multiply karo

KYA. Step 3 aur Step 5 stack karo: ek entry = 2 state bits + N vector bits = $2 + N$ bits. Har block ke liye ek entry hai, aur $M$ blocks hain.

KYUN. Yeh final composition hai. Directory bas $M$ identical rows hain, har ek $2 + N$ wide — bits ka ek rectangle. Uska area hai width × height.

PICTURE. Ek grid: $M$ rows tall, har row ek 2-bit coral state chunk aur ek $N$ -bit lavender vector chunk mein split. Total area annotated as $M (2 + N)$ .

Step 7 — Parent ke numbers plug in karo (aur scale feel karo)

KYA. $N = 64$ , $M = 16 M = 16, 777, 216$ blocks use karo.

KYUN. Jo formula evaluate nahi kar sakte woh sirf ek fog hai. Hum ise us 132 MB par utaarte hain jo parent claim karta hai, aur dekhte hain ki megabytes kahan se aa rahe hain.

PICTURE. Ek bar: 2 state bits ek sliver hain; 64 vector bits har entry mein dominate karte hain. Overhead almost entirely "har block ke liye, har core ke liye ek bit" hai.

~97% directory bits kahan jaate hain?

N

-bit sharer vector mein — har block ke liye, har core ke liye ek bit.

Step 8 — Degenerate cases (koi bhi scenario bina draw kiye mat chhodna)

KYA. Formula ko uske edges tak push karo taaki reader ko kuch surprise na kare.

KYUN. Ek formula ko apne extremes survive karne chahiye; har extreme reveal karta hai ki ek bit kyun present hai.

PICTURE. Teen mini-panels: $N = 1$ , Uncached row, all-shared row.

Definition Edge cases explained

Single core, $N = 1$ . Entry = $2 + 1 = 3$ bits. Coherence trivial hai (disagree karne wala koi nahi), lekin vector ko phir bhi apna 1 bit chahiye "core 0 ke paas hai" aur "kisi ke paas nahi" mein distinguish karne ke liye. Formula 0 par collapse nahi karta.
Uncached block. State = Uncached, vector = all zeros ( $0000 \dots 0$ ). Row phir bhi exist karti hai aur phir bhi $2 + N$ bits cost karti hai — hum sharing ki possibility ke liye pay karte hain, chahe idle ho. Yeh full-map ki unavoidable price hai.
Saare cores share karte hain (hot read-only block). Vector = all ones. Yeh exactly woh case hai jis par Step 4 ki list encoding blow up ho gayi thi; bit-vector ise same fixed $N$ bits mein handle karta hai. Eventual write par, saare $N$ bits $N$ invalidations guide karte hain — yeh reason hai ki hum sharers ko exactly track karne par itna jor dete hain (inke peeche MESI/MOESI states dekhein).

Ek-picture summary

Upar ki sab cheez, compressed: " $M$ blocks, $N$ cores" se bit rectangle tak aur 132 MB number tak, har contribution colour-coded ke saath.

Recall Feynman retelling — ise apne words mein wapis bolo

Socho memory ek badi wall hai jisme $M$ chhote cubbies hain (har ek cache-block sized), aur tumhare paas $N$ roommates (cores) hain, har ek ki pocket mein woh kisi bhi cubby ke contents ki copy carry kar sakte hain. Chaos avoid karne ke liye jab koi copy change kare, hum ek clipboard rakhte hain jisme har cubby ke liye ek line hoti hai. Har line sirf do cheezein likhti hai: (1) ek tiny 3-way status — empty / shared-read-only / ek-insaan-ne-change-kiya — jisme check karne ke liye 2 boxes chahiye kyunki do yes/no boxes up to char cheezein label kar sakti hain aur hamare paas sirf teen hain; aur (2) $N$ tick-boxes ki ek row, har roommate ke liye ek, tick hoga agar woh roommate copy hold kar raha hai. Humne names likhne ki bajay tick-boxes choose kiye kyunki names lambe aur variable ho jaate hain, lekin tick-boxes hamesha same width ke hote hain aur turant batate hain ki change hone par sabko notify karna hai. Dhyan do ki changer ki identity free milti hai: agar "changed-it" mode mein sirf ek box ticked hai, toh woh ticked box hi changer hai. Toh ek line = $2 + N$ boxes, aur $M$ lines hain, total $M (2 + N)$ boxes milte hain. 16 million cubbies aur 64 roommates daalo aur har line 66 bits ki hai, aur poora clipboard 132 MB weighs karta hai — lagbhag saara woh $N$ roommate tick-boxes se. Wahi heaviness exactly woh reason hai kyun real machines cheat karte hain: clipboard ko NUMA homes mein split karo, ya sirf un cubbies ke liye lines rakho jinhein koi actually hold karta hai.

Yeh bhi dekho: Cache coherence protocols (MESI, MOESI) · NUMA architectures · Interconnect topologies · Memory consistency models · Cache line false sharing · wapas parent topic par.