Reference · Hardware and programming models

A map of parallel machines and programs

"SIMD" and "SPMD" are two answers to two different questions. SIMD is one way hardware can run many operations at once; SPMD is one way to write a program that has many operations to run. There are several of each, and any real system mixes them. This page lays them all out, using the same small job for every machine and the same small computation for every programming model, so you can compare them side by side.

You'll be able to: Place any parallel machine in Flynn's taxonomy and say where it doesn't fit. Predict how the same loop runs on a scalar core, SIMD, a vector unit, multiple cores, SMT, a GPU warp and a VLIW bundle, including what a branch does to each. Explain systolic arrays, dataflow and spatial hardware. Recognize ten programming models by their code, and say which hardware each maps onto naturally.
Background: Units 3–5 of these notes and CS149 Lectures 2–3. Each section links to the lesson that covers the idea in depth.

Keep asking two separate questions: how does the hardware get many operations done at once? and how does the program express that there are many operations? A compiler or runtime maps the second onto the first, and the same program can run on very different machines.

Section 1

Two separate questions, one mapping

A programming model is the abstraction you write in: what "parallel" looks like in the code, how work is divided, and how the pieces communicate. A hardware organization is what physically executes instructions: how many instruction streams there are, and how many data elements each instruction touches. Between them sits a compiler, runtime or library that maps one onto the other.

Many-to-many. The same model can target different hardware: an SPMD program in ISPC compiles to SIMD lanes, while the same style in CUDA runs on GPU warps and in MPI runs across whole machines. And the same hardware runs many models: a multicore CPU happily runs threads, fork-join tasks, message passing or a SQL engine. The arrows show a few of the common pairings.

Section 2

Hardware, first cut: Flynn's four boxes

In 1966 Michael Flynn classified machines by two counts: how many instruction streams (program counters driving execution) and how many data streams (sets of operands being worked on). Each count is one or many, which gives four boxes. Click a box to see what it means.

I = instruction stream, D = data stream, PU = processing unit. The taxonomy is old and coarse, but still useful for a first question: is there one program counter or many, and does each instruction touch one value or many?

Real chips are combinations. A laptop CPU is MIMD across its cores and SIMD inside each core. A GPU is MIMD across its streaming multiprocessors and SIMD-like within each warp. The next section runs one job on seven concrete organizations to show the differences Flynn's boxes hide.

Section 3

The same job on seven machines

The job: compute y[i] = a[i] × b[i] + c for eight elements, y0 … y7. Each element is one multiply-add, and the eight are independent. Every machine below has enough hardware to do some of them at once; what differs is who decides what runs together and how many instructions it takes. Pick a machine, then switch on the branch.

Each row is a piece of execution hardware, each column a clock cycle. A labelled cell is useful work on one element; a hatched cell is a slot that was occupied but did nothing useful (a masked lane or a predicated-off operation). With the branch on, elements y1, y2 and y5 take the "else" path. Teaching model: one operation per slot per cycle, no memory delays, and no loop or branch instructions counted.

Machine	Who picks what runs together?	Where you meet it	Covered in
Scalar (SISD)	nobody: one operation at a time	the baseline of every CPU core	Unit 1
SIMD	the programmer or compiler, writing wide instructions	x86 SSE/AVX, Arm NEON	Unit 4 · L19
Vector	the compiler; the hardware picks how many elements per beat	RISC-V V, Arm SVE, classic Cray machines	Unit 4 · L19
Multicore (MIMD)	the programmer or runtime, by starting threads	every modern CPU	Unit 4 · L16
SMT	the hardware, each cycle, from the resident threads	Intel Hyper-Threading, IBM POWER	Unit 4 · L18
SIMT (GPU warp)	the hardware groups scalar threads into warps	NVIDIA and AMD GPUs	Unit 5
VLIW	the compiler, packing independent operations into bundles	DSPs (e.g. Qualcomm Hexagon), Itanium	this page

Section 4

Beyond the four boxes: data moves, not instructions

Every machine in Section 3 fetches instructions and reads operands from registers. Three important designs work differently: they cut down instruction fetch and register traffic by letting data flow through a fixed arrangement of arithmetic units.

Systolic arrays: a grid that pumps data

A systolic array is a grid of simple multiply-add cells, each connected only to its neighbours. Values enter at the edges and pulse one cell per clock, like blood through a heart (hence "systolic"). Each value is used by every cell it passes through, so one value read from memory feeds many operations. Google's TPU uses a large systolic array for matrix multiplication. Step through a 3 × 3 matrix product C = A × B:

Output-stationary systolic array. Cell (i, j) keeps a running sum for C[i][j]. Row i of A enters from the left, delayed by i clocks; column j of B enters from the top, delayed by j clocks. The delays ("skew") make A[i][k] and B[k][j] arrive at cell (i, j) in the same clock. Each cell passes its A value right and its B value down. After 7 clocks all nine outputs are complete: 27 multiply-adds with each input value read from memory only once.

Dataflow: fire when the inputs arrive

A dataflow machine has no program counter. The program is a graph; each operation fires as soon as all its inputs are available, and its result travels as a token to the operations that need it. Independent operations fire in the same step automatically. Pure dataflow computers were a research direction in the 1970s–80s; today the idea lives on inside out-of-order cores (Unit 3), which run a small window of instructions in dataflow order, and in several AI accelerators that map whole computation graphs onto hardware.

r = (a + b) × (c − d) + e × f with a = 2, b = 3, c = 7, d = 4, e = 5, f = 2. Five operations, but only three steps: the graph's depth, not its size, sets the time when there's enough hardware. A sequential core would take five steps, one per operation.

Spatial hardware: build the circuit for the loop

FPGAs (field-programmable gate arrays) and CGRAs (coarse-grained reconfigurable arrays) go further: instead of running instructions, you configure the chip into a circuit shaped like your computation. For y = a × b + c that's a multiplier wired to an adder, with registers between them so each stage can work on a different element.

No instruction fetch, no decode, no register file. After the pipeline fills, one finished element leaves every clock, and a new one enters. The price is flexibility: changing the computation means reconfiguring the hardware, which takes far longer than loading a new program. FPGAs are common in networking, signal processing and prototyping chips; clock rates are lower than CPUs', so the win comes from doing exactly the needed work in parallel.

Design	What replaces instruction fetch	Strength	Weakness
Systolic array	a fixed grid; data pulses cell to cell	huge reuse for matrix multiply; tiny control cost	good only for regular, dense linear algebra
Dataflow	operations fire when their input tokens arrive	finds all the parallelism in a graph automatically	matching tokens to operations is costly in general-purpose hardware
Spatial (FPGA, CGRA)	a circuit configured for this computation	exactly the needed operators, deeply pipelined	slow to reconfigure; harder to program

Section 5

Programming models: ten ways to write the same computation

Now the other question. The computation: the sum of squares of eight numbers, x = [3, 1, 4, 1, 5, 9, 2, 6]. The answer is 9 + 1 + 16 + 1 + 25 + 81 + 4 + 36 = 173. It has two parts every parallel program must handle: independent work (squaring each element) and combination (adding the results), which forces the workers to communicate. Pick a model and compare its code with the picture of how it divides the work.

Same answer, 173, every time. What changes is who divides the work (you, a runtime, or a compiler), whether workers share memory or send messages, and how the partial sums meet. Colours mark which worker handles each element.

Section 6

Mix and match: which model runs on which machine

Models and machines aren't paired one-to-one. The table shows typical, real pairings; a blank cell means the combination is unusual, not impossible.

Model ↓ · Hardware →	SIMD / vector unit	GPU (SIMT)	Multicore CPU	Cluster of machines
SPMD	ISPC, OpenMP `simd`	CUDA, HIP, OpenCL	ISPC tasks, OpenMP	MPI programs are usually SPMD
Shared-memory threads			pthreads, `std::thread`, Java
Fork-join tasks		CUDA dynamic parallelism (rare)	Cilk, TBB, Java ForkJoin, OpenMP tasks	Ray, Dask
Data-parallel operations	NumPy's vectorized kernels	PyTorch, CuPy, Thrust	NumPy, parallel STL	Spark, Dask arrays
Message passing		NCCL collectives between GPUs	MPI on one node, actors (Erlang, Akka)	MPI, actors
Dataflow / graph	XLA fusing into vector code	JAX/XLA, TensorFlow, CUDA Graphs	TensorFlow, Halide	Apache Beam, TensorFlow distributed
Pipeline		CUDA streams overlapping copy and compute	Unix pipes, Go channels, TBB flow graph	pipeline-parallel model training
BSP		kernel-by-kernel phases	OpenMP loops with barriers	MPI iterations, Pregel
Declarative	vectorized database engines	GPU databases	SQL databases, DuckDB	distributed SQL, MapReduce

Most real programs stack several. A typical training job uses data-parallel tensor operations, which a graph compiler fuses into SPMD kernels for a SIMT GPU, with message-passing collectives between GPUs in a BSP rhythm and a pipeline of copies overlapping compute (Unit 6). Recognizing each layer tells you where to look when something is slow.

Check yourselfName the hardware or the model, then say why.

A loop has a data-dependent branch that splits elements roughly half and half. Which machines from Section 3 slow down, and which don't?
Show answer
SIMD, vector, SIMT and predicated VLIW slow down: they share one instruction stream across elements, so both paths run with masks and half the slots are wasted. Scalar, multicore and SMT don't, because each instruction stream follows only its own element's path.
Is SMT a kind of SIMD?
Show answer
No. SMT runs several instruction streams (it's MIMD in Flynn's terms) that share one core's execution units. SIMD runs one instruction stream over many data elements. A core can have both at once.
Why can a systolic array do a matrix multiply with far fewer memory reads than a scalar core?
Show answer
Each value read from memory enters the grid once and is reused by every cell it passes: in a 3 × 3 array, each A and B value takes part in three multiply-adds. A scalar core would reload operands from registers or cache for every multiply-add.
An MPI program starts the same executable on every rank, each branching on its rank number. Which programming model is that?
Show answer
SPMD, communicating by message passing. The two aren't exclusive: SPMD says how the program is structured (one program, many instances), message passing says how the instances share data.
Your sum-of-squares code is np.sum(x * x). Who decided how to parallelize it?
Show answer
The library (NumPy and its compiled kernels), not you. That's the data-parallel model: you describe whole-array operations, and the implementation chooses the SIMD instructions, loop order and (in some libraries) threads.

For any parallel system, name the programming model you write in, the hardware organization it runs on, and the layer (compiler, runtime or library) that maps one onto the other.

Back toCourse map RelatedCS149 L3 · Abstraction vs implementation →