Shared memory vs distributed memory

Why This Distinction Matters

The problem being solved: When you split a computation across N processors, they need to share results. The architecture determines:

HOW data moves (implicit hardware vs explicit messages)
WHEN consistency is guaranteed (automatic vs programmer-controlled)
WHERE bottlenecks appear (memory bus vs network)

Shared Memory: The Implicit Communication Model

Formula Memory Access Time

$T_{\text{access}} = T_{\text{cache hit}} \cdot P(\text{hit}) + T_{\text{cache miss}} \cdot P(\text{miss})$ Derivation from first principles:

A processor requests data at address A
First check: Is A in my private L1 cache? (hit time ≈ 1-4 cycles)
If not: Is it in L2? L3? (≈ 10-40 cycles)
If not: Fetch from shared main memory via memory bus (≈ 100-300 cycles)
Coherence protocol (MESI, MOESI): Before writing, hardware broadcasts invalidation to other caches $T_{\text{write with coherence}} = T_{\text{cache write}} + T_{\text{invalidate broadcast}} + T_{\text{bus arbitration}}$

Why this formula matters: As cores increase, the memory bus becomes a bottleneck (serialization point). Cache coherence traffic grows as $O(N^2)$ in worst case (N cores all writing shared data).

Worked example Shared Memory in Action

Scenario: 4 threads updating a shared counter total.

// Thread 1, 2, 3, 4 all execute:
total = total + local_result;  // NOT atomic!

What happens under the hood (step-by-step):

Thread 1 reads total (value 100) into its cache
Thread 1 computes 100 + 5 = 105
Before Thread 1 writes back, Thread 2 also reads 100 (cache coherence hasn't kicked in yet if timing is unlucky)
Both write back105, losing one update!

Why this step (cache coherence)? The hardware's MESI protocol would normally invalidate Thread 2's cached copy when Thread 1 writes, but the read-modify-write isn't atomic. Fix: Use atomic operations (fetch_add) or locks.

Worked example Measuring Shared Memory Overhead

Experiment: False sharing penalty.

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

Prediction: Even though each thread writes a different index, if count[0] and count[1] are in the same cache line, writing count[0] invalidates Thread 1's cache of count[1].

Result: Performance drops by 5-10× compared to padding each count[i] to separate cache lines.

Why this matters: Shared memory makes spatial locality an enemy when multiple threads write nearby addresses.

Distributed Memory: The Explicit Communication Model

Formula Message Passing Latency

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

Where:

$T_{\text{latency}}$ = time to initiate message (setup, OS overhead)≈ 1-50 μs
$M$ = message size in bytes
$B$ = bandwidth of network (GB/s)

Derivation:

Step 1: Processor A calls send(data, size, dest_rank)
Step 2: OS copies data into network buffer (memory copy cost)
Step 3: Network interface card (NIC) packetizes and transmits over interconnect (Ethernet, InfiniBand)
Step 4: Destination NIC receives, interrupts Processor B, copies into receive buffer
Step 5: Processor B calls receive() to retrieve Why latency dominates: For small messages (< 1 KB), $T_{\text{latency}} \gg M/B$ . This is why MPI programs batch communications—sending 1 message of 1 MB is faster than 1000 messages of 1 KB each.

Worked example Distributed Memory: Matrix Multiplication

Scenario: Compute $C = A \times B$ where $A, B$ are $1000 \times 1000$ matrices split across 4 nodes.

Data distribution:

Node 0: rows 0-249of $A$
Node 1: rows 250-499 of $A$
Node 2: rows 500-749 of $A$
Node 3: rows 750-999 of $A$
All nodes need all columns of $B$ Communication pattern (step-by-step):

Broadcast $B$ : Node 0 sends full $B$ to all others (3 messages of ~1 MB each)
Local compute: Each node computes its chunk: C[my_rows, :] = A[my_rows, :] @ B
No further communication needed (embarrassingly parallel after broadcast)

$T_{\text{total}} = T_{\text{broadcast}} + T_{\text{compute local}} = \left(T_{\text{lat}} + \frac{1\text{ MB}}{B}\right) \cdot 3 + \frac{250 \cdot 1000^2}{FLOPS}$ Why this step (broadcast)? Unlike shared memory where $B$ would be in global memory, here we explicitly replicate it. Cost is paid once upfront.

Worked example When Distributed Memory Wins

Problem: Train a neural network with 100 GB parameters on 100 GPUs. Shared memory approach fails: No single machine has100 GPUs sharing memory. Even with NVLink, coherence across 100 GPUs is impractical.

Distributed memory approach:

Each GPU holds 1 GB of parameters (model paralelism) or full model but different data (data parallelism)
After each batch, GPUs exchange gradients via AllReduce (sum gradients across all GPUs)
Network: 100 Gbps InfiniBand, latency ~2 μs $T_{\text{AllReduce}} \approx 2 \log_2(100) \cdot T_{\text{lat}} + \frac{1\text{ GB}}{100\text{ Gbps}} \approx 14 \mu s +80 \text{ ms}$

Result: Scales to 100 GPUs because no shared bus bottleneck. Each GPU's memory is independent.

The Coherence Problem in Shared Memory

Formula Cache Coherence Overhead

For $N$ processors with private caches, maintaining coherence requires: $T_{\text{coherence}} = O(N) \cdot T_{\text{broadcast invalidate}}$

Why $O(N)$ ?

When Processor 1 writes to address X, it must send invalidate messages to all $N-1$ other caches
Each invalidate message uses shared memory bus bandwidth
Under heavy write contention, the bus saturates

Formal model (MSI protocol):

Modified (M): Cache has only up-to-date copy, memory stale
Shared (S): Multiple caches have read-only copies
Invalid (I): Cache line not valid State transition on write:

If cache line in S → broadcast invalidate, transition to M
If another cache in M → that cache writes back to memory, you transition to M $\text{Bus transactions per write} = \begin{cases} 1 & \text{if already M} \\ N & \text{if in S (must invalidate } N-1 \text{ caches)} \end{cases}$

Comparative Analysis

Aspect	Shared Memory	Distributed Memory
Addressing	Global address space (any CPU → any address)	Local address space (CPU → only own memory)
Communication	Implicit (load/store instructions)	Explicit (send/receive, MPI)
Synchronization	Locks, barriers (hardware atomic ops)	Messages carry synchronization (blocking receive)
Scalability	Limited by memory bus (≈ 8-64 cores typical)	Scales to1000s of nodes (limited by network)
Programming	Easier (threads, OpenMP)	Harder (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 "Distributed memory eliminates synchronization"

Why this feels right: No locks needed—everyone has private data!

Why it's wrong:

Message passing is synchronization—receive() blocks until data arrives
Deadlock is easier in message passing: Process A waits for B's message, B waits for A's message → both stuck
You still need barriers/reductions to coordinate phases (e.g., "everyone finish iteration10 before starting iteration 11")

Example deadlock:

// Both processes execute this:
send(data, other_rank);
receive(buffer, other_rank);  // ❌ Deadlock if send is blocking!

The fix: Use non-blocking sends (isend) or carefully order sends/receives.

Recall Feynman Explanation (ELI12)

Imagine you and your friends are building a huge LEGO castle.

Shared memory = You all sit around one giant table with all the LEGO bricks in the middle. Anyone can grab any brick anytime. Good: You can instantly see what others built and use their bricks. Bad: If you both reach for the same brick, you fight! And if 10 friends all crowd the table, you're constantly bumping into each other. Distributed memory = Everyone gets their own small table in different rooms, with their own pile of bricks. Good: No fighting—you have your own space! You can have100 friends each in their own room building their section. Bad: If you need a blue brick and your friend has it, you have to walk to their room and ask for it (slow!). And you need to plan: "I'll give you my red bricks, you give me your blue bricks."

The choice depends on your LEGO castle design. If everyone needs to constantly share bricks and change the same part → shared table is better (despite crowding). If everyone builds independent towers and only occasionally combines them → separate rooms scale better.

Hybrid Models: The Real World

Modern systems combine both:

Worked example Hybrid Shared-Distributed

Typical supercomputer node:

2 CPUs × 32 cores = 64 cores sharing memory within the node (256 GB RAM)
1000 such nodes connected by InfiniBand network (distributed across nodes) Programming model (MPI + OpenMP):

// Each node runs one MPI process
#pragma omp parallel for  // Shared memory paralelism within node
for (int i = 0; i < local_size; i++) {
    local_array[i] = compute(i);
}
// Distributed memory between nodes
MPI_Allreduce(&local_sum, &global_sum, 1, MPI_DOUBLE, MPI_SUM, MPI_COMM_WORLD);

Why hybrid? Best of both worlds—low-latency shared memory for threads on same node, message passing for cross-node (where latency is unavoidable anyway).

Performance Models

Connections

Cache Coherence Protocols – MESI, MOESI, snooping vs directory
NUMA Architecture – Non-uniform memory access in multi-socket shared memory
Message Passing Interface (MPI) – Standard API for distributed memory
OpenMP – Directive-based shared memory paralelism
Interconnect Networks – Topologies for distributed systems (torus, fat-tree)
Parallel Programming Models – Task parallelism, data parallelism, PGAS
Memory Consistency Models – Sequential consistency, release consistency
False Sharing – Cache line interference in shared memory

#flashcards/hardware

What is the key difference between shared and distributed memory architectures? :: Shared memory: all processors access single global address space (implicit communication via loads/stores). Distributed memory: each processor has private local memory, communication via explicit message passing.

Why does shared memory not scale beyond ~64 cores?

The memory bus becomes a bottleneck—cache coherence traffic grows as O(N) to O(N²) under write contention, saturating bus bandwidth. Also, maintaining coherence requires invalidating remote caches for every write to shared data.

Derive the message passing latency formula :: T_send = T_latency + M/B. T_latency is the fixed cost to initiate the message (OS overhead, network setup). M/B is the transmission time for M bytes at bandwidth B. For small messages, latency dominates; for large messages, bandwidth matters.

What is false sharing and why does it hurt performance?

False sharing occurs when two threads write to different variables that happen to be in the same cache line (typically 64 bytes). Writing one variable invalidates the entire cache line in other cores' caches, causing unnecessary coherence traffic and cache misses—performance can drop 5-10×.

When should you choose distributed memory over shared memory?

Choose distributed memory when: (1) you need to scale beyond ~64 cores, (2) communication is coarse-grained (bulk data transfers, not fine-grained random access), (3) the problem naturally decomposes into independent subproblems (embarrassingly parallel), or (4) you need to aggregate memory capacity beyond a single machine.

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

Cache coherence protocols (e.g., MESI) ensure all caches see a consistent view of memory. When one core writes to a cache line, the protocol automatically invalidates or updates copies in other cores' caches—using the memory bus to broadcast these control messages. This is "hidden message passing."

Why is MPI_Allreduce a common bottleneck in distributed systems?

Allreduce combines values from all processes (e.g., suming gradients in ML) and broadcasts the result to everyone. It requires O(log N) communication rounds (tree-based algorithms) and transfers O(N × message_size) total data. Latency and bandwidth are both critical—dominates when frequent synchronization is needed.

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

NUMA (non-uniform memory access) occurs in multi-socket systems where CPUs share an address space but accessing "remote" memory (attached to another socket) is 2-3× slower than "local" memory. It's architecturally shared memory but has performance characteristics of distributed memory—programmers must be locality-aware.

Explain the deadlock risk in distributed memory with an example :: If both processes do send(other); receive(other); and send is blocking, both wait forever for the other to receive before they can send. The fix: use non-blocking sends (MPI_Isend), post receives first, or carefully order communications (e.g., even ranks send first, odd ranks receive first).

What is a hybrid MPI+OpenMP model?

Use MPI for inter-node communication (distributed memory) and OpenMP threads for intra-node parallelism (shared memory). Each node runs one MPI process with multiple OpenMP threads. Exploits low-latency shared memory within nodes and scales across nodes via message passing.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek library mein bohot saare students baith kar padh rahe hain. Shared memory matlab sabke saamne ek hi bada table hai jismein sari books rakhi hain—koi bhi kisi bhi book kouthaa sakta hai instantly. Lekin problem yeh hai ki agar 50 studentsek hi table ke pas khade hon, toh dhaka-muki hogi aur sabko wait karna padega. Yeh hai memory bus ka bottleneck.

Distributed memory matlab har student apne pas ek choti table aur apni books rakhta hai. Ab koi interference nahi, har koi apni jagah par kaam kar raha hai peacefully. Lekin agar tumhe kisi aur student ki book chahiye, toh tumhe jake explicitly request karna hoga aur wo tumhe courier se bhejega—matlab slow messaging overhead. MPI, MapReduce ye sab distributed memory use karte hain taki thousands of machines ko coordinate kar sakein.

Aaj kal real systems hybrid use karte hain—ek node ke andar shared memory (threads), aur nodes ke bech distributed memory (network messages). Isse best of both worlds milta hai: local speed aur global scalability. CPU cores badhane hain toh eventually distributed memory ki taraf jana padta hai kyunki single memory bus sirf 64-100 cores tak hi handle kar sakta hai—uske bad coherence traffic itna zyada ho jata hai ki performance gir jati hai. Toh choice simple hai: small scale → shared, massive scale → distributed.

What Are These Architectures?

Why This Distinction Matters

Shared Memory: The Implicit Communication Model

Distributed Memory: The Explicit Communication Model

The Coherence Problem in Shared Memory

Comparative Analysis

Hybrid Models: The Real World

Performance Models

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Parallelism & Multicore

Connections