6.1.5 · D5Parallelism & Multicore
Question bank — Shared memory vs distributed memory
Recall First, the one-sentence anchors (peek only if the words below feel unfamiliar)
Shared memory = every processor can name and touch every byte with a plain load/store. Distributed memory = a processor can only touch its own bytes; to reach another's data it must send a message. Cache coherence = the hardware promise that if I write a value, no other cache keeps showing the old one. Latency = the fixed wait before any data arrives; bandwidth = how fast bytes stream once the pipe is open.
True or false — justify
Shared memory means there is literally only one physical bank of RAM in the machine.
False — it means one logical address space; NUMA machines have several physical memory banks, but every CPU can still address all of them (some just farther/slower). See NUMA Architecture.
In a distributed-memory system, a processor can read another processor's variable if it knows the address.
False — addresses are local; the same numeric address means different memory on each node. The only way in is an explicit message via Message Passing Interface (MPI).
Cache coherence removes the need for locks in shared-memory code.
False — coherence keeps individual cache lines consistent, but a read-modify-write like
x = x+1 is several operations; two threads can still interleave and lose an update. You need atomics/locks for that.Message passing is always slower than a shared-memory load.
True per operation (µs vs ns), but false as a system claim — shared memory hits a bus/coherence bottleneck past a few dozen cores, while message passing keeps scaling to thousands of nodes.
False sharing only happens when two threads write the same variable.
False — it happens when they write different variables that land in the same 64-byte cache line; the hardware invalidates the whole line, not the byte. See False Sharing.
OpenMP programs run on distributed-memory clusters without change.
False — OpenMP assumes a single shared address space (threads sharing memory); across separate nodes you need message passing. Hybrid MPI+OpenMP is the usual fix.
A distributed system has no cache coherence problem at all.
True for hardware coherence — each node's memory is private, so no cross-node invalidations. The equivalent burden reappears as the programmer's job of keeping replicated copies in sync via messages.
Increasing cores in a shared-memory machine always increases throughput.
False — beyond the point where the memory bus or coherence traffic saturates, adding cores adds contention, and throughput can flatten or even drop.
Spot the error
"Broadcasting matrix B to all nodes costs one message, so it's cheap."
To reach
N-1 other nodes you send N-1 messages (or a log-depth tree of them); each pays latency. It's paid once, but it is not a single message."Since each thread writes count[i] for a different i, there's no coherence traffic."
If the
count[] entries share a cache line, every write invalidates the others' copies — classic false sharing. Different index ≠ different cache line."To scale to 100 GPUs we just use one big shared-memory space over NVLink."
No single machine hosts 100 GPUs coherently; maintaining coherence across that many is impractical. You use distributed memory + AllReduce over the interconnect instead.
"Sending 1000 messages of 1 KB is the same cost as one message of 1 MB because the bytes are equal."
The bytes are equal but latency is per-message: 1000 × latency vs 1 × latency. For small messages latency dominates, so batching into one big message is far faster.
"In MSI, a write to a Shared line is free because copies already exist."
The opposite — a write to a Shared line must invalidate every other holder (up to
N-1 bus transactions). Being Shared makes the write expensive."A blocking receive() wastes time, so non-blocking is always better."
Non-blocking lets you overlap compute with communication, but it needs a later
wait/test and correct buffer management. Used carelessly it reads half-arrived data — "better" only if you actually overlap useful work.Why questions
Why does coherence traffic scale roughly as per contended write?
One writer must notify the other cache holders to invalidate their copies, so the message count grows with the number of processors sharing that line.
Why do MPI programmers deliberately batch communication?
Because has a fixed per-message latency term; fewer, larger messages amortize that fixed cost instead of paying it thousands of times.
Why is spatial locality (nearby addresses) a good thing for a single thread but a danger in shared memory?
For one thread, packing data into one line means fewer misses. For many threads writing nearby addresses, that same line becomes a coherence ping-pong — the closeness that helped one thread hurts several. See False Sharing.
Why can distributed memory keep scaling when shared memory stalls?
Distributed nodes have independent memories and no shared bus to serialize on; adding nodes adds bandwidth. Shared memory funnels everyone through one bus/coherence fabric that saturates.
Why does a weaker consistency model often make shared-memory hardware faster?
A weaker model lets the hardware reorder/buffer writes instead of making every write globally visible immediately, cutting stalls — at the price of the programmer inserting explicit fences where ordering truly matters.
Why is programming distributed memory considered harder than shared memory?
You must hand-orchestrate who sends what, when, and to whom, and mismatched send/receive pairs cause deadlock — work the shared-memory hardware does implicitly with loads/stores.
Edge cases
What happens on a shared-memory write when the line is already in Modified state in your own cache?
No invalidation is needed — you already hold the only up-to-date copy, so it costs ~1 transaction, not .
In distributed memory, what is the cost to communicate if two processes never share any data?
Zero communication cost — an embarrassingly parallel workload pays only local compute. This is the best case distributed memory targets.
On a NUMA machine, is every "shared" access equally fast?
No — accessing your local memory bank is fast; reaching a remote bank crosses the interconnect and is slower. It's still one address space, but with non-uniform latency. See NUMA Architecture.
What is the latency of a zero-byte MPI message?
Not zero — it's essentially , since the term vanishes but the fixed setup/OS/NIC overhead remains. This is how latency is often measured.
If a distributed AllReduce sums gradients across all nodes, what happens when just one node is slow (a straggler)?
The whole collective stalls — every node waits at the synchronization point until the slowest arrives, so one straggler throttles all. This is why load balance matters as much as raw speed.
What consistency does a single-core machine give for free that a multicore shared-memory machine does not?
Sequential consistency of its own program order is automatic on one core; with multiple cores, writes from different cores can appear in different orders unless the model and fences enforce it.