Shared memory vs distributed memory

6.1.5 · Hardware › Parallelism & Multicore

Why This Distinction Matters

Jo problem solve ho rahi hai: Jab aap ek computation ko N processors mein split karte ho, unhe results share karne padte hain. Architecture determine karta hai:

HOW data move hota hai (implicit hardware vs explicit messages)
WHEN consistency guarantee hoti hai (automatic vs programmer-controlled)
WHERE bottlenecks aate hain (memory bus vs network)

Shared Memory: The Implicit Communication Model

Formula Memory Access Time

$T_{access} = T_{cache hit} \cdot P (hit) + T_{cache miss} \cdot P (miss)$ First principles se derivation:

Processor address A par data request karta hai
Pehla check: Kya A mere private L1 cache mein hai? (hit time ≈ 1-4 cycles)
Agar nahi: Kya L2 mein hai? L3 mein? (≈ 10-40 cycles)
Agar nahi: memory bus ke zariye shared main memory se fetch karo (≈ 100-300 cycles)
Coherence protocol (MESI, MOESI): Write karne se pehle, hardware doosre caches ko invalidation broadcast karta hai $T_{write with coherence} = T_{cache write} + T_{invalidate broadcast} + T_{bus arbitration}$

Yeh formula kyun matter karta hai: Jaise-jaise cores badhte hain, memory bus ek bottleneck ban jaata hai (serialization point). Cache coherence traffic worst case mein $O (N^{2})$ badhta hai (N cores sab shared data likh rahe hain).

Worked example Shared Memory in Action

Scenario: 4 threads ek shared counter total update kar rahe hain.

// Thread 1, 2, 3, 4 sab yahi execute karte hain:
total = total + local_result;  // NOT atomic!

Hood ke andar kya hota hai (step-by-step):

Thread 1 total read karta hai (value 100) apne cache mein
Thread 1 compute karta hai 100 + 5 = 105
Thread 1 ke write back karne se pehle, Thread 2 bhi 100 read kar leta hai (agar timing unlucky ho toh cache coherence abhi tak nahi chali)
Dono 105 write back karte hain, ek update kho jaata hai!

Cache coherence kyun chahiye? Hardware ka MESI protocol normally Thread 2 ke cached copy ko invalidate kar deta jab Thread 1 likhta, but read-modify-write atomic nahi hai. Fix: Atomic operations (fetch_add) ya locks use karo.

Worked example Measuring Shared Memory Overhead

Experiment: False sharing penalty.

struct { int count[8]; } shared;  // 8 ints ek cache line mein (64 bytes)
// Thread i updates shared.count[i]

Prediction: Bhale hi har thread ek alag index likhta ho, agar count[0] aur count[1] ek hi cache line mein hain, toh count[0] likhna Thread 1 ke count[1] wale cache ko invalidate kar deta hai.

Result: Performance 5-10× girr jaata hai agar har count[i] ko alag cache lines mein pad kar diya jaye uske comparison mein.

Yeh kyun matter karta hai: Shared memory spatial locality ko dushman bana deta hai jab multiple threads nearby addresses likhte hain.

Distributed Memory: The Explicit Communication Model

Formula Message Passing Latency

$T_{send} = T_{latency} + \frac{M}{B}$

Jahan:

$T_{latency}$ = message initiate karne ka time (setup, OS overhead) ≈ 1-50 μs
$M$ = message size bytes mein
$B$ = network ki bandwidth (GB/s)

Derivation:

Step 1: Processor A send(data, size, dest_rank) call karta hai
Step 2: OS data ko network buffer mein copy karta hai (memory copy cost)
Step 3: Network interface card (NIC) packetize karta hai aur interconnect (Ethernet, InfiniBand) par transmit karta hai
Step 4: Destination NIC receive karta hai, Processor B ko interrupt karta hai, receive buffer mein copy karta hai
Step 5: Processor B receive() call karta hai retrieve karne ke liye Latency kyun dominate karti hai: Chhote messages ke liye (< 1 KB), $T_{latency} ≫ M / B$ . Isliye MPI programs batch communications karte hain—1 MB ka 1 message bhejana 1 KB ke 1000 messages se faster hai.

Worked example Distributed Memory: Matrix Multiplication

Scenario: $C = A \times B$ compute karo jahan $A, B$ $1000 \times 1000$ matrices hain jo 4 nodes mein split hain.

Data distribution:

Node 0: $A$ ki rows 0-249
Node 1: $A$ ki rows 250-499
Node 2: $A$ ki rows 500-749
Node 3: $A$ ki rows 750-999
Sare nodes ko $B$ ke sare columns chahiye Communication pattern (step-by-step):

$B$ Broadcast karo: Node 0 poora $B$ baaki sabko bhejta hai (3 messages ~1 MB each)
Local compute: Har node apna chunk compute karta hai: C[my_rows, :] = A[my_rows, :] @ B
Aur koi communication nahi chahiye (broadcast ke baad embarrassingly parallel)

$T_{total} = T_{broadcast} + T_{compute local} = (T_{lat} + \frac{1 MB}{B}) \cdot 3 + \frac{250 \cdot 100 0 ^{2}}{F L O P S}$ Yeh step (broadcast) kyun? Shared memory ke unlike jahan $B$ global memory mein hoti, yahan hum ise explicitly replicate karte hain. Cost ek baar upfront pay hoti hai.

The Coherence Problem in Shared Memory

Formula Cache Coherence Overhead

$N$ processors ke liye private caches ke saath, coherence maintain karne ke liye chahiye: $T_{coherence} = O (N) \cdot T_{broadcast invalidate}$

$O (N)$ kyun?

Jab Processor 1 address X par likhta hai, use sare $N - 1$ doosre caches ko invalidate messages bhejne padte hain
Har invalidate message shared memory bus bandwidth use karta hai
Heavy write contention mein, bus saturate ho jaata hai

Formal model (MSI protocol):

Modified (M): Cache mein sirf up-to-date copy hai, memory stale hai
Shared (S): Multiple caches mein read-only copies hain
Invalid (I): Cache line valid nahi hai Write par state transition:

Agar cache line S mein hai → invalidate broadcast karo, M mein transition karo
Agar doosra cache M mein hai → woh cache memory mein write back karta hai, aap M mein transition karte ho $Bus transactions per write = {1 N if already M if in S (must invalidate N - 1 caches)$

Comparative Analysis

Aspect	Shared Memory	Distributed Memory
Addressing	Global address space (koi bhi CPU → koi bhi address)	Local address space (CPU → sirf apni memory)
Communication	Implicit (load/store instructions)	Explicit (send/receive, MPI)
Synchronization	Locks, barriers (hardware atomic ops)	Messages synchronization carry karte hain (blocking receive)
Scalability	Memory bus se limited (≈ 8-64 cores typical)	1000s of nodes tak scale hota hai (network se limited)
Programming	Aasaan (threads, OpenMP)	Mushkil (message orchestration, deadlock risks)
Latency	Cache hit: ~1 ns, miss: ~100 ns	Message: ~1-50 μs (1000× slower)
Bandwidth	Memory bus: ~100 GB/s	Network: 10-200 Gbps (~1-25 GB/s)

Common mistake "Shared memory hamesha faster hoti hai kyunki koi message passing nahi"

Yeh sahi kyun lagta hai: Loads/stores explicit send() ke comparison mein "free" lagte hain.

Yeh galat kyun hai:

Cache coherence hidden message passing hai—hardware bus par invalidations bhejta hai, jiska limited bandwidth hota hai
False sharing: Do threads alag variables likh rahe hain ek hi cache line mein, line caches ke beech ping-pong karti hai (performance collapse)
NUMA effects: Multi-socket systems mein, "shared" memory ka non-uniform access time hota hai—local memory padhna fast hai, remote socket memory 2-3× slower hai (basically ek message)

Fix: Shared memory fine-grained, unpredictable communication ke liye jeetati hai (jaise parallel search tree). Distributed memory coarse-grained, bulk communication ke liye jeetata hai (jaise map-reduce, simulations).

Common mistake "Distributed memory synchronization khatam kar deta hai"

Yeh sahi kyun lagta hai: Koi locks nahi chahiye—sabke paas private data hai!

Yeh galat kyun hai:

Message passing hi synchronization hai—receive() tab tak block karta hai jab tak data na aaye
Deadlock message passing mein zyada aasaan hai: Process A B ke message ka wait kar raha hai, B A ke message ka wait kar raha hai → dono stuck
Aapko phir bhi phases coordinate karne ke liye barriers/reductions chahiye (jaise "sab iteration 10 finish karo iteration 11 shuru karne se pehle")

Example deadlock:

// Dono processes yahi execute karte hain:
send(data, other_rank);
receive(buffer, other_rank);  // ❌ Deadlock if send is blocking!

Fix: Non-blocking sends (isend) use karo ya sends/receives ko carefully order karo.

Recall Feynman Explanation (ELI12)

Imagine karo tum aur tumhare dost ek bada LEGO castle bana rahe ho.

Shared memory = Tum sab ek giant table ke aas-paas baithe ho jisme bich mein sare LEGO bricks hain. Koi bhi kisi bhi brick ko anytime utha sakta hai. Achha: Tum instantly dekh sakte ho doosron ne kya banaya aur unke bricks use kar sakte ho. Bura: Agar tum dono ek hi brick ke liye pahuncho, tum ladte ho! Aur agar 10 dost table ke aas-paas bheed lagate hain, tum constantly ek doosre se takraate ho. Distributed memory = Har kisi ko apni choti table milti hai alag kamron mein, apne bricks ke saath. Achha: Koi ladai nahi—tumhara apna space hai! Tumhare paas 100 dost ho sakte hain har apne kamre mein apna section banate hue. Bura: Agar tumhe ek blue brick chahiye aur tumhare dost ke paas hai, tumhe unke kamre mein jaana padega aur maangna padega (slow!). Aur tumhe plan karna padega: "Main tumhe apni red bricks dunga, tum mujhe apni blue bricks dena."

Choice tumhare LEGO castle design par depend karti hai. Agar sab ko constantly bricks share karni hain aur ek hi part change karna hai → shared table better hai (crowding ke bawajood). Agar sab independent towers banate hain aur sirf kabhi kabhi combine karte hain → alag kamre better scale karte hain.

Hybrid Models: The Real World

Modern systems dono combine karte hain:

Worked example Hybrid Shared-Distributed

Typical supercomputer node:

2 CPUs × 32 cores = 64 cores node ke andar memory share karte hain (256 GB RAM)
1000 aise nodes InfiniBand network se connected hain (nodes ke beech distributed) Programming model (MPI + OpenMP):

// Har node ek MPI process run karta hai
#pragma omp parallel for  // Node ke andar shared memory parallelism
for (int i = 0; i < local_size; i++) {
    local_array[i] = compute(i);
}
// Nodes ke beech distributed memory
MPI_Allreduce(&local_sum, &global_sum, 1, MPI_DOUBLE, MPI_SUM, MPI_COMM_WORLD);

Hybrid kyun? Dono worlds ka best—same node par threads ke liye low-latency shared memory, cross-node ke liye message passing (jahan latency waise bhi unavoidable hai).

Performance Models

Connections

Cache Coherence Protocols – MESI, MOESI, snooping vs directory
NUMA Architecture – Multi-socket shared memory mein non-uniform memory access
Message Passing Interface (MPI) – Distributed memory ke liye standard API
OpenMP – Directive-based shared memory parallelism
Interconnect Networks – Distributed systems ke liye topologies (torus, fat-tree)
Parallel Programming Models – Task parallelism, data parallelism, PGAS
Memory Consistency Models – Sequential consistency, release consistency
False Sharing – Shared memory mein cache line interference

#flashcards/hardware

What is the key difference between shared and distributed memory architectures? :: Shared memory: sare processors single global address space access karte hain (implicit communication loads/stores ke zariye). Distributed memory: har processor ki private local memory hoti hai, communication explicit message passing ke zariye.

Why does shared memory not scale beyond ~64 cores?

Memory bus bottleneck ban jaata hai—cache coherence traffic write contention mein O(N) se O(N²) tak badhta hai, bus bandwidth saturate ho jaati hai. Saath hi, coherence maintain karne ke liye shared data par har write ke liye remote caches ko invalidate karna padta hai.

Derive the message passing latency formula :: T_send = T_latency + M/B. T_latency message initiate karne ki fixed cost hai (OS overhead, network setup). M/B, M bytes ke liye bandwidth B par transmission time hai. Chhote messages ke liye latency dominate karti hai; bade messages ke liye bandwidth matter karti hai.

What is false sharing and why does it hurt performance?

False sharing tab hoti hai jab do threads alag variables likhte hain jo ek hi cache line mein hote hain (typically 64 bytes). Ek variable likhna doosre cores ke caches mein poori cache line invalidate kar deta hai, unnecessary coherence traffic aur cache misses cause karta hai—performance 5-10× girr sakti hai.

When should you choose distributed memory over shared memory?

Distributed memory tab choose karo jab: (1) ~64 cores se zyada scale karna ho, (2) communication coarse-grained ho (bulk data transfers, fine-grained random access nahi), (3) problem naturally independent subproblems mein decompose hoti ho (embarrassingly parallel), ya (4) ek single machine se zyada memory capacity aggregate karni ho.

What is the role of cache coherence protocols in shared memory?

Cache coherence protocols (jaise MESI) ensure karte hain ki sare caches memory ka consistent view dekhein. Jab ek core kisi cache line par likhta hai, protocol automatically doosre cores ke caches mein copies invalidate ya update karta hai—memory bus par yeh control messages broadcast karke. Yahi "hidden message passing" hai.

Why is MPI_Allreduce a common bottleneck in distributed systems?

Allreduce sare processes se values combine karta hai (jaise ML mein gradients sum karna) aur result sabko broadcast karta hai. Ise O(log N) communication rounds chahiye (tree-based algorithms) aur total O(N × message_size) data transfer hota hai. Latency aur bandwidth dono critical hain—jab frequent synchronization chahiye tab dominate karta hai.

What is NUMA and how does it blur the shared vs distributed boundary?

NUMA (non-uniform memory access) multi-socket systems mein hoti hai jahan CPUs ek address space share karte hain but "remote" memory access (doosre socket se attached) "local" memory se 2-3× slower hoti hai. Architecturally shared memory hai but performance characteristics distributed memory jaisi hain—programmers ko locality-aware rehna padta hai.

Explain the deadlock risk in distributed memory with an example :: Agar dono processes send(other); receive(other); karte hain aur send blocking hai, toh dono forever wait karte hain doosre ke receive karne ka pehle woh send kar sakein. Fix: non-blocking sends (MPI_Isend) use karo, pehle receives post karo, ya communications carefully order karo (jaise even ranks pehle send karte hain, odd ranks pehle receive karte hain).

What is a hybrid MPI+OpenMP model?

Inter-node communication ke liye MPI use karo (distributed memory) aur intra-node parallelism ke liye OpenMP threads (shared memory). Har node ek MPI process run karta hai multiple OpenMP threads ke saath. Nodes ke andar low-latency shared memory exploit karta hai aur nodes ke beech message passing ke zariye scale karta hai.

What Are These Architectures?