Shared memory vs distributed memory: Visual walkthrough

We are going to derive, from absolute zero, the total time a parallel program spends, and see exactly where shared memory and distributed memory pay their bills. Every symbol below is earned before it is used.

Prerequisites we will lean on (each is its own vault note): Cache Coherence Protocols, NUMA Architecture, Message Passing Interface (MPI), Interconnect Networks, False Sharing. This is the visual companion to the parent topic.

Step 1 — What is "one memory access", really?

WHAT. A processor (call it a core — one worker that runs instructions) needs a number that lives at some address. An address is just a house number in memory: "give me what's stored at location A". The time to fetch it is what we call $T_{access}$ .

WHY start here. Every parallel program is, underneath, millions of memory accesses. If we understand the cost of one, we can add them up. We cannot talk about "shared vs distributed" until we know what a single fetch costs.

PICTURE — figure s01. The core sits on the left. Its request travels rightward along a ladder: L1 cache (~1 ns) → L2/L3 (~10 ns) → main memory (~100 ns). Each rung to the right is slower but bigger. The caption on the axis reads "distance from core → slower, bigger", and the text under it reminds us that a hit means found early (fast) while a miss means we had to climb further (slow).

Figure — Shared memory vs distributed memory

This is a weighted average: we use a weighted average precisely because an access is sometimes fast, sometimes slow, and we want the expected (typical) cost. That is the one tool that answers "what does an access cost on average?"

Step 2 — Add a second core: the hidden cost appears

WHAT. Give the data to two cores at once. Both keep their own copy in their own cache. Now Core 1 changes the value. Core 2's copy is instantly wrong — stale.

WHY. This is the entire reason shared memory is hard. The moment two caches hold the same address, someone must police them so nobody reads a stale copy. That policing is cache coherence, and it is not free.

PICTURE — figure s02. Core 1's cache (top left) now holds X = 105 (new); Core 2's cache (bottom left) still holds X = 100 (stale); the shared bus and main memory sit on the right. A black arrow shows Core 1's write reaching the bus; the red arrow labelled "invalidate!" points at Core 2's cache — the hardware telling it "throw away your copy of X". That red arrow travels over the same bus the data uses.

The key realization: shared memory is message passing — the messages are just sent by hardware behind your back, over the memory bus.

Step 3 — Scale it: why the bus becomes a wall

WHAT. Put $N$ cores on one bus, all writing the same address. Each write must invalidate the other $N - 1$ caches — that is $N - 1$ invalidate messages, one per sharer.

WHY. We want to know how cost grows with $N$ , because "does it scale?" is the whole question of parallel computing. Growth rate is answered by big-O (defined at the top): here we ask whether the cost climbs like $N$ , like $N^{2}$ , or worse.

PICTURE — figure s03. The writer core sits at the top. Below it, $N - 1$ other caches line up on the one grey shared bus (drawn as a thick pipe). From the writer, $N - 1$ red invalidate arrows fan out, one to each other cache. Every arrow must squeeze through the single pipe — that pipe is the bottleneck, and the caption spells out "N-1 red invalidates → cost grows ~ O(N), all-write ~ O(N^2)".

Step 4 — The escape hatch: give each core its own memory

WHAT. Instead of one bus and shared caches, give every core its own private memory. Now Core 1 physically cannot touch Core 2's memory. No invalidate storms — because there is nothing shared to invalidate.

WHY. We are trading a hidden cost (coherence) for an explicit one (sending a message when you truly need someone else's data). Making the cost visible lets the programmer control it. This is the message-passing world.

PICTURE — figure s04. Two separated boxes. On the left, "Core A" sits above its own "memory A (private)"; on the right, "Core B" above "memory B (private)". There is no shared bus between them — the only link is a single orange arrow labelled "send / receive over network" crossing the gap. The text underneath states the moral: an explicit message means you control WHEN data moves.

Step 5 — What does one message cost?

WHAT. Sending $M$ bytes has two parts: a fixed setup cost that you pay no matter how tiny the message, plus a per-byte cost that grows with size.

WHY split it in two? Because the two parts behave completely differently as $M$ changes, and knowing which dominates tells you how to write fast code. That is the whole point of the next formula.

PICTURE — figure s05. A straight line on axes "message size M (bytes)" (horizontal) versus "time T_send" (vertical). The line does not start at zero — it starts at height $T_{lat}$ (marked by the orange dashed line, "T_lat: fixed toll"). From there it rises with slope $1/ B$ (the plum arrow labels this the "bandwidth region"). The flat-ish left end is where latency rules; the steep right end is where bandwidth rules.

Step 6 — Edge case: the message of size zero

WHAT. Set $M = 0$ . Then $M / B = 0$ , so $T_{send} = T_{lat}$ . A zero-byte message still costs the full latency.

WHY show this. It proves latency is a floor you can never dig below by shrinking data. Beginners assume "no data = no cost"; the formula says otherwise. Programs that send many tiny sync messages (like a barrier) pay $T_{lat}$ over and over.

PICTURE — figure s06. The same line as Step 5, but now with a highlighted orange dot sitting exactly at $M = 0$ . The dot is not on the horizontal axis — it floats at height $T_{lat}$ , and the annotation "M = 0 → T = T_lat (not 0!)" points straight at it. That vertical gap between the dot and zero is the unavoidable toll.

$M = 0 \Rightarrow T_{send} = T_{lat} + \frac{0}{B} = T_{lat} (\neq = 0)$

Step 7 — Edge case: the write that costs nothing (the M-state shortcut)

WHAT. Back in shared memory, suppose a core already owns the line privately (state M — see Step 3). It writes again. No other cache has a copy, so zero invalidate messages fire ( $k = 0$ in the Step 2 formula).

WHY show this. It is the best case of coherence, and it explains why single-threaded code and thread-private data run at full speed on shared memory: coherence only bites when data is actually shared between cores. It also sets up the trap in the summary — the villain is not sharing, it's unnecessary sharing.

PICTURE — figure s07. One core in the centre labelled "core owns X, state = M", sitting above the grey shared bus. There are no red arrows anywhere — the annotation reads "no other cache holds X → 0 red arrows", and below the bus the text notes "shared bus stays quiet". Silence on the bus is the whole point.

The one-picture summary

WHAT. One decision plot. Horizontal axis = how much cores must communicate. As sharing rises, shared memory's coherence cost climbs (the bus saturates), while distributed memory holds a steadier — but latency-floored — cost. Where the two curves cross is the crossover: below it, shared wins; above it, distributed wins.

PICTURE — figure s08. Axes "how much cores must communicate →" (horizontal) versus "total time" (vertical). The orange curve (shared memory) starts low but bends sharply upward — its coherence cost grows super-linearly as sharing rises. The teal curve (distributed memory) starts higher (it pays a latency floor even for light communication) but rises only gently. They meet at a plum dot labelled "crossover". The region left of the dot is labelled "shared wins"; the region right of it "distributed wins".

Recall Feynman retelling — say it back in plain words

Imagine two ways to run a workshop. In the shared-table shop, every worker sees the same board. Cheap when they mostly ignore each other — but the moment two grab the same tool, a rule forces everyone to yell "drop your copy!" and that yelling clogs the one hallway (the bus). More workers on the same tool → more yelling → gridlock. And it's not only changing a tool that causes chatter: even fetching a tool someone else just changed needs a round of "hand it over" messages (the read-miss and upgrade traffic of Step 3). In the separate-tables shop, each worker has their own private board. Nobody can grab someone else's tool by accident — but to share, you mail a package. Mailing has a fixed post-office toll ( $T_{lat}$ ) plus a per-pound cost ( $M / B$ , using the speed you actually see, not the brochure's peak). Even an empty envelope costs the toll (Step 6), so you batch — send one big package, not a thousand tiny ones. The winner? If your workers rarely share, the shared table is fastest. If they share a lot — or you have hundreds of workers — the yelling drowns the shared table, and the mail-based shop wins. And watch out for the sneaky tax (Step 7): two workers using tools that happen to sit in the same drawer trigger the "drop your copy!" rule even though they never wanted the same tool. Space the tools out.

Recall Quick self-test

What does a zero-byte message cost, and why? ::: The full latency $T_{lat}$ — the setup toll is fixed and independent of size, so shrinking data to nothing never removes it. How many invalidate messages does one write to a Shared line send, and what is the total worst-case growth when all N cores write it? ::: One write sends $N - 1$ invalidates (one per other sharer), giving $O (N)$ per write; all $N$ cores hammering it gives $N \cdot (N - 1)$ total, i.e. $O (N^{2})$ . When is a shared-memory write essentially free? ::: When the cache already owns the line in Modified (M) state — no other cache holds a copy, so it sends 0 invalidates. Besides writes, name one read-side action that still costs coherence traffic. ::: Reading a line held in Invalid state (a read-miss refill), or upgrading a Shared line to writable — both need bus messages.