Flynn's taxonomy (SISD - SIMD - MIMD): Visual walkthrough

Before any letter appears, agree on one picture: time is a horizontal bar. A longer bar means the program takes longer. Splitting work across cores means stacking pieces of the bar side-by-side instead of end-to-end so they finish together. That single idea drives everything below.

Step 1 — Draw the whole job as one bar of time

WHAT. We run a program on one core (one worker). Whatever it takes, we call that total time $T$ . The letter $T$ just names "how long the single-core run lasts" — nothing more.

WHY. We need a fixed reference. Every speedup is measured against this one honest run. If we don't pin down $T$ , "twice as fast" has no meaning.

PICTURE. One solid bar. Its full length is $T$ . Time flows left → right.

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

Step 2 — Not all work can be shared: split the bar in two

WHAT. Look inside the job. Some work must happen in order — reading a config file, setting up, printing the final answer. Call the fraction of the total that is stuck-in-order the serial part. The rest — loops over independent data, like the SIMD-style array adds from the parent — is the parallelizable part. We name the parallel fraction $P$ .

WHY. A "fraction" is just "what slice of the bar." If $P = 0.75$ , then three-quarters of the bar can be spread across cores and one-quarter cannot. This split is the only thing that will decide the answer, so we make it visible first.

PICTURE. The same bar, now painted two colours: an amber serial chunk of length $(1 - P) T$ and a cyan parallel chunk of length $P T$ .

Step 3 — Hand the parallel part to $N$ cores

WHAT. Introduce $N$ = the number of cores (workers). We take only the cyan parallel chunk and cut it into $N$ equal slices, then run those slices at the same time, stacked on top of each other. The serial amber chunk is untouched — it still runs on one core, alone.

WHY. This is the whole promise of a MIMD machine: independent work done simultaneously. Independent slices can overlap in time, so laid side-by-side their finish time is just one slice's length. One slice of the cyan chunk lasts $\frac{P T}{N}$ : the parallel time $P T$ divided among $N$ cores.

PICTURE. The cyan chunk fans out into $N$ shorter bars stacked vertically (they run together). The amber chunk stays full-length in front of them.

Step 4 — Rebuild the new, shorter bar

WHAT. The new total run time — call it $T_{N}$ — is what's left end-to-end: the serial chunk that never shrank plus the squished parallel chunk.

WHY. Cores overlapped the parallel work, but nothing could overlap the serial work — a single worker still has to grind through it. So we glue the two remaining lengths back into one bar.

PICTURE. A shorter bar: full amber serial piece, then a thin cyan stub of width $P T / N$ .

Step 5 — Turn "shorter bar" into "how much faster": divide

WHAT. Speedup $S (N)$ asks a ratio question: "how many times shorter is the new bar than the old bar?" So we divide old time by new time.

WHY. We use division and not subtraction because "twice as fast" is a ratio (bar half as long), not a difference in seconds. A ratio is what people mean by "speedup."

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

Every term has a factor of $T$ . That common $T$ cancels — the speedup does not care how long the program is, only how it is split. Divide top and bottom by $T$ :

Step 6 — The degenerate cases (check the formula never lies)

We must show the formula behaves sanely at every extreme, so no reader ever hits a scenario we skipped.

Case A — one core, $N = 1$ . Plug in: $S (1) = \frac{1}{( 1 - P ) + P} = \frac{1}{1} = 1$ . One core gives exactly the speed we started with. Good — no free lunch from doing nothing.

Case B — nothing parallel, $P = 0$ . Then $S (N) = \frac{1}{1 + 0} = 1$ for any $N$ . A purely serial program ignores every extra core. The bar is all amber; slicing zero cyan changes nothing.

Case C — everything parallel, $P = 1$ . Then $S (N) = \frac{1}{0 + 1/ N} = N$ . Perfect linear speedup — this is the ideal SIMD case from the parent, where $N$ lanes really do give $N \times$ .

PICTURE. Three bars side by side showing these limits.

Step 7 — The wall: let $N \to \infty$

WHAT. Push the number of cores toward infinity. In $\frac{P}{N}$ , as $N$ grows the whole term slides toward $0$ (dividing by a huge number). What survives?

WHY. This answers the headline question: what is the most speedup money can ever buy? Adding cores only attacks the $\frac{P}{N}$ term; it can never touch $(1 - P)$ .

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

PICTURE. As cores climb, the cyan stub vanishes but the amber serial block remains — the bar flattens onto a floor, and the speedup curve bends into a ceiling of height $1/ (1 - P)$ .

The one-picture summary

The single figure ties it together: the original bar splits into serial (amber) + parallel (cyan); cores squeeze only the cyan; the serial amber sets a hard floor; and the speedup curve rises fast, then bends into the ceiling $1/ (1 - P)$ .

Recall Feynman retelling — say it like a story

Imagine painting a fence. Some of the work — buying the paint, opening the tin, cleaning up — you must do alone, in order. That's the amber part; friends can't help. The rest — actually brushing planks — you can split among helpers; that's the cyan part. Bring one friend, ten, a thousand: the brushing gets faster and faster, but the buying-and-cleanup time never changes. So the whole job can never get faster than the time that lonely amber work eats. Amdahl's Law is just the arithmetic of that fence: divide the original time by (the stubborn serial slice + the parallel slice cut into $N$ pieces), and no matter how many friends show up, you slam into a ceiling of one-over-the-serial-fraction.

Recall Quick self-test

With $P = 0.95$ , what is the speedup ceiling as cores go to infinity? ::: $1/ (1 - 0.95) = 20 \times$ . In Amdahl's Law, which term has no $N$ in it, and why does that matter? ::: The serial term $(1 - P)$ ; it never shrinks with more cores, so it sets the hard limit. Why divide (not subtract) old time by new time to get speedup? ::: Speedup is a ratio ("half as long = 2×"), not a difference in seconds.

Return to the parent: Flynn's taxonomy (SISD · SIMD · MIMD).