Shared memory vs distributed memory: Visual walkthrough

6.1.5 · D2 · Hardware › Parallelism & Multicore › Shared memory vs distributed memory

Hum bilkul scratch se derive karenge ki ek parallel program total time kahan lagata hai, aur exactly kahan shared memory aur distributed memory apna hisaab chukate hain. Neeche har symbol pehle explain hota hai, tabhi use hota hai.

Prerequisites jin par hum depend karenge (har ek ka apna vault note hai): Cache Coherence Protocols, NUMA Architecture, Message Passing Interface (MPI), Interconnect Networks, False Sharing. Yeh parent topic ka visual companion hai.

Step 1 — "Ek memory access" asal mein kya hota hai?

KYA HOTA HAI. Ek processor (ise core kaho — ek worker jo instructions chalata hai) ko ek number chahiye jo kisi address par rakha hai. Ek address bas memory mein ek ghar ka number hai: "jo A location par stored hai, woh do". Use fetch karne ki time ko hum $T_{access}$ kehte hain.

YEH YAHAN KYU SHURU HUA. Har parallel program, andar se, laakhon memory accesses ka collection hota hai. Agar hum ek ki cost samajh lein, toh unhe add kar sakte hain. "Shared vs distributed" ki baat tab tak nahi ho sakti jab tak hum ek single fetch ki cost nahi jaante.

PICTURE — figure s01. Core baayein hai. Uski request ek seedhi ke (ladder) par daayin taraf travel karti hai: L1 cache (~1 ns) → L2/L3 (~10 ns) → main memory (~100 ns). Har seedha dabba daayin taraf jaake slow hota hai magar bada. Axis ka caption padhta hai "distance from core → slower, bigger", aur neeche text yaad dilata hai ki hit matlab pehle mil gaya (fast), miss matlab aur aage jaana pada (slow).

Figure — Shared memory vs distributed memory

Yeh ek weighted average hai: hum weighted average isliye lete hain kyunki access kabhi fast hoti hai, kabhi slow, aur hum expected (typical) cost jaanna chahte hain. Yahi woh ek tool hai jo jawab deta hai "ek access average mein kya cost karti hai?"

Step 2 — Ek doosra core add karo: hidden cost saamne aati hai

KYA HOTA HAI. Data ko do cores ko ek saath do. Dono apni-apni cache mein apni copy rakhte hain. Ab Core 1 value change karta hai. Core 2 ki copy usi waqt galat ho jaati hai — stale.

KYU. Yahi poori wajah hai ki shared memory mushkil hai. Jis pal do caches ek hi address rakhti hain, kisi ko unhe police karna hota hai taaki koi stale copy na padhe. Woh policing cache coherence kehlaati hai, aur woh free nahi hai.

PICTURE — figure s02. Core 1 ki cache (upar baayein) mein X = 105 (new) hai; Core 2 ki cache (neeche baayein) abhi bhi X = 100 (stale) rakhti hai; shared bus aur main memory daayin taraf hain. Ek kala arrow dikhata hai ki Core 1 ki write bus tak pahunchi; laal arrow jis par "invalidate!" likha hai Core 2 ki cache ki taraf point karta hai — hardware use bata raha hai "apni X ki copy hatao". Woh laal arrow usi bus par travel karta hai jo data use karta hai.

Key realization: shared memory asal mein message passing hai — messages bas hardware aapki peeth peeche memory bus par bhejta hai.

Step 3 — Scale karo: bus ek wall kyun ban jaati hai

KYA HOTA HAI. $N$ cores ko ek bus par rakho, sab ek hi address par write kar rahe hain. Har write baaki $N - 1$ caches ko invalidate karni padti hai — woh $N - 1$ invalidate messages hain, har sharer ko ek.

KYU. Hum jaanna chahte hain ki cost $N$ ke saath kaise badhti hai, kyunki "kya yeh scale karta hai?" parallel computing ka poora sawaal hai. Growth rate big-O se jawaab milta hai (upar define kiya): yahan hum puchhte hain ki cost $N$ , $N^{2}$ , ya worse ki tarah badhti hai.

PICTURE — figure s03. Writer core upar hai. Neeche, $N - 1$ doosri caches ek shared bus (moti grey pipe ki tarah draw ki) par line mein khadi hain. Writer se, $N - 1$ laal invalidate arrows fan out hote hain, har doosri cache ko ek. Har arrow ek hi pipe se guzarna padta hai — wahi pipe bottleneck hai, aur caption clearly likhta hai "N-1 red invalidates → cost grows ~ O(N), all-write ~ O(N^2)".

Intuition Reads mein bhi coherence cost lagti hai, sirf writes mein nahi

Sirf writes nahi, reads bhi bus par baat karte hain. Jab ek core ek line read karna chahta hai jise woh Invalid (I) state mein rakhta hai (kyunki kisine write karke use kick out kiya — Step 2), use ek fresh copy fetch karni padti hai: woh bus par ek read request bhejta hai, aur jo bhi Modified state mein line rakhta hai use supply karna hota hai (ek write-back / cache-to-cache transfer). Aur jab ek core jo sirf Shared state mein line rakhta hai write karna chahta hai, use pehle permission ke liye ek upgrade request bhejna padta hai. Toh dono directions — read-miss refills aur write-upgrades — bus traffic add karte hain. Bus par invalidates, upgrades, aur refill data sab mix hoke chalte hain, isliye heavy sharing (kisi bhi direction mein) use saturate kar deta hai.

Step 4 — Escape hatch: har core ko apni memory do

KYA HOTA HAI. Ek bus aur shared caches ki jagah, har core ko apni private memory do. Ab Core 1 physically Core 2 ki memory ko touch nahi kar sakta. Koi invalidate storms nahi — kyunki invalidate karne ke liye shared kuch hai hi nahi.

KYU. Hum ek hidden cost (coherence) ki jagah ek explicit cost (message bhejna jab sach mein kisi aur ka data chahiye) le rahe hain. Cost ko visible banana programmer ko use control karne deta hai. Yeh message-passing ki duniya hai.

PICTURE — figure s04. Do alag boxes. Baayein, "Core A" apni "memory A (private)" ke upar hai; daayin, "Core B" "memory B (private)" ke upar. Dono ke beech koi shared bus nahi — ek hi link hai ek orange arrow jis par "send / receive over network" likha hai jo beech se guzar raha hai. Neeche text ka moral yeh hai: ek explicit message matlab aap control karte ho KAB data move hoga.

Step 5 — Ek message ki cost kya hoti hai?

KYA HOTA HAI. $M$ bytes bhejna do parts mein hota hai: ek fixed setup cost jo aap chahe message kitna bhi chhota ho pay karte ho, plus ek per-byte cost jo size ke saath badhti hai.

IN DONO MEIN KYUN SPLIT KARO? Kyunki dono parts $M$ badalne par bilkul alag behave karte hain, aur yeh jaanna ki kaun dominate karta hai aapko batata hai ki fast code kaise likhein. Yahi agli formula ka poora point hai.

PICTURE — figure s05. Ek seedhi line axes par: "message size $M$ (bytes)" (horizontal) versus "time $T_{send}$ " (vertical). Line zero se shuru nahi hoti — woh $T_{lat}$ height par shuru hoti hai (orange dashed line, "T_lat: fixed toll"). Wahan se yeh $1/ B$ slope ke saath upar jaati hai (plum arrow ise "bandwidth region" label karta hai). Baayaan flat-ish end woh hai jahan latency rule karta hai; seedha daayin end woh hai jahan bandwidth rule karta hai.

Step 6 — Edge case: size zero ka message

KYA HOTA HAI. $M = 0$ set karo. Tab $M / B = 0$ , toh $T_{send} = T_{lat}$ . Ek zero-byte message abhi bhi poori latency cost karta hai.

YEH KYUN DIKHAO. Yeh prove karta hai ki latency ek floor hai jise aap data chhota karke kabhi nahi tod sakte. Beginners assume karte hain "koi data = koi cost nahi"; formula kuch aur kehta hai. Bahut saare tiny sync messages bhejna (jaise ek barrier) baar baar $T_{lat}$ pay karta hai.

PICTURE — figure s06. Step 5 wali line, lekin ab ek highlighted orange dot exactly $M = 0$ par. Dot horizontal axis par nahi hai — yeh $T_{lat}$ height par float karta hai, aur annotation "M = 0 → T = T_lat (not 0!)" seedha uski taraf point karta hai. Dot aur zero ke beech ka woh vertical gap hi unavoidable toll hai.

$M = 0 \Rightarrow T_{send} = T_{lat} + \frac{0}{B} = T_{lat} (\neq = 0)$

Step 7 — Edge case: woh write jo kuch cost nahi karta (M-state shortcut)

KYA HOTA HAI. Shared memory par wapas aao, maan lo ek core pehle se line ko privately own karta hai (state M — Step 3 dekho). Woh phir se likhta hai. Kisi doosri cache ke paas copy nahi, toh zero invalidate messages fire hote hain (Step 2 formula mein $k = 0$ ).

YEH KYUN DIKHAO. Yeh coherence ka best case hai, aur yeh explain karta hai ki single-threaded code aur thread-private data shared memory par poori speed se kyun chalta hai: coherence tab hi kaatata hai jab data cores ke beech actually shared hota hai. Yeh summary mein trap bhi setup karta hai — villain sharing nahi, unnecessary sharing hai.

PICTURE — figure s07. Beech mein ek core jis par "core owns X, state = M" likha hai, grey shared bus ke upar. Kahin bhi koi laal arrows nahi — annotation padhta hai "no other cache holds X → 0 red arrows", aur bus ke neeche text note karta hai "shared bus stays quiet". Bus par khamoshi hi poora point hai.

Ek picture mein poora summary

KYA HOTA HAI. Ek decision plot. Horizontal axis = cores ko kitna communicate karna hai. Jaise sharing badhti hai, shared memory ki coherence cost chadhti hai (bus saturate ho jaata hai), jabki distributed memory ki cost steady — lekin latency-floored — rehti hai. Jahan dono curves milti hain woh crossover hai: us se neeche shared jeetta hai; uske upar distributed jeetta hai.

PICTURE — figure s08. Axes "how much cores must communicate →" (horizontal) versus "total time" (vertical). Orange curve (shared memory) neeche shuru hoti hai magar tezi se upar mod leti hai — uski coherence cost sharing badhne par super-linearly badhti hai. Teal curve (distributed memory) upar shuru hoti hai (woh halki communication ke liye bhi latency floor pay karti hai) magar dhire badhti hai. Dono ek plum dot par milti hain jis par "crossover" likha hai. Dot ke baayein region par "shared wins" likha hai; daayin region par "distributed wins".

Recall Feynman retelling — apne words mein bol kar batao

Do tarike sochon ek workshop chalane ke. Shared-table shop mein, har worker ek hi board dekhta hai. Sasta hota hai jab woh mostly ek doosre ko ignore karte hain — magar jaise hi do ek hi tool uthate hain, ek rule sab ko force karta hai "apni copy chhodo!" aur woh chillana ek hi hallway (bus) ko jam kar deta hai. Ek hi tool par zyada workers → zyada chillana → gridlock. Aur sirf change karna tool ko nahi chalata chatter: koi bhi tool jo kisi ne abhi change kiya use fetch karna bhi "haath kar do" messages ka ek round chahta hai (Step 3 ka read-miss aur upgrade traffic). Separate-tables shop mein, har worker ka apna private board hai. Koi bhi accident se kisi aur ka tool nahi le sakta — magar share karne ke liye, aapko ek package mail karna padta hai. Mail karne mein ek fixed post-office toll ( $T_{lat}$ ) aur per-pound cost ( $M / B$ , woh speed use karo jo aap actually dekhte ho, brochure ki peak nahi) lagta hai. Ek khaali envelope bhi toll cost karta hai (Step 6), toh aap batch karo — hazaar chhote packages ki jagah ek bada bheejo. Winner kaun? Agar aapke workers rarely share karte hain, shared table fastest hai. Agar woh bahut zyada share karte hain — ya aapke paas hundreds of workers hain — toh chillana shared table ko duba deta hai, aur mail-based shop jeetta hai. Aur sneaky tax se bachna (Step 7): do workers jo tools use karte hain jo ek hi drawer mein happen to baithe hain, "apni copy chhodo!" rule trigger karte hain chahe unhone kabhi ek hi tool nahi maanga. Tools ko alag raho.

Recall Quick self-test

Ek zero-byte message kya cost karta hai, aur kyun? ::: Poori latency $T_{lat}$ — setup toll fixed aur size se independent hai, toh data ko zero karne se woh kabhi remove nahi hota. Ek Shared line par ek write kitne invalidate messages bhejta hai, aur jab saare $N$ cores use likhte hain toh worst-case total growth kya hai? ::: Ek write $N - 1$ invalidates bhejta hai (har doosre sharer ko ek), isliye ek write per $O (N)$ ; saare $N$ cores use hammer karte hain toh total $N \cdot (N - 1)$ hoga, yaani $O (N^{2})$ . Shared-memory write essentially free kab hoti hai? ::: Jab cache already line ko Modified (M) state mein own karta hai — koi doosri cache copy nahi rakhti, toh 0 invalidates bhejta hai. Writes ke alawa, ek read-side action batao jo abhi bhi coherence traffic cost karta hai. ::: Invalid state mein rakhi line ko padhna (read-miss refill), ya Shared line ko writable mein upgrade karna — dono ke liye bus messages chahiye.