Flynn's taxonomy (SISD - SIMD - MIMD): Worked examples

This page is the drill-room for Flynn's taxonomy (SISD - SIMD - MIMD). The parent note built the ideas; here we push a number through every kind of situation the taxonomy can throw at you — from the friendly "just count cycles" case, to the nasty zero-and-degenerate cases (what if a task cannot be parallelised at all?), to the limiting case (what if you had infinite cores?).

The scenario matrix

Every worked example below is tagged with the cell it covers. Together they fill the whole grid.

Cell	Case class	What makes it tricky	Example
A	SISD baseline	serial, one instruction, one datum	Ex 1
B	SIMD ideal	independent data, full $N \times$	Ex 2
C	SIMD ragged	data count not a multiple of lanes	Ex 3
D	SIMD dependency (degenerate)	a dependency kills parallelism	Ex 4
E	MIMD task-parallel	different code per core	Ex 5
F	Amdahl, ordinary $P$	mixed serial + parallel	Ex 6
G	Amdahl, $P = 0$ and $P = 1$ (extremes)	the two degenerate fractions	Ex 7
H	Amdahl, $N \to \infty$ (limit)	ceiling on speedup	Ex 8
I	Real-world word problem	pick the architecture	Ex 9
J	Exam twist	SIMD vs MIMD on the same array	Ex 10

Figure — Flynn's taxonomy (SISD - SIMD - MIMD)

Look at the board above: the horizontal axis is how many instruction streams (one vs many), the vertical axis is how many data streams. Each example plants a flag in one region.

Ex 1 — Cell A: the SISD baseline

Forecast: guess the total before reading on — is it $2 ns$ , $8 ns$ , or something bigger?

Count the additions. Four numbers means four ADD operations. Why this step? In SISD each datum is touched by exactly one instruction, one at a time — nothing overlaps.
Note the dependency. sum after the second add needs the result of the first. So add #2 cannot begin until add #1 finishes. Why this step? This is what forces the serial line — the whole reason SISD gives no speedup.
Multiply. Total $= N \cdot T = 4 \times 2 ns = 8 ns$ . Why this step? With no overlap, times simply add up.

Verify: four cycles $\times 2 ns = 8 ns$ . Units: $[count] \times [ns] = [ns]$ ✓. Sanity: it must be slower than any parallel version — and it is our slowest number, good.

Ex 2 — Cell B: SIMD, the ideal case

Forecast: if four lanes each do one add "at once", how many $T$ 's of time pass?

One instruction, four data. The control unit broadcasts a single ADD; lanes $1..4$ each hold one datum. Why this step? This is the defining move of SIMD — one instruction stream, four data streams.
All lanes fire in the same cycle. Because $10, 20, 30, 40$ are independent (no lane needs another lane's answer), they run together. Why this step? Independence is the licence to parallelise; without it we'd be back in Ex 4.
Time. $T_{SIMD} = T = 2 ns$ .
Speedup. $\frac{T _{SISD}}{T _{SIMD}} = \frac{4 \times 2}{2} = 4$ .

$Speedup = \frac{N \cdot T}{T} = N = 4$

Verify: $8 ns \div 2 ns = 4 \times$ ✓. Sanity: speedup equals lane count $N = 4$ , the theoretical ceiling for SIMD — correct for the ideal case.

Ex 3 — Cell C: SIMD with a ragged tail

Forecast: $10/4$ isn't a whole number — will you need 2 passes or 3?

Divide with a ceiling. $⌈ 10/4 ⌉ = 3$ passes: lanes handle elements ${0..3}$ , ${4..7}$ , then ${8, 9}$ . Why this step? You cannot do "two and a half" broadcasts — the last partial group still costs a full vector op.
The third pass wastes lanes. Pass 3 uses only 2 of 4 lanes; the other 2 do nothing but still burn a cycle. Why this step? This is the overhead the parent note warned about — real speedup rarely hits $N \times$ .
Time. $3 \times 2 ns = 6 ns$ .
Effective speedup vs SISD (which is $10 \times 2 = 20 ns$ ): $20/6 \approx 3.33 \times$ , not $4 \times$ .

Verify: $⌈ 10/4 ⌉ = 3$ ; $3 \times 2 = 6 ns$ ; $20/6 = 3.33 \dots$ ✓. Sanity: $3.33 < 4$ , so ragged data lowers speedup below the lane count — exactly the "ragged tail" penalty.

Ex 4 — Cell D: SIMD defeated by a dependency (degenerate input)

Forecast: these are the same numbers as Ex 2 — will SIMD still give $4 \times$ ?

Spot the dependency. $b_{2}$ needs $b_{1}$ ; $b_{3}$ needs $b_{2}$ . Lane 3 cannot start until lane 2 is done. Why this step? A data dependency between elements removes the "independent" licence from Ex 2 step 2.
Lanes must wait for each other. The naive broadcast is illegal — you'd read a value not yet written. Why this step? This is the degenerate case: the workload structurally refuses lockstep parallelism.
Result. Naively you fall back to SISD-like timing: $4 \times 2 = 8 ns$ , speedup $= 1 \times$ (none). (Clever "parallel scan" algorithms exist, but the point stands: the naive same-instruction trick fails.)

Verify: speedup $= 8/8 = 1$ ✓. Sanity: identical data to Ex 2, yet speedup collapsed from $4$ to $1$ — proving speedup depends on dependency structure, not on the numbers.

Ex 5 — Cell E: MIMD, genuinely different code

Forecast: three $30 ms$ jobs — is the wall-clock $90 ms$ or $30 ms$ ?

Note the streams. Three different instruction streams, three different data sets ⇒ MIMD. Why this step? SIMD is impossible — there is no single common instruction to broadcast.
They run simultaneously and independently. No core waits on another (no shared result). Why this step? Task-parallel work overlaps fully when tasks don't depend on each other.
Wall-clock time = the longest single job $= 30 ms$ (they finish together since equal length).

Verify: serial would be $3 \times 30 = 90 ms$ ; MIMD gives $30 ms$ ; speedup $90/30 = 3 \times$ ✓. Sanity: equals core count $3$ because jobs are perfectly independent and equal-sized.

Ex 6 — Cell F: Amdahl's Law, ordinary fraction

Forecast: you have 8 cores and 90% is parallel — will you get close to $8 \times$ ?

Recall the parent's law — the symbol $S (N)$ means "how many times faster with $N$ cores":

$S (N) = \frac{1}{( 1 - P ) + \frac{P}{N}}$

Serial part stays put. $1 - P = 0.1$ . That tenth of the work runs on one core no matter what. Why this step? Serial work is the anchor Amdahl's Law is built to expose.
Parallel part shrinks by $N$ . $\frac{P}{N} = \frac{0.9}{8} = 0.1125$ . Why this step? Splitting parallel work across 8 cores divides its time by 8.
Add and invert. Denominator $= 0.1 + 0.1125 = 0.2125$ ; so $S (8) = 1/0.2125 \approx 4.71$ .

Verify: $1/ (0.1 + 0.9/8) = 1/0.2125 = 4.705 \dots \approx 4.71 \times$ ✓. Sanity: far below $8 \times$ — that stubborn 10% serial slice cut our speedup nearly in half. This is the whole lesson of Amdahl's Law.

Ex 7 — Cell G: the two degenerate fractions ( $P = 0$ and $P = 1$ )

Forecast: one of these gives no speedup and one gives the maximum — which is which?

Case $P = 0$ . Denominator $= (1 - 0) + 0/8 = 1$ . So $S (8) = 1/1 = 1 \times$ . Why this step? If nothing can be split, extra cores are useless — the honest degenerate result.
Case $P = 1$ . Denominator $= (1 - 1) + 1/8 = 0 + 0.125 = 0.125$ . So $S (8) = 1/0.125 = 8 \times$ . Why this step? With zero serial work, the law reduces to plain $S (N) = N$ — matching the ideal SIMD/MIMD picture.

Verify: $P = 0 \Rightarrow S = 1$ ; $P = 1 \Rightarrow S = 8$ ✓. Sanity: these are the floor ( $1$ ) and ceiling ( $N$ ) of Amdahl speedup — every real program lives strictly between them.

Ex 8 — Cell H: the limit $N \to \infty$

Forecast: unlimited cores — does speedup shoot to infinity, or hit a wall?

Take $N \to \infty$ . The term $\frac{P}{N} = \frac{0.9}{N} \to 0$ . Why this step? Dividing parallel work among endless cores drives its time toward zero.
What's left is the serial floor. $N \to \infty lim S (N) = \frac{1}{1 - P} = \frac{1}{0.1} = 10$ . Why this step? The serial fraction can never be sped up, so it caps everything.

$lim_{N \to \infty} S (N) = \frac{1}{1 - P}$

Verify: $1/ (1 - 0.9) = 1/0.1 = 10 \times$ ✓. Sanity: even infinite hardware only gets $10 \times$ here — the serial 10% is a hard ceiling. This is why "just add more cores" eventually stops helping.

The curve above (from Ex 6, 7, 8) shows speedup flattening toward the dashed ceiling $1/ (1 - P)$ as cores increase — you approach it but never cross it.

Ex 9 — Cell I: real-world word problem (choose the architecture)

Forecast: are these both SIMD? Both MIMD? Or one of each?

Job (a): one operation, millions of data. Every pixel gets the identical "add brightness" instruction. Why this step? One instruction + many data ⇒ this is the textbook SIMD (GPU) job.
Job (b): different code per thread. Physics, AI, and audio are unrelated algorithms. Why this step? Multiple instruction streams + multiple data ⇒ MIMD (multicore CPU).

Verify: (a) SIMD, (b) MIMD ✓. Sanity: matches the parent note — "GPUs are SIMD, modern CPUs are MIMD."

Ex 10 — Cell J: the exam twist

Forecast: both have "4-wide" hardware — will they tie?

Machine X (SIMD). $⌈ 16/4 ⌉ = 4$ vector ops $\Rightarrow 4 \times 2 = 8 ns$ . Why this step? One broadcast handles 4 elements; 16 elements need 4 broadcasts.
Machine Y (MIMD). Each core does $16/4 = 4$ scalar multiplies, in parallel with the others $\Rightarrow 4 \times 2 = 8 ns$ . Why this step? Cores run at the same time, so wall-clock is just one core's share.
Compare. Both give $8 ns$ — a tie on this idealised workload.

Verify: X $= 4 \times 2 = 8$ ; Y $= 4 \times 2 = 8$ ; equal ✓. Sanity: the trap is thinking one must win — for identical independent operations, the wide-vs-many distinction disappears in the timing (it reappears in cost, flexibility, and instruction-fetch bandwidth, which the parent note discusses).

Recall Quick self-test

What does $P = 0$ give for speedup on any $N$ ? ::: Exactly $1 \times$ — nothing parallel, extra cores useless. Ceiling of speedup as $N \to \infty$ for $P = 0.9$ ? ::: $1/ (1 - 0.9) = 10 \times$ . Why did the prefix-sum (Ex 4) get no SIMD speedup? ::: Each element depends on the previous one — no independence, no lockstep. Why is $10$ floats on $4$ lanes only $\approx 3.33 \times$ , not $4 \times$ ? ::: The ragged last pass wastes idle lanes ( $⌈ 10/4 ⌉ = 3$ passes).