Foundations — Shared memory vs distributed memory

Before you can read a single formula in the parent note, you must know what each little symbol is a picture of. We build them one at a time, from nothing, in an order where each rests on the one before.

1. A processor (a worker)

We need this word because parallelism means "more than one worker at once". Everything downstream — sharing, messaging, bottlenecks — only appears once you have two or more workers.

The letter $N$ throughout the parent note simply means how many workers there are. When you see $O(N)$ or $O(N^2)$, read it as "how the cost grows as I add more workers".

2. Memory and an address

The parent note writes "a processor requests data at address A". That whole sentence is meaningless until you see memory as numbered boxes and an address as a box number. This is the object everyone is fighting over.

3. Address space — shared vs local

Why the topic needs this: this single difference — one street or many streets — is the entire fork between distributed and shared programming. In the comparison table, "Global address space" vs "Local address space" is literally this picture. See Parallel Programming Models for how each is programmed.

4. Cache — a scratchpad near the worker

The parent note's line "Is A in my private L1 cache?" is asking: do I already have a sticky-note copy? L1, L2, L3 are just increasingly bigger, slightly slower notebooks — L1 on your desk, L3 shared down the hall.

5. Cache line — the copy unit

6. Coherence — keeping the copies honest

The parent's MSI / MESI / MOESI are recipes for this shredding rule. The three MSI letters are just labels on your photocopy:

Why the topic needs coherence: it is the hidden message passing the parent's final "mistake" callout warns about — shared memory isn't magically free; the hardware is quietly mailing "shred your copy!" notes for you. Full recipes live in Cache Coherence Protocols and the rules on when a write becomes visible live in Memory Consistency Models.

7. The bus — the one shared hallway

Why this is the villain: with $N$ workers all writing shared data, the bus fills with invalidate traffic and becomes the bottleneck — the reason the parent says shared memory tops out at ~8–64 cores. When memory is instead split so different regions are "closer" to different cores, you get NUMA Architecture.

8. Message passing — the mailroom

The couriers and corridors between desks are the interconnect — see Interconnect Networks (Ethernet, InfiniBand).

9. Latency and bandwidth — the two costs of travel

Why both terms matter: for a tiny letter, all the time is shoe-tying ($T_{\text{latency}}\gg M/B$) — this is why the parent says to batch many small messages into one big one. For a huge crate, the corridor width $B$ dominates.

10. The two little "Big-O" phrases

This is the shorthand behind "coherence traffic grows as $O(N^2)$ in the worst case" — the mathematical reason shared memory stops scaling.

How the foundations feed the topic

Read top to bottom: workers own memory (boxes); how those boxes are addressed forks the design; caches make things fast but need coherence over a bus; the alternative is a mailroom priced by latency and bandwidth — and Big-O tells you which one survives many workers.

Equipment checklist

Cover the right side, answer, then reveal.