Exercises — Shared memory vs distributed memory

(a) Shared. One physical memory, all 8 cores read/write the same global address space directly. (b) Distributed. Each node has its own private memory; nodes talk by passing messages. (c) Distributed. VMs cannot touch each other's RAM; the only channel is the network.

Rule of thumb: Can core X read core Y's data with a plain load instruction? Yes → shared. Only by sending a message → distributed.

This is distributed memory — communication is explicit (you literally name the operation). In shared memory the equivalent is implicit: A simply does x = 5; and B later does read x. No send/receive appears — the hardware moved the data for you (via the cache-coherence protocol). See Parallel Programming Models.

$P(\text{miss})=1-0.95=0.05$. $T_{\text{access}}=1\cdot 0.95+100\cdot 0.05=0.95+5.0=5.95\text{ ns}$ What it means: even though 95% of accesses are fast, the rare 5% of slow misses dominate the average (5.0 of the 5.95 ns). Misses are the enemy.

Transfer time per byte-batch is $M/B$. With $B=10^{10}$ bytes/s:

One big message: $M=10^6$ bytes. $T=10\mu s+\frac{10^6}{10^{10}}\text{ s}=10\mu s+100\mu s=110\mu s.$

1000 small messages: each pays its own $T_{\text{lat}}$. $T=1000\left(10\mu s+\frac{10^3}{10^{10}}\text{ s}\right)=1000(10\mu s+0.1\mu s)=10100\mu s.$

The batched version is $\approx 92\times$ faster. Why: the fixed latency $T_{\text{lat}}$ is paid per message, so slicing your data into 1000 pieces pays it 1000 times. This is why MPI programs batch — see the parent note. Related: Interconnect Networks.

Invalidates needed $=N-1$. For $N=8$: $8-1=7$ messages. Serialized on one bus: $T=7\times 30\text{ ns}=210\text{ ns}.$ Why $N-1$ and not $N$: the writer already owns its own copy — it only needs to silence the other caches. This $O(N)$ growth is exactly why shared-memory bus machines top out around 8–64 cores. See Cache Coherence Protocols.

This is False Sharing. All 8 counters live in one cache line. Coherence tracks whole lines, not individual bytes. So when Thread 0 writes count[0], the hardware invalidates that line in every other thread's cache — even though nobody else touched count[0]. Each write ping-pongs the line across all cores.

What it looks like: the line bounces core→core→core on every update, turning 8 independent writes into a fully serialized coherence storm (parent reports 5–10× slowdown).

Fix: pad each counter to its own cache line:

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

Now writes hit different lines → no cross-invalidation.

One message of $1\text{ MB}=10^6$ bytes: $T_{\text{one}}=10\mu s+\frac{10^6}{10^{10}}\text{ s}=10+100=110\mu s.$ Three sequential sends (Node 0 → Nodes 1,2,3): $T_{\text{broadcast}}=3\times 110\mu s=330\mu s=0.33\text{ ms}.$ Compare to compute $=50\text{ ms}$. Communication is only $0.33/50\approx 0.66\%$ of runtime. Conclusion: computation dominates — this problem is "embarrassingly parallel" after the one-time broadcast. Pay $B$'s transfer once, then crunch. This is distributed memory at its best.

Latency term: $2{\log }_2(100)\cdot 2\mu s$. Since ${\log }_2(100)\approx 6.644$: $2\times 6.644\times 2\mu s\approx 26.6\mu s.$ Bandwidth term: $\frac{8\times 10^9\text{ bits}}{10^{11}\text{ bits/s}}=0.08\text{ s}=80\text{ ms}.$ $T_{\text{AllReduce}}\approx 0.0266\text{ ms}+80\text{ ms}\approx 80\text{ ms}.$ Bandwidth dominates utterly (80 ms vs 0.027 ms). For huge messages, $M/B\gg T_{\text{lat}}$ — the exact opposite of Exercise 2.2 where tiny messages made latency king. The lesson: message size decides which term wins.

Design: hybrid MPI + OpenMP.

• Inside a node (32 cores): shared memory. Use OpenMP threads sharing one address space — communication is free implicit loads/stores, no message overhead.
• Across nodes (64 nodes): distributed memory. Use MPI: one MPI rank per node, ranks exchange messages.

Why not threads-everywhere? You cannot — 64 separate machines have no shared address space; a thread on node 0 physically cannot load node 5's RAM. Shared memory does not span the network.

Why not MPI-everywhere (2048 ranks)? It works, but wastes the shared memory inside each node: cores on the same node would copy data through message buffers instead of just reading it directly. You'd pay 32×64 = 2048 ranks of coherence-free-but-copy-heavy traffic and needless memory duplication. Hybrid uses the right tool per level: implicit sharing where memory is shared, explicit messaging only where it must cross the network. See NUMA Architecture and Memory Consistency Models.

Steel-man: In shared memory, writing a variable secretly triggers invalidate broadcasts to $N-1$ caches (Ex 3.1). Those invalidations are messages on the bus — you just never wrote send(). So shared memory hasn't abolished communication; it has hidden and automated it. When the hidden traffic saturates the bus, shared memory stops scaling — the same wall distributed memory faces, only invisible.

Distributed memory gives up: the convenience of implicit communication + automatic consistency — the programmer must now orchestrate every transfer and risk deadlock. Distributed memory keeps (and this is the win): independent, non-shared memory — no single bus every core fights over. That is why it scales to thousands of nodes while shared memory stalls at tens of cores.

Latency dominates message time when the message is ::: small (so $M/B$ is tiny next to $T_{\text{lat}}$). A write from MSI state S must send this many invalidates among $N$ cores ::: $N-1$. The unit of false sharing is the ::: cache line (~64 bytes), not the variable. The interface that decides shared vs distributed ::: load/store (implicit) vs send/receive (explicit).