Shared memory vs distributed memory: Exercises — Hinglish deep dive

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

Shuru karne se pehle, teen numbers jo hum baar baar use karenge (sab parent note se):

Har system ke liye bolo shared ya distributed memory: (a) Ek laptop jisme 8-core Intel CPU hai jo ek program 8 threads ke saath run kar raha hai. (b) Ek 500-node cluster jahaan har node ek alag computer hai jo InfiniBand se connected hai. (c) 100 cloud VMs jo network ke zariye coordinate kar rahe hain.

Recall Solution 1.1

(a) Shared. Ek physical memory, saare 8 cores ek hi global address space ko directly read/write karte hain. (b) Distributed. Har node ki apni private memory hai; nodes messages pass karke baat karte hain. (c) Distributed. VMs ek doosre ki RAM touch nahi kar sakti; sirf network hi channel hai.

Rule of thumb: Kya core X, core Y ka data ek plain load instruction se read kar sakta hai? Haan → shared. Sirf message bhejke → distributed.

Exercise 1.2 (L1)

Is sentence mein "Processor A send(data, size, dest) call karta hai aur Processor B receive() call karta hai," yeh kaunsa memory model hai, aur doosre model mein equivalent action kaisa dikhta?

Recall Solution 1.2

Yeh distributed memory hai — communication explicit hai (tum literally operation ka naam lete ho). Shared memory mein equivalent hota hai implicit: A simply x = 5; karta hai aur B baad mein read x karta hai. Koi send/receive nahi aata — hardware ne tumhare liye data move kar diya (cache-coherence protocol ke zariye). Dekho Parallel Programming Models.

Level 2 — Application

Exercise 2.1 (L2)

Ek core ke liye $T_{hit} = 1 ns$ , $T_{miss} = 100 ns$ , aur hit rate $P (hit) = 0.95$ hai. $T_{access}$ calculate karo.

Recall Solution 2.1

$P (miss) = 1 - 0.95 = 0.05$ . $T_{access} = 1 \cdot 0.95 + 100 \cdot 0.05 = 0.95 + 5.0 = 5.95 ns$ Matlab: bhale hi 95% accesses fast hain, rare 5% slow misses average ko dominate karte hain (5.95 ns mein se 5.0 ns). Misses hi dushman hain.

Exercise 2.2 (L2)

Ek network mein $T_{lat} = 10 μ s$ aur $B = 10 GB/s$ hai. Compare karo ek 1 MB message bhejna vs 1000 messages of 1 KB each (same total 1 MB). ( $1 MB = 1 0^{6}$ bytes, $1 KB = 1 0^{3}$ bytes, $1 GB = 1 0^{9}$ bytes use karo.)

Recall Solution 2.2

Har byte-batch ka transfer time $M / B$ hai. $B = 1 0^{10}$ bytes/s ke saath:

Ek bada message: $M = 1 0^{6}$ bytes. $T = 10 μ s + \frac{1 0 ^{6}}{1 0 ^{10}} s = 10 μ s + 100 μ s = 110 μ s .$

1000 chhote messages: har ek apna $T_{lat}$ pay karta hai. $T = 1000 (10 μ s + \frac{1 0 ^{3}}{1 0 ^{10}} s) = 1000 (10 μ s + 0.1 μ s) = 10100 μ s .$

Batched version $\approx 92 \times$ faster hai. Kyun: fixed latency $T_{lat}$ har message par pay hota hai, toh data ko 1000 pieces mein kaatna ise 1000 baar pay karwata hai. Isliye MPI programs batch karte hain — parent note dekho. Related: Interconnect Networks.

Figure — Shared memory vs distributed memory

Level 3 — Analysis

Exercise 3.1 (L3)

$N$ cores ek variable share karte hain MSI protocol ki Shared (S) state mein. Core 1 isme likhta hai. Parent ke rule "S se write karne par baaki $N - 1$ caches invalidate hone chahiye" ko use karte hue, kitne invalidate messages fire hote hain? Agar $N = 8$ aur har invalidate mein 30 ns bus time lagta hai (serialized), toh coherence burst kitna lamba hai?

Recall Solution 3.1

Invalidates needed $= N - 1$ . $N = 8$ ke liye: $8 - 1 = 7$ messages. Ek bus par serialized: $T = 7 \times 30 ns = 210 ns .$ Kyun $N - 1$ aur $N$ nahi: writer apni copy already khud rakhta hai — use sirf baaki caches ko silence karna hai. Yeh $O (N)$ growth hi wajah hai ki shared-memory bus machines 8–64 cores ke aaspaas top out kar jaati hain. Dekho Cache Coherence Protocols.

Exercise 3.2 (L3)

Ek struct int count[8] ko ek 64-byte cache line mein pack karta hai (har int = 8 bytes → 8×8 = 64). Aath threads mein se har ek ek alag index par likhta hai. Explain karo kyun performance collapse ho jaati hai, aur ek-line fix do.

Recall Solution 3.2

Yeh False Sharing hai. Saare 8 counters ek cache line mein rehte hain. Coherence poori lines track karta hai, individual bytes nahi. Toh jab Thread 0 count[0] likhta hai, hardware us line ko har doosre thread ki cache mein invalidate kar deta hai — chahe kisi ne count[0] touch na kiya ho. Har write line ko saare cores ke beech ping-pong karata hai.

Kaisa dikhta hai: line har update par core→core→core bounce karti hai, 8 independent writes ko ek fully serialized coherence storm mein badal deta hai (parent 5–10× slowdown report karta hai).

Fix: har counter ko apni cache line par pad karo:

struct { int val; char pad[56]; } count[8]; // har entry = 64 bytes

Ab writes alag lines par hit karte hain → koi cross-invalidation nahi.

Level 4 — Synthesis

Exercise 4.1 (L4)

$C = A \times B$ compute karo jahaan $A, B$ $1000 \times 1000$ matrices hain jo 4 nodes mein row-wise split hain. Node 0 poora $B$ ( $\approx 1 MB$ compressed yahan arithmetic ke liye) baaki 3 nodes ko broadcast karta hai, ek message each. Network: $T_{lat} = 10 μ s$ , $B_{net} = 10 GB/s$ . Broadcast time compute karo. Phir decide karo: kya communication ya computation likely bottleneck hai agar local compute $\approx 50 ms$ hai?

Recall Solution 4.1

$1 MB = 1 0^{6}$ bytes ka ek message: $T_{one} = 10 μ s + \frac{1 0 ^{6}}{1 0 ^{10}} s = 10 + 100 = 110 μ s .$ Teen sequential sends (Node 0 → Nodes 1,2,3): $T_{broadcast} = 3 \times 110 μ s = 330 μ s = 0.33 ms .$ Compute $= 50 ms$ se compare karo. Communication sirf $0.33/50 \approx 0.66%$ runtime hai. Conclusion: computation dominate karta hai — yeh problem ek one-time broadcast ke baad "embarrassingly parallel" hai. $B$ ka transfer ek baar pay karo, phir crunch karo. Yeh distributed memory at its best hai.

Exercise 4.2 (L4)

100 GPUs har batch mein gradient AllReduce karte hain. Model: $T_{AllReduce} \approx 2 lo g_{2} (N) \cdot T_{lat} + \frac{M}{B}$ , $N = 100$ , $T_{lat} = 2 μ s$ , $M = 1 GB = 8 \times 1 0^{9}$ bits, $B = 100 Gbps = 1 0^{11}$ bits/s ke saath. $T_{AllReduce}$ estimate karo. Kaunsa term dominate karta hai?

Recall Solution 4.2

Latency term: $2 lo g_{2} (100) \cdot 2 μ s$ . Kyunki $lo g_{2} (100) \approx 6.644$ : $2 \times 6.644 \times 2 μ s \approx 26.6 μ s .$ Bandwidth term: $\frac{8 \times 1 0 ^{9} bits}{1 0 ^{11} bits/s} = 0.08 s = 80 ms .$ $T_{AllReduce} \approx 0.0266 ms + 80 ms \approx 80 ms .$ Bandwidth bilkul dominate karta hai (80 ms vs 0.027 ms). Bade messages ke liye, $M / B ≫ T_{lat}$ — Exercise 2.2 ka bilkul ulta jahaan tiny messages ne latency ko king banaya. Lesson: message size decide karta hai kaunsa term jeetega.

Level 5 — Mastery

Exercise 5.1 (L5)

Ek single node mein 32 cores shared memory share karte hain (shared-memory model, OpenMP andar). Tumhare paas 64 aise nodes hain ek InfiniBand network par (distributed model, Message Passing Interface (MPI) across). Total = 2048 cores. Programming model design karo, aur justify karo kyun flat "MPI-everywhere" ya "threads-everywhere" scheme worse hai.

Recall Solution 5.1

Design: hybrid MPI + OpenMP.

Ek node ke andar (32 cores): shared memory. OpenMP threads use karo jo ek address space share karte hain — communication free implicit loads/stores hai, koi message overhead nahi.
Nodes ke across (64 nodes): distributed memory. MPI use karo: har node par ek MPI rank, ranks messages exchange karte hain.

Threads-everywhere kyun nahi? Tum nahi kar sakte — 64 alag machines ka koi shared address space nahi hai; node 0 par ek thread physically node 5 ki RAM load nahi kar sakta. Shared memory network cross nahi karta.

MPI-everywhere kyun nahi (2048 ranks)? Yeh kaam karta hai, lekin har node ke andar shared memory ko waste karta hai: ek hi node ke cores data ko message buffers ke through copy karte instead of directly padhne ke. Tum 32×64 = 2048 ranks ki coherence-free-but-copy-heavy traffic aur unnecessary memory duplication pay karte. Hybrid sahi tool har level par use karta hai: implicit sharing jahaan memory shared hai, explicit messaging sirf jahaan network cross karna ho. Dekho NUMA Architecture aur Memory Consistency Models.

Exercise 5.2 (L5)

Parent ke claim "cache coherence is hidden message passing" ko steel-man karo. Phir woh ek property batao jo distributed memory scalability ke badle mein chhod deta hai, aur ek jo rakhta hai.

Recall Solution 5.2

Steel-man: Shared memory mein, ek variable likhna secretly $N - 1$ caches ko invalidate broadcasts trigger karta hai (Ex 3.1). Woh invalidations bus par messages hain — tumne kabhi send() nahi likha. Toh shared memory ne communication khatam nahi ki; usne use chhupaaya aur automate kiya hai. Jab hidden traffic bus ko saturate karta hai, shared memory scaling band kar deta hai — wohi wall jo distributed memory face karta hai, bas invisible.

Distributed memory chhod deta hai: implicit communication + automatic consistency ki suwidha — programmer ko ab har transfer orchestrate karna hai aur deadlock ka risk hai. Distributed memory rakhta hai (aur yahi jeet hai): independent, non-shared memory — koi single bus nahi jiske liye har core lade. Isliye yeh hazaaron nodes tak scale karta hai jabki shared memory tens of cores par ruk jaata hai.

Recall Self-test: gap bharo

Latency message time dominate karta hai jab message ::: chhota ho (toh $M / B$ , $T_{lat}$ ke muqable mein tiny hai). MSI state S se ek write $N$ cores mein se itne invalidates bhejta hai ::: $N - 1$ . False sharing ki unit hai ::: cache line (~64 bytes), variable nahi. Woh interface jo shared vs distributed decide karta hai ::: load/store (implicit) vs send/receive (explicit).

Exercises — Shared memory vs distributed memory

Level 1 — Recognition

Exercise 1.1 (L1)