Flynn's Taxonomy & Memory Models
Session 02 • 2311CSC501J — Parallel Processing
What You'll Learn
- Flynn's four classes: SISD, SIMD, MISD, MIMD
- SPMD — how real parallel programs are written
- Shared vs distributed memory (UMA / NUMA)
- Which model maps to OpenMP, MPI, and CUDA
"Two lenses for any parallel machine: sort it by its streams, then by how it shares memory. Do both, and you already know which tool to reach for."
— The whole session in one line
Flynn's Big Idea: Count the Streams
In 1966, Michael Flynn asked a beautifully simple question. Forget the details of any chip — just ask two things:
1. Instruction streams?
How many sequences of commands run at once — Single or Multiple?
2. Data streams?
How many data items are being acted on at once — Single or Multiple?
Two questions × two answers = a clean 2×2 grid with four categories. Every machine ever built lands in exactly one. Decode the letters: S/M Instruction, S/M Data — and each name explains itself.
The 2×2 Matrix
| Single Data | Multiple Data | |
|---|---|---|
| Single Instruction | SISD plain sequential machine |
SIMD one op, many data items (GPU) |
| Multiple Instruction | MISD rare — redundancy / voting |
MIMD independent processors (the common case) |
Don't memorize — decode. SIMD = Single Instruction, Multiple Data. Say the letters, get the meaning for free.
The Four Categories
SISD
One instruction on one data item, one at a time. The classic sequential machine.
One chef, one recipe, one dish.
SIMD
One instruction on many data items at once. The heart of GPUs and data parallelism.
A drill sergeant's one command; 100 soldiers, 100 rifles.
MISD
Many instructions on the same data. Rare — fault-tolerant, voting systems.
Several inspectors check one product different ways.
MIMD
Independent processors, own instructions on own data. The common case — your laptop is here.
An office where everyone does a different task.
Watch: Flynn's Taxonomy & Real Examples
A clean walk through the four categories — a good reinforcement after the matrix.
| Category | Real example |
|---|---|
| SISD | Old single-core CPU running a simple program |
| SIMD | GPU shading pixels; CPU vector units (SSE / AVX) |
| MISD | Space Shuttle redundant flight computers (voting) |
| MIMD | Multicore CPUs, clusters, supercomputers |
SPMD: What Real Programs Do
Nobody hand-writes a different program for each processor. Instead, real parallel code uses one pattern:
SPMD — Single Program, Multiple Data
Every processor runs the same program, on different data, and each can branch differently using its own rank / ID.
if (my_rank == 0):
read the file, hand out the chunks
else:
wait for my chunk, then process it
# One program. Rank 0 takes a different path than rank 7.MPI and OpenMP programs are SPMD. SPMD is a practical special case of MIMD — not a fifth Flynn category. Flynn classifies the hardware; SPMD is how we write software for it.
Shared Memory: One Fridge
New lens: forget streams — ask how do processors share data? First answer: they all share one pool of RAM. Core 3 writes x=5, core 7 sees it. Just use threads.
Analogy: roommates sharing one fridge. Grabbing food is easy — it's all right there. But you bump into each other, and two people reaching for the last egg at once = a collision (a race condition, Unit III).
Pro
Simple mental model — threads just share variables. No explicit data movement.
Con
Doesn't scale past tens of cores; needs cache coherence (Session 05).
UMA vs NUMA: Every Fridge Equidistant?
UMA
Uniform Memory Access. Every core reaches all memory in the same time. Classic SMP — your laptop.
Every fridge is the same few steps away.
NUMA
Non-Uniform Memory Access. Memory is attached to sockets: local = fast, remote = slower. Every multi-socket server.
Your fridge is here; your roommate's is across town.
NUMA is why "just add more CPUs to one box" eventually stops helping. Past a point, cores spend their time reaching across sockets for remote memory. It's the physics behind the ceiling on vertical scaling.
Watch: What Is NUMA?
AKIO TV — a friendly visual of why local and remote memory differ in speed.
Shared memory is easy to program but hard to scale. When one box can't grow anymore, you're forced to a completely different model — each processor with its own memory.
Distributed Memory: Own Houses
Each processor has its own private memory. No one can touch another's memory directly — the only way to share is to send a message over a network. That is exactly what MPI does.
Analogy: everyone has their own fridge in their own house. To share food you must phone and deliver. More coordination — but you can add houses forever.
Pro
Scales massively — thousands of nodes. Clusters and supercomputers.
Con
Programmer must explicitly move data; more complex to write and debug.
Shared = easy to program, hard to scale. Distributed = hard to program, scales without limit.
Hybrid: The Modern Reality
Real supercomputers are both: a cluster of nodes on a fast network (distributed), where each node is a shared-memory multicore machine, usually with a GPU. Every modern supercomputer is hybrid.
Analogy: a neighborhood of shared houses. Inside each house, roommates share one fridge (shared memory); between houses, you phone and deliver (distributed memory). Three tools, one program.
Model → Tool: The Bridge to Unit IV
The payoff: the memory model tells you which tool to use. Classify the machine, then pick the tool. That's the whole workflow.
| Model / hardware | Programming tool |
|---|---|
| Shared memory (one box, many cores) | OpenMP / threads |
| Distributed memory (cluster, many boxes) | MPI (message passing) |
| GPU / SIMD (data parallel) | CUDA |
| Hybrid (cluster of multicore + GPU nodes) | MPI + OpenMP + CUDA |
Everything technical in Unit IV is just learning to drive these three tools. Today you learned when to use each; later you learn how.
Recap & What's Next
Key Takeaways
- Flynn sorts by streams: SISD, SIMD (GPUs), MISD (rare), MIMD (the common case).
- SPMD = one program, branch by rank — how real MPI/OpenMP code is written (a case of MIMD).
- Shared memory = one pool of RAM (UMA/NUMA); easy, but hits a scaling ceiling.
- Distributed memory = private memory + messages (MPI); harder, but scales forever. Hybrid = both.
- The memory model picks the tool: OpenMP, MPI, or CUDA.
Homework
- Explain "one big computer vs a thousand small computers" (shared vs distributed) to a non-technical friend.
- Is your laptop UMA or NUMA? Confirm a multi-socket server is NUMA.
- Come ready: "If shared memory is so easy, why do supercomputers still use distributed memory between nodes?"
Next session: Parallel Programming Models
We stop classifying and start doing — your first OpenMP program.