Shared memory vs distributed memory: Worked examples

This page is the drill ground for the parent topic. The parent told you the ideas; here we count every kind of question these ideas can throw at you, then solve one example for each. Nothing is hand-waved: every number is derived, every unit is checked.

Before we touch a single formula, one promise: I will not use a symbol until I have said, in plain words, what it means and drawn the picture it lives in.

The figure below draws exactly these two pictures side by side. Look at the left half: three cores (lavender circles) all reach into ONE butter-coloured memory with cheap two-way whisper arrows (coral) — but notice how crowded the single table is. Now the right half: each core owns its own mint memory box, and the only way to share is a one-way coral "letter" arrow between nodes. That left-vs-right contrast is the whole page in one image; every example below just puts numbers on one side of it.

Figure — Shared memory vs distributed memory

The scenario matrix

A "scenario" here = one shape of problem. If we solve one example per row, no exam question can surprise you. The table below names each cell in plain words only — the compact symbols $N$ (how many cores/caches), $M$ (message size in bytes) and $B$ (network bandwidth) are all defined immediately after, in "The three tools", before any example uses them.

#	Cell (case class)	What makes it distinct	Covered by
A	Shared, cache-hit dominated	Almost all accesses hit cache → tiny average time	Ex 1
B	Shared, coherence-storm	Many cores writing one line → bus floods with invalidations	Ex 2
C	Shared, degenerate: false sharing	Different variables, same cache line → hidden invalidations	Ex 3
D	Distributed, latency-bound (small msg)	Message so small the fixed stamp cost dominates	Ex 4
E	Distributed, bandwidth-bound (big msg)	Message so big the per-byte cost dominates	Ex 5
F	Distributed, collective (AllReduce)	Cost grows slowly (like a logarithm) with core count	Ex 6
G	Zero / limiting input	Empty message; single core; what do formulas say?	Ex 7
H	Crossover word problem	Real decision: pick shared or distributed for a task	Ex 8
I	Exam twist: mixed / trap	Setup that looks like it favours one but doesn't	Ex 9

We reuse three formulas from the parent, restated here so nothing is assumed.

Formula The three tools (each symbol defined in words)

Tool 1 — Average shared-memory access time. $T_{access} = T_{hit} \cdot P + T_{miss} \cdot (1 - P)$

$T_{hit}$ = time when the data was already in the fast cache (a "found it instantly" time).
$T_{miss}$ = time when we had to walk out to slow main memory (a "had to go fetch it" time).
$P$ = the hit rate: a fraction between $0$ and $1$ saying what share of accesses were lucky hits. $P = 1$ means always found, $P = 0$ means never.
The two pieces are a weighted average: reward the good outcome by $P$ , the bad by whatever is left, $1 - P$ .

Tool 2 — Point-to-point message time. $T_{send} = T_{lat} + \frac{M}{B}$

$T_{lat}$ = latency, the fixed "postage" you pay to start any message, even an empty one.
$M$ = message size in bytes (how thick the envelope).
$B$ = bandwidth, the wire's drain rate in bytes-per-second (how fast bytes leave).
$M / B$ = bytes divided by bytes-per-second = seconds. Units check: it is a time. Good.

Tool 3 — Coherence traffic on a write. $bus transactions per write = {1 N line already Modified in my cache line Shared across all N caches$

$N$ = number of processor caches holding a copy (the core count in play).
A bus transaction (a.k.a. bus message) here = one request placed on the shared coherence bus that all caches see — e.g. an invalidate ("drop your copy of this line") or a line transfer ("hand me the up-to-date line"). Counting transactions counts how many times the shared bus is occupied, which is what saturates it.
"Modified", "Shared", "Invalid" are the MSI states from the parent.

Cell A — Shared, cache-hit dominated

Worked example Ex 1 · The lucky-hit average

A core accesses memory with hit rate $P = 0.95$ . A hit costs $T_{hit} = 2$ ns, a miss costs $T_{miss} = 120$ ns. What is the average access time?

Forecast: Guess before reading. Closer to 2 ns or to 120 ns? (Hint: $95%$ of the time it's a hit.)

Step 1 — Split into the two outcomes. Hits happen a fraction $P = 0.95$ of the time; misses the remaining $1 - P = 0.05$ . Why this step? Tool 1 is just "weight each outcome by how often it happens" — a plain average.

Step 2 — Weight and add. $T_{access} = 2 (0.95) + 120 (0.05) = 1.9 + 6.0 = 7.9 ns$ Why this step? The rare miss (only $5%$ ) still contributes $6$ ns because it is $60 \times$ more expensive than a hit. The tail is heavy.

Verify: Sanity — the answer must lie between $2$ and $120$ . It does ( $7.9$ ). And because hits dominate, it sits near the low end. Units: ns throughout. ✓

Cell B — Shared, coherence-storm

Worked example Ex 2 · Bus traffic when everyone writes

$N = 8$ cores (recall $N$ = number of caches holding a copy) each hold a Shared read-only copy of one variable flag. All 8 then write to flag, one after another. How many invalidate bus messages total?

Forecast: Is it $8$ ? $8 \times 7$ ? Guess.

Step 1 — First writer. Core 1's line is Shared (others have copies). By Tool 3, it must invalidate the other $N - 1 = 7$ caches. That is $7$ bus transactions, and now only Core 1 holds the line (state Modified). Why this step? A write cannot proceed while stale copies exist elsewhere — coherence demands sole ownership.

Step 2 — Each later writer. Now the line lives Modified in exactly one cache. Core 2 wants it: Core 1 must hand it over (1 transfer). Now Core 2 is sole owner. Core 3 does the same, etc. There are $7$ such hand-offs (cores 2→3→…→8), each $1$ transaction. Why this step? After the storm settles to one owner, ownership just migrates — no more broadcast to 7 caches, because only one copy exists.

Step 3 — Total. $7 (first broadcast) + 7 (hand-offs) = 14 transactions$

Verify: Compare to a naive " $N$ per write $\times 8$ writes $= 64$ ". The real answer $14$ is far lower because after the first write nobody else has a copy to invalidate. The $O (N)$ -per-write bound in the parent is the worst case (when the line keeps being re-shared), not the steady state. ✓ This is consistency traffic made concrete.

Worked example Ex 3 · Two variables, one cache line

A 64-byte cache line holds an array of ints. Each int is 4 bytes. Thread 0 writes count[0]; Thread 1 writes count[1]. They share no logical data. Each ping-pong (invalidate + re-fetch of the whole line) costs $100$ ns, and they alternate $1000$ times. What is the wasted time, versus the ideal $2$ ns per write if there were no conflict?

Forecast: Should be near zero waste (different variables), right? Watch.

Step 0 — How many ints share the line? A 64-byte line at 4 bytes per int holds $64/4 = 16$ ints. So count[0] and count[1] are only 2 of the 16 slots — deliberately not padded. In real code you would pad each counter to its own 64-byte line (waste 60 bytes to keep them apart); here we intentionally leave them packed so both fall in the same line and collide. That packing is the whole point of the trap. Why this step? The bug only exists because the two variables are neighbours in one line; we must show they actually fit there before claiming they collide.

Step 1 — Recognise the trap. count[0] and count[1] sit in the same 64-byte line. Coherence works on whole lines, not individual ints. Writing count[0] marks the entire line Modified, invalidating Thread 1's copy of count[1]. Why this step? The hardware has no idea the two ints are logically independent — false sharing is coherence punishing spatial neighbours.

Step 2 — Count the ping-pongs. Each of the $1000$ alternations forces one line transfer at $100$ ns: $T_{false} = 1000 \times 100 = 100, 000 ns = 100 μ s$ Why this step? Every time the other thread touches the shared line, the line bounces back — so the count of expensive transfers equals the number of alternations, not the number of variables.

Step 3 — Compare to the ideal. " $1000$ alternations" means Thread 0 and Thread 1 each write $1000$ times, so $2 \times 1000 = 2000$ writes happen in total. If padded to separate lines, each of those $2000$ writes is a local hit at $2$ ns: $T_{ideal} = 2000 \times 2 = 4000 ns = 4 μ s$ $slowdown = \frac{100 , 000}{4000} = 25 \times$ Why this step? We must count both threads' writes ( $2000$ , not $1000$ ) to make a fair "same work" comparison; dividing actual by conflict-free time then isolates the pure penalty of false sharing.

Verify: Order-of-magnitude matches the parent's " $5 - 10 \times$ " range (we chose a harsher ping cost, giving $25 \times$ ). Units: ns → μs consistent. ✓ The fix is padding — the classic cache-line padding trick.

Cell D — Distributed, latency-bound (small message)

The next figure plots this exact idea. The horizontal axis is message size $M$ in bytes (log scale, running from $1$ byte on the left to $1 0^{9}$ bytes on the right); the vertical axis is total send time in microseconds (also log scale). Follow the lavender curve (total $T_{send}$ ): on the far left it hugs the coral dashed "latency floor" — that flat $5 μ s$ stamp is Ex 4's answer, marked with a coral dot. The mint dotted line is the pure per-byte term $M / B$ ; on the far right the lavender curve rides up along it — that steep region is Ex 5, marked with a mint dot. The legend names all three lines. Where the coral floor and mint slope cross is the "latency vs bandwidth" crossover — the whole distributed story in one plot.

Cell E — Distributed, bandwidth-bound (big message)

Worked example Ex 5 · A fat message (bit/byte trap)

Same network idea but a faster wire: $T_{lat} = 5 μ s$ , and the wire is quoted as $B = 100$ Gbps (gigabits/sec, $= 100 \times 1 0^{9}$ bits/s). We send $M = 1$ GB ( $= 1 0^{9}$ bytes). Time?

Forecast: Careful — Gbps is bits, GB is bytes.

Step 1 — Convert bandwidth to bytes/sec. $B = 100 Gbps = \frac{100 \times 1 0 ^{9} bits/s}{8 bits/byte} = 12.5 \times 1 0^{9} bytes/s$ Why this step? Divide by 8 or your answer is $8 \times$ too small — the classic exam trap flagged above.

Step 2 — Byte transfer time. $\frac{M}{B} = \frac{1 0 ^{9} bytes}{12.5 \times 1 0 ^{9} bytes/s} = 0.08 s = 80, 000 μ s$ Why this step? This is Tool 2's per-byte term again — but now $M$ is a billion bytes, so the term that was invisible in Ex 4 becomes enormous. Same formula, opposite regime.

Step 3 — Add latency. $T_{send} = 5 μ s + 80, 000 μ s = 80, 005 μ s \approx 80 ms$ Why this step? Tool 2 always adds the fixed stamp on top; here we do it just to show it is negligible ( $5$ out of $80, 005$ ), proving the message is bandwidth-bound.

Verify: Now $M / B ≫ T_{lat}$ — the fixed stamp is a rounding error. We are bandwidth-bound. This $80$ ms matches the parent's AllReduce estimate. ✓ Contrast with Ex 4: both messages obey the same Tool 2, opposite regime, decided purely by $M$ .

Cell F — Distributed, collective (AllReduce grows like log N)

Worked example Ex 6 · Summing gradients across 100 GPUs

An AllReduce combines a value from every one of $N = 100$ GPUs. To match the earlier examples we keep the same latency $T_{lat} = 5 μ s$ per hop. A tree-based AllReduce takes about $2 lo g_{2} (N)$ latency hops plus one payload pass of size $M = 1$ GB at $B = 100$ Gbps. Estimate the time.

Forecast: Does adding 100 GPUs cost $100 \times$ or only $lo g$ -times the latency?

Step 1 — Latency term. $2 lo g_{2} (100) \cdot T_{lat} = 2 \times 6.6439 \times 5 μ s \approx 66.4 μ s$ Why this step? A tree halves the group at each level, so it takes $lo g_{2} N$ levels — not $N$ . Each level costs one hop of the same $5 μ s$ stamp, so we multiply hops by $T_{lat}$ .

Step 2 — Payload term. From Ex 5, $1$ GB at $100$ Gbps $\approx 80$ ms $= 80, 000 μ s$ . Why this step? The gradients themselves still have to cross the wire once, so we reuse Tool 2's per-byte cost we already computed — no need to redo the division.

Step 3 — Total and interpretation. Add the two contributions: $T_{AllReduce} \approx 66.4 μ s + 80, 000 μ s = 80, 066.4 μ s \approx 80.07 ms$ Why this step? Total time is latency hops plus payload; adding them and comparing the two numbers ( $66.4 μ s$ against $80, 000 μ s$ ) shows which dominates — the payload, by a factor of about $1205 \times$ .

Interpretation: The latency term is a rounding error next to the $80$ ms payload, so for big gradients AllReduce is bandwidth-bound, and its cost is essentially the cost of moving the data once. The magic is the $lo g$ : because $lo g_{2} 100 \approx 6.6$ , jumping from $100$ to $1000$ GPUs adds only one more hop ( $\approx 5 μ s$ ), not $900 \times$ more latency.

Verify: Latency ( $\sim 66 μ s$ ) is over $1000 \times$ smaller than payload — payload dominates. Same order of magnitude as the parent's " $\approx 80$ ms" estimate, and total rounds to $80.07$ ms. ✓ This $lo g$ scaling is the scaling win of distributed collectives.

Cell G — Zero and limiting inputs

Worked example Ex 7 · What the formulas say at the edges

Test each tool at its degenerate input. These are the "trick zeros" exams love.

Case G1 — Empty message ( $M = 0$ ). $T_{send} = T_{lat} + \frac{0}{B} = T_{lat}$ Why? Even a zero-byte "ping" pays the stamp. Sending nothing still costs $T_{lat} = 5 μ s$ . This is why synchronization pings are not free.

Case G2 — Single processor ( $N = 1$ ). Coherence traffic: with only one cache, a write is always to a Modified line I already own → Tool 3 gives 1 bus transaction (in fact, no invalidations to send). No sharing means no coherence cost. A "parallel" machine with $N = 1$ has zero coordination overhead — the honest baseline.

Case G3 — Perfect hit rate ( $P = 1$ ). $T_{access} = T_{hit} \cdot 1 + T_{miss} \cdot 0 = T_{hit} = 2 ns$ Why? Every access hits; misses never happen; the average collapses to the hit time. Confirms Tool 1 behaves sanely at its boundary.

Case G4 — Perfect miss rate ( $P = 0$ ). $T_{access} = 2 (0) + 120 (1) = 120 ns$ The other extreme: pure misses give the pure miss time. The average always lives between these two poles ( $2$ and $120$ ).

Verify: All four edges give the physically obvious answer, so the formulas are trustworthy on the interior too. ✓

Cell H — Crossover word problem

Worked example Ex 8 · Which machine should you buy?

You have a task that does $R = 1 0^{6}$ shared-variable updates. On a shared machine each update (with coherence contention) averages $T_{s} = 150$ ns. On a distributed machine each "update" becomes a message of $M = 8$ bytes with $T_{lat} = 5 μ s$ , $B = 10$ GB/s. Which is faster, and why?

Forecast: Distributed "scales better", so it wins... or does it, for tiny frequent updates?

Step 1 — Shared total. $T_{shared} = R \cdot T_{s} = 1 0^{6} \times 150 ns = 1.5 \times 1 0^{8} ns = 0.15 s$ Why this step? Each update is independent and costs $T_{s}$ , so total time is just count times cost.

Step 2 — Cost of one distributed message. Using Tool 2 with $B = 10$ GB/s $= 1 0^{10}$ bytes/s: $\frac{M}{B} = \frac{8}{1 0 ^{10}} s = 0.0000008 μ s$ , so $T_{one msg} = 5 μ s + 0.0000008 μ s \approx 5 μ s$ Why this step? We must convert one shared update into its distributed equivalent — a message — before we can compare. It is latency-bound (cf. Ex 4), so the stamp is the whole cost.

Step 3 — Distributed total. $T_{dist} = R \cdot T_{one msg} = 1 0^{6} \times 5 μ s = 5 \times 1 0^{6} μ s = 5 s$ Why this step? Same "count times cost" logic as Step 1, now with the message cost, so the two machines are compared on identical footing.

Step 4 — Compare. $\frac{T _{dist}}{T _{shared}} = \frac{5 s}{0.15 s} \approx 33 \times slower$ Why this step? A ratio, not a difference, tells us how many times worse one choice is — the decision-relevant quantity.

Verify: For many tiny frequent shared updates, shared memory wins by ~33×. The message stamp ( $5 μ s$ ) is $33 \times$ the shared update cost ( $150$ ns), so the ratio had to come out near $33$ . The "distributed scales better" rule only kicks in when work per communication is large (Ex 5/6) — not here. ✓ This is the real engineering trade-off the parent's jigsaw metaphor points at.

Cell I — Exam twist / trap

Worked example Ex 9 · The "looks bandwidth-bound but isn't" trap

An exam asks: "Node A sends $N_{msg} = 1000$ separate messages of $M = 1$ KB $= 1000$ bytes each, $T_{lat} = 5 μ s$ , $B = 10$ GB/s $= 1 0^{4}$ bytes/μs. Total time? Now compare to sending it as one $1$ MB message."

Forecast: The data is $1$ MB either way — so same time? (Trap!)

Step 1 — Cost of 1000 small messages. Each: $T_{lat} + M / B = 5 + \frac{1000}{1 0 ^{4}} = 5 + 0.1 = 5.1 μ s$ . $T_{many} = 1000 \times 5.1 = 5100 μ s$ Why this step? You pay the $5 μ s$ stamp 1000 times. That is the whole trap.

Step 2 — Cost of one big message. $M = 1 0^{6}$ bytes: $5 + \frac{1 0 ^{6}}{1 0 ^{4}} = 5 + 100 = 105 μ s$ . Why this step? Batching pays the stamp once, so only the per-byte term grows — and the bytes are the same 1 MB either way.

Step 3 — Ratio. $\frac{5100}{105} \approx 48.6 \times faster to batch$ Why this step? The ratio exposes that the only difference is 999 extra stamps, which is the exam's whole point.

Verify: Same bytes ( $1$ MB total), wildly different time — because latency is paid per message, bandwidth per byte. Batching pays latency once. This is the parent's "batch communications" rule, quantified. ✓ It is the single most common vs MPI performance-tuning exam question.

Recall Self-test (answer before revealing)

The average access time formula weights hit and miss by what? ::: The hit rate $P$ and its complement $1 - P$ ; it is a weighted average, always between $T_{hit}$ and $T_{miss}$ . In Ex 2, why is the total 14, not 64? ::: After the first broadcast (7 invalidations) only one cache owns the line, so later writes just migrate ownership (7 hand-offs) — nobody else has a copy to invalidate. Why does false sharing (Ex 3) hurt even with independent variables? ::: Coherence acts on whole cache lines; two logically-separate ints in one 64-byte line ping-pong the line between cores. A zero-byte message costs how much (Ex 7)? ::: Exactly $T_{lat}$ — the fixed latency; you cannot send anything, even nothing, for free. In Ex 8, why does shared memory win? ::: For many tiny frequent updates, the message stamp ( $5 μ s$ ) dwarfs a shared update ( $150$ ns), making messaging ~33× slower. The batching win (Ex 9) exists because latency is paid per ___ and bandwidth per ___. ::: per message; per byte.