Shared memory vs distributed memory: Worked examples

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

Yeh page parent topic ka drill ground hai. Parent ne tumhe ideas bataye; yahan hum har tarah ke questions count karte hain jo yeh ideas throw kar sakti hain, phir ek example solve karte hain. Kuch bhi hand-wave nahi hai: har number derive kiya gaya hai, har unit check ki gayi hai.

Kisi bhi formula ko touch karne se pehle, ek promise: main koi symbol use nahi karunga jab tak main clearly nahi keh deta ki uska matlab kya hai aur woh kis picture mein rehta hai.

Neeche wali figure exactly yeh do pictures side by side draw karti hai. Left half dekho: teen cores (lavender circles) sab ek butter-coloured memory mein reach karte hain cheap two-way whisper arrows (coral) ke saath — lekin notice karo ki ek table kitni crowded hai. Ab right half: har core apna khud ka mint memory box rakhta hai, aur share karne ka ek hi tarika hai — ek one-way coral "letter" arrow nodes ke beech. Woh left-vs-right contrast hi poori page hai; neeche har example bas ek side par numbers dalta hai.

Figure — Shared memory vs distributed memory

The scenario matrix

Yahan "scenario" = ek shape of problem. Agar hum har row ke liye ek example solve karein, koi bhi exam question tumhe surprise nahi kar sakta. Neeche ki table har cell ko plain words mein naam deti hai — compact symbols $N$ (kitne cores/caches), $M$ (message size bytes mein) aur $B$ (network bandwidth) sab "The three tools" mein immediately baad mein define hain, kisi bhi example ke use karne se pehle.

#	Cell (case class)	Ise distinct kya banata hai	Covered by
A	Shared, cache-hit dominated	Almost saare accesses cache hit karte hain → tiny average time	Ex 1
B	Shared, coherence-storm	Kaafi cores ek line par likh rahe hain → bus invalidations se flood ho jaata hai	Ex 2
C	Shared, degenerate: false sharing	Alag variables, same cache line → hidden invalidations	Ex 3
D	Distributed, latency-bound (small msg)	Message itna chhota ki fixed stamp cost dominate karti hai	Ex 4
E	Distributed, bandwidth-bound (big msg)	Message itni badi ki per-byte cost dominate karti hai	Ex 5
F	Distributed, collective (AllReduce)	Cost slowly (logarithm ki tarah) badhti hai core count ke saath	Ex 6
G	Zero / limiting input	Empty message; single core; formulas kya kehte hain?	Ex 7
H	Crossover word problem	Real decision: ek task ke liye shared ya distributed choose karo	Ex 8
I	Exam twist: mixed / trap	Setup jo lagta hai ek ko favor karti hai lekin karti nahi	Ex 9

Hum parent se teen formulas reuse karte hain, yahan restate ki gayi hain taaki kuch assume na ho.

Formula Teen tools (har symbol words mein define kiya gaya)

Tool 1 — Average shared-memory access time. $T_{access} = T_{hit} \cdot P + T_{miss} \cdot (1 - P)$

$T_{hit}$ = woh time jab data fast cache mein already tha (ek "instantly mil gaya" time).
$T_{miss}$ = woh time jab hume slow main memory tak jaana pada (ek "jaake fetch karna pada" time).
$P$ = hit rate: $0$ aur $1$ ke beech ka ek fraction jo kehta hai kitne accesses lucky hits the. $P = 1$ matlab hamesha mila, $P = 0$ matlab kabhi nahi.
Do pieces ek weighted average hain: achhe outcome ko $P$ se reward karo, bure ko jo bacha $1 - P$ se.

Tool 2 — Point-to-point message time. $T_{send} = T_{lat} + \frac{M}{B}$

$T_{lat}$ = latency, woh fixed "postage" jo tum koi bhi message start karne par pay karte ho, chahe empty ho.
$M$ = message size bytes mein (envelope kitni moti hai).
$B$ = bandwidth, wire ka drain rate bytes-per-second mein (bytes kitni tezi se jaate hain).
$M / B$ = bytes divided by bytes-per-second = seconds. Units check: yeh ek time hai. ✓

Tool 3 — Coherence traffic on a write. $bus transactions per write = {1 N line already Modified in my cache line Shared across all N caches$

$N$ = processor caches ki sankhya jo ek copy rakhte hain (us mein play hone wala core count).
Ek bus transaction (a.k.a. bus message) yahan = shared coherence bus par ek request rakhna jo saare caches dekhte hain — jaise ek invalidate ("apni copy drop karo is line ki") ya ek line transfer ("mujhe updated line do"). Transactions count karna count karna hai kitni baar shared bus occupied hai, jo ise saturate karta hai.
"Modified", "Shared", "Invalid" MSI states hain parent se.

Cell A — Shared, cache-hit dominated

Worked example Ex 1 · Lucky-hit average

Ek core hit rate $P = 0.95$ ke saath memory access karta hai. Ek hit costs $T_{hit} = 2$ ns, ek miss costs $T_{miss} = 120$ ns. Average access time kya hai?

Forecast: Padhne se pehle guess karo. $2$ ns ke kareeb ya $120$ ns ke? (Hint: $95%$ time hit hota hai.)

Step 1 — Do outcomes mein split karo. Hits $P = 0.95$ fraction of the time hote hain; misses baaki $1 - P = 0.05$ . Yeh step kyun? Tool 1 sirf "har outcome ko kitni baar hota hai usse weight karo" hai — ek plain average.

Step 2 — Weight karo aur add karo. $T_{access} = 2 (0.95) + 120 (0.05) = 1.9 + 6.0 = 7.9 ns$ Yeh step kyun? Rare miss (sirf $5%$ ) phir bhi $6$ ns contribute karta hai kyunki yeh hit se $60 \times$ zyada expensive hai. Tail heavy hoti hai.

Verify: Sanity — answer $2$ aur $120$ ke beech hona chahiye. Hai ( $7.9$ ). Aur kyunki hits dominate karte hain, yeh low end ke paas hai. Units: ns throughout. ✓

Cell B — Shared, coherence-storm

Worked example Ex 2 · Bus traffic jab sab likhte hain

$N = 8$ cores (yaad karo $N$ = caches ki sankhya jo copy rakhti hain) ek variable flag ki Shared read-only copy rakhte hain. Phir saaro 8 flag par likhte hain, ek ke baad ek. Kul kitne invalidate bus messages?

Forecast: Kya yeh $8$ hai? $8 \times 7$ ? Guess karo.

Step 1 — Pehla writer. Core 1 ki line Shared hai (doosron ke paas copies hain). Tool 3 se, ise baaki $N - 1 = 7$ caches ko invalidate karna hoga. Yeh $7$ bus transactions hain, aur ab sirf Core 1 line rakhta hai (state Modified). Yeh step kyun? Ek write tab tak proceed nahi kar sakta jab tak kahin stale copies exist karti hain — coherence sole ownership demand karti hai.

Step 2 — Har baad ka writer. Ab line exactly ek cache mein Modified hai. Core 2 use chahta hai: Core 1 ko ise hand over karna hoga (1 transfer). Ab Core 2 sole owner hai. Core 3 wahi karta hai, etc. $7$ aise hand-offs hain (cores 2→3→…→8), har ek $1$ transaction. Yeh step kyun? Storm ek owner par settle hone ke baad, ownership sirf migrate karti hai — ab 7 caches par broadcast nahi karna, kyunki sirf ek copy exist karti hai.

Step 3 — Total. $7 (pehla broadcast) + 7 (hand-offs) = 14 transactions$

Verify: Naive " $N$ per write $\times 8$ writes $= 64$ " se compare karo. Actual answer $14$ bahut kam hai kyunki pehle write ke baad kisi aur ke paas invalidate karne ke liye copy nahi hai. Parent mein $O (N)$ -per-write bound worst case hai (jab line baar baar re-shared hoti rehti hai), steady state nahi. ✓ Yeh consistency traffic concrete banaya gaya hai.

Worked example Ex 3 · Do variables, ek cache line

Ek 64-byte cache line ints ka ek array rakhti hai. Har int 4 bytes ka hai. Thread 0 count[0] likhta hai; Thread 1 count[1] likhta hai. Unke paas koi logical data share nahi hai. Har ping-pong (invalidate + puri line re-fetch) $100$ ns cost karti hai, aur woh $1000$ baar alternate karte hain. Wasted time kya hai, ideal $2$ ns per write se compare karte hue agar koi conflict na hota?

Forecast: Near zero waste hona chahiye (alag variables), right? Dekho.

Step 0 — Kitne ints line share karte hain? Ek 64-byte line at 4 bytes per int mein $64/4 = 16$ ints hain. Toh count[0] aur count[1] sirf 16 mein se 2 slots hain — deliberately padded nahi kiye gaye. Real code mein tum har counter ko uski apni 64-byte line tak pad karte (60 bytes waste karo unhe alag rakhne ke liye); yahan hum intentionally unhe packed rakhte hain taaki dono same line mein fall karein aur collide karein. Woh packing hi poore trap ka point hai. Yeh step kyun? Bug sirf isliye exist karta hai kyunki do variables ek line mein neighbours hain; hume pehle yeh show karna hoga ki woh actually wahan fit hote hain pehle yeh claim karne se ki collide karte hain.

Step 1 — Trap pehchano. count[0] aur count[1] same 64-byte line mein hain. Coherence poori lines par kaam karti hai, individual ints par nahi. count[0] likhna poori line ko Modified mark karta hai, Thread 1 ki count[1] ki copy ko invalidate karta hai. Yeh step kyun? Hardware ko bilkul idea nahi hai ki do ints logically independent hain — false sharing hai coherence jo spatial neighbours ko punish karta hai.

Step 2 — Ping-pongs count karo. $1000$ alternations mein se har ek $100$ ns par ek line transfer force karta hai: $T_{false} = 1000 \times 100 = 100, 000 ns = 100 μ s$ Yeh step kyun? Jab bhi doosra thread shared line ko touch karta hai, line bounce back karti hai — isliye expensive transfers ki count alternations ki count ke barabar hai, variables ki sankhya ke nahi.

Step 3 — Ideal se compare karo. " $1000$ alternations" matlab Thread 0 aur Thread 1 dono $1000$ baar likhte hain, isliye $2 \times 1000 = 2000$ writes total hoti hain. Agar separate lines par padded hoon, un $2000$ writes mein se har ek $2$ ns par local hit hai: $T_{ideal} = 2000 \times 2 = 4000 ns = 4 μ s$ $slowdown = \frac{100 , 000}{4000} = 25 \times$ Yeh step kyun? Hume fair "same work" comparison ke liye dono threads ki writes count karni hain ( $2000$ , $1000$ nahi); actual ko conflict-free se divide karna phir pure penalty of false sharing isolate karta hai.

Verify: Order-of-magnitude parent ke " $5 - 10 \times$ " range se match karta hai (humne harsher ping cost choose kiya, isliye $25 \times$ mila). Units: ns → μs consistent. ✓ Fix padding hai — classic cache-line padding trick.

Cell D — Distributed, latency-bound (small message)

Agla figure exactly yahi idea plot karta hai. Horizontal axis message size $M$ bytes mein hai (log scale, left par $1$ byte se right par $1 0^{9}$ bytes tak); vertical axis total send time microseconds mein hai (bhi log scale). Lavender curve follow karo (total $T_{send}$ ): far left par yeh coral dashed "latency floor" se chipki hai — woh flat $5 μ s$ stamp hi Ex 4 ka answer hai, coral dot se marked. Mint dotted line pure per-byte term $M / B$ hai; far right par lavender curve uske saath upar jaati hai — woh steep region Ex 5 hai, mint dot se marked. Legend teeno lines ka naam leta hai. Jahan coral floor aur mint slope cross karte hain woh "latency vs bandwidth" crossover hai — poori distributed story ek plot mein.

Cell E — Distributed, bandwidth-bound (big message)

Worked example Ex 5 · Ek fat message (bit/byte trap)

Same network idea lekin faster wire: $T_{lat} = 5 μ s$ , aur wire quote ki gayi hai $B = 100$ Gbps (gigabits/sec, $= 100 \times 1 0^{9}$ bits/s) ke roop mein. Hum $M = 1$ GB ( $= 1 0^{9}$ bytes) bhejte hain. Time?

Forecast: Dhyan raho — Gbps bits mein hai, GB bytes mein.

Step 1 — Bandwidth ko bytes/sec mein convert karo. $B = 100 Gbps = \frac{100 \times 1 0 ^{9} bits/s}{8 bits/byte} = 12.5 \times 1 0^{9} bytes/s$ Yeh step kyun? 8 se divide karo ya tumhara answer $8 \times$ bahut chhota hoga — woh classic exam trap upar flag kiya gaya hai.

Step 2 — Byte transfer time. $\frac{M}{B} = \frac{1 0 ^{9} bytes}{12.5 \times 1 0 ^{9} bytes/s} = 0.08 s = 80, 000 μ s$ Yeh step kyun? Yeh phir Tool 2 ka per-byte term hai — lekin ab $M$ ek billion bytes hai, isliye woh term jo Ex 4 mein invisible tha woh enormous ho jaata hai. Same formula, opposite regime.

Step 3 — Latency add karo. $T_{send} = 5 μ s + 80, 000 μ s = 80, 005 μ s \approx 80 ms$ Yeh step kyun? Tool 2 hamesha fixed stamp upar add karta hai; yahan hum yeh karte hain sirf yeh dikhane ke liye ki yeh negligible hai ( $80, 005$ mein se $5$ ), prove karta hai ki message bandwidth-bound hai.

Verify: Ab $M / B ≫ T_{lat}$ — fixed stamp rounding error hai. Hum bandwidth-bound hain. Yeh $80$ ms parent ke AllReduce estimate se match karta hai. ✓ Ex 4 se contrast: dono messages same Tool 2 follow karte hain, opposite regime mein, sirf $M$ se decide hota hai.

Cell F — Distributed, collective (AllReduce grows like log N)

Worked example Ex 6 · 100 GPUs par gradients sum karna

Ek AllReduce $N = 100$ GPUs mein se har ek se ek value combine karta hai. Pehle ke examples se match karne ke liye hum same latency $T_{lat} = 5 μ s$ per hop rakhte hain. Ek tree-based AllReduce lagbhag $2 lo g_{2} (N)$ latency hops leta hai plus $M = 1$ GB ki ek payload pass at $B = 100$ Gbps. Time estimate karo.

Forecast: Kya 100 GPUs add karne ki cost $100 \times$ hai ya sirf $lo g$ -times ki latency?

Step 1 — Latency term. $2 lo g_{2} (100) \cdot T_{lat} = 2 \times 6.6439 \times 5 μ s \approx 66.4 μ s$ Yeh step kyun? Ek tree har level par group ko half karta hai, isliye $lo g_{2} N$ levels lagte hain — $N$ nahi. Har level ek hop ka same $5 μ s$ stamp cost karta hai, isliye hum hops ko $T_{lat}$ se multiply karte hain.

Step 2 — Payload term. Ex 5 se, $1$ GB at $100$ Gbps $\approx 80$ ms $= 80, 000 μ s$ . Yeh step kyun? Gradients khud abhi bhi wire cross karne padte hain ek baar, isliye hum Tool 2 ka per-byte cost reuse karte hain jo humne already compute kiya — division dobara karne ki zaroorat nahi.

Step 3 — Total aur interpretation. Do contributions add karo: $T_{AllReduce} \approx 66.4 μ s + 80, 000 μ s = 80, 066.4 μ s \approx 80.07 ms$ Yeh step kyun? Total time latency hops plus payload hai; unhe add karke aur do numbers compare karke ( $66.4 μ s$ vs $80, 000 μ s$ ) pata chalta hai kaun dominate karta hai — payload, lagbhag $1205 \times$ ke factor se.

Interpretation: Latency term $80$ ms payload ke paas rounding error hai, isliye bade gradients ke liye AllReduce bandwidth-bound hai, aur uski cost essentially ek baar data move karne ki cost hai. Magic $lo g$ mein hai: kyunki $lo g_{2} 100 \approx 6.6$ , $100$ se $1000$ GPUs jump karna sirf ek aur hop ( $\approx 5 μ s$ ) add karta hai, na $900 \times$ zyada latency.

Verify: Latency ( $\sim 66 μ s$ ) payload se $1000 \times$ se zyada chhota hai — payload dominate karta hai. Parent ke " $\approx 80$ ms" estimate se same order of magnitude, aur total $80.07$ ms round hota hai. ✓ Yeh $lo g$ scaling distributed collectives ki scaling win hai.

Cell G — Zero aur limiting inputs

Worked example Ex 7 · Formulas edges par kya kehte hain

Har tool ko uske degenerate input par test karo. Yeh woh "trick zeros" hain jinhein exams love karte hain.

Case G1 — Empty message ( $M = 0$ ). $T_{send} = T_{lat} + \frac{0}{B} = T_{lat}$ Kyun? Zero-byte "ping" bhi stamp pay karta hai. Kuch bhi na bhejna phir bhi $T_{lat} = 5 μ s$ cost karta hai. Isliye synchronization pings free nahi hain.

Case G2 — Single processor ( $N = 1$ ). Coherence traffic: sirf ek cache ke saath, ek write hamesha ek Modified line par hai jo main already own karta hoon → Tool 3 deta hai 1 bus transaction (fact mein, koi invalidations bhejne ki zaroorat nahi). Koi sharing nahi matlab koi coherence cost nahi. $N = 1$ wali ek "parallel" machine mein zero coordination overhead hai — honest baseline.

Case G3 — Perfect hit rate ( $P = 1$ ). $T_{access} = T_{hit} \cdot 1 + T_{miss} \cdot 0 = T_{hit} = 2 ns$ Kyun? Har access hit karta hai; misses kabhi nahi hote; average hit time par collapse ho jaata hai. Confirm karta hai Tool 1 apni boundary par sahi behave karta hai.

Case G4 — Perfect miss rate ( $P = 0$ ). $T_{access} = 2 (0) + 120 (1) = 120 ns$ Doosra extreme: pure misses pure miss time dete hain. Average hamesha in do poles ke beech rehta hai ( $2$ aur $120$ ).

Verify: Saaro char edges physically obvious answer dete hain, isliye formulas interior par bhi trustworthy hain. ✓

Cell H — Crossover word problem

Worked example Ex 8 · Kaun si machine khareedni chahiye?

Tumhare paas ek task hai jo $R = 1 0^{6}$ shared-variable updates karta hai. Ek shared machine par har update (coherence contention ke saath) average $T_{s} = 150$ ns leta hai. Ek distributed machine par har "update" $M = 8$ bytes ka ek message ban jaata hai with $T_{lat} = 5 μ s$ , $B = 10$ GB/s. Kaun faster hai, aur kyun?

Forecast: Distributed "better scales" karta hai, toh woh jeetha... ya phir tiny frequent updates ke liye?

Step 1 — Shared total. $T_{shared} = R \cdot T_{s} = 1 0^{6} \times 150 ns = 1.5 \times 1 0^{8} ns = 0.15 s$ Yeh step kyun? Har update independent hai aur $T_{s}$ cost karta hai, isliye total time sirf count times cost hai.

Step 2 — Ek distributed message ki cost. Tool 2 use karte hue with $B = 10$ GB/s $= 1 0^{10}$ bytes/s: $\frac{M}{B} = \frac{8}{1 0 ^{10}} s = 0.0000008 μ s$ , toh $T_{one msg} = 5 μ s + 0.0000008 μ s \approx 5 μ s$ Yeh step kyun? Hume compare karne se pehle ek shared update ko uske distributed equivalent — ek message — mein convert karna hoga. Yeh latency-bound hai (cf. Ex 4), isliye stamp hi poori cost hai.

Step 3 — Distributed total. $T_{dist} = R \cdot T_{one msg} = 1 0^{6} \times 5 μ s = 5 \times 1 0^{6} μ s = 5 s$ Yeh step kyun? Same "count times cost" logic Step 1 jaisi, ab message cost ke saath, isliye do machines identical footing par compare hoti hain.

Step 4 — Compare karo. $\frac{T _{dist}}{T _{shared}} = \frac{5 s}{0.15 s} \approx 33 \times slower$ Yeh step kyun? Ek ratio, difference nahi, batata hai ki ek choice kitni baar worse hai — decision-relevant quantity.

Verify: Kaafi tiny frequent shared updates ke liye, shared memory ~33× se jeetta hai. Message stamp ( $5 μ s$ ) shared update cost ( $150$ ns) ka $33 \times$ hai, isliye ratio near $33$ aana hi tha. "Distributed better scales" rule tab hi kaam karta hai jab communication ke per kaam zyada ho (Ex 5/6) — yahan nahi. ✓ Yahi real engineering trade-off hai jo parent ka jigsaw metaphor point karta hai.

Cell I — Exam twist / trap

Worked example Ex 9 · "Lagta hai bandwidth-bound hai lekin hai nahi" trap

Ek exam poochta hai: "Node A $N_{msg} = 1000$ separate messages bhejta hai $M = 1$ KB $= 1000$ bytes each, $T_{lat} = 5 μ s$ , $B = 10$ GB/s $= 1 0^{4}$ bytes/μs. Total time? Ab ise ek single $1$ MB message bhejne se compare karo."

Forecast: Data $1$ MB dono taraf hai — toh same time? (Trap!)

Step 1 — 1000 small messages ki cost. Har ek: $T_{lat} + M / B = 5 + \frac{1000}{1 0 ^{4}} = 5 + 0.1 = 5.1 μ s$ . $T_{many} = 1000 \times 5.1 = 5100 μ s$ Yeh step kyun? Tum $5 μ s$ stamp 1000 baar pay karte ho. Yahi poora trap hai.

Step 2 — Ek bade message ki cost. $M = 1 0^{6}$ bytes: $5 + \frac{1 0 ^{6}}{1 0 ^{4}} = 5 + 100 = 105 μ s$ . Yeh step kyun? Batching stamp ek baar pay karta hai, isliye sirf per-byte term badhta hai — aur bytes wahi $1$ MB hain dono taraf.

Step 3 — Ratio. $\frac{5100}{105} \approx 48.6 \times faster to batch$ Yeh step kyun? Ratio expose karta hai ki sirf difference $999$ extra stamps hain, jo hi exam ka poora point hai.

Verify: Same bytes ( $1$ MB total), wildly different time — kyunki latency per message pay hoti hai, bandwidth per byte. Batching ek baar latency pay karta hai. Yahi parent ka "batch communications" rule hai, quantified. ✓ Yeh single most common vs MPI performance-tuning exam question hai.

Recall Self-test (reveal karne se pehle answer do)

Average access time formula hit aur miss ko kisse weight karta hai? ::: Hit rate $P$ aur uske complement $1 - P$ se; yeh ek weighted average hai, hamesha $T_{hit}$ aur $T_{miss}$ ke beech. Ex 2 mein total 14 kyun hai, 64 kyun nahi? ::: Pehle broadcast ke baad (7 invalidations) sirf ek cache line own karta hai, isliye baad ki writes sirf ownership migrate karti hain (7 hand-offs) — kisi aur ke paas invalidate karne ke liye copy nahi. False sharing (Ex 3) independent variables ke saath bhi kyun hurt karta hai? ::: Coherence poori cache lines par kaam karti hai; ek 64-byte line mein do logically-separate ints cores ke beech line ko ping-pong karte hain. Ek zero-byte message kitna cost karta hai (Ex 7)? ::: Exactly $T_{lat}$ — fixed latency; kuch bhi, chahe kuch bhi na ho, free mein nahi bhej sakte. Ex 8 mein shared memory kyun jeeta hai? ::: Kaafi tiny frequent updates ke liye, message stamp ( $5 μ s$ ) shared update ( $150$ ns) ko dwarf karta hai, messaging ko ~33× slower banata hai. Batching win (Ex 9) exist karta hai kyunki latency ___ per pay hoti hai aur bandwidth ___ per. ::: per message; per byte.