Flynn's taxonomy (SISD - SIMD - MIMD): Exercises — Hardware deep dive

This page is a self-test ladder. Each rung is harder than the last. Cover the solution, try the problem, then reveal. If a word or symbol is new, we build it from zero before using it.

Quick vocabulary you will need (all from the parent Flynn's taxonomy (SISD - SIMD - MIMD)):

The four boxes are just the two yes/no questions "one or many instructions?" crossed with "one or many data streams?" Here is that grid so you can see all four at a glance before we use them:

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

Reading the grid: the horizontal axis is the instruction question (Single on the left, Multiple on the right); the vertical axis is the data question (Single at the bottom, Multiple at the top). Each of the four cells is one architecture. Note the top-left / bottom-right diagonal: SISD (the plain serial CPU) and MIMD (many full cores) are the two "everyday" machines; SIMD (top-left column, many data) is the vector/GPU box; MISD (bottom-right, greyed) is the rare theoretical box we will not build speedup formulas for.

Level 1 — Recognition

Exercise 1.1

Classify each machine as SISD, SIMD, MISD, or MIMD: (a) An Arduino Uno running one loop. (b) A GPU adding two 1024-element arrays with one add instruction. (c) An 8-core desktop running a browser, a music player, and a compiler at the same time. (d) Four flight computers each running a different safety algorithm on the same sensor reading, voting on the answer.

Recall Solution

What we look for: count instruction streams (how many different programs) and data streams (how many independent data items).

(a) One program, one data item at a time → SISD.
(b) One add instruction broadcast to 1024 data pairs → SIMD.
(c) Several cores, each its own program and data → MIMD.
(d) Many different instructions, but they all chew the same single data stream → MISD (the rare, mostly theoretical box — here in its one real niche, fault-tolerant voting).

Exercise 1.2

Fill the blanks: "S____D means Single Instruction, Multiple Data. Its speedup comes from ____-level parallelism, not ____-level parallelism."

Recall Solution

SIMD.
Data-level parallelism (same op, many data).
Not task-level parallelism (that is MIMD's job).

Exercise 1.3

Why does the MISD box (Exercise 1.1(d)) give no time speedup, even with four computers running at once? What is its point instead?

Recall Solution

Why no speedup: all four computers grind through the same single data stream — nobody is splitting the work, so the job does not finish sooner. Speedup $= \frac{baseline time}{accelerated time}$ needs the accelerated time to shrink; here it does not, so speedup $\approx 1$ . Its actual point: reliability, not speed. Four different algorithms voting on one input catch each other's bugs and hardware faults (used in avionics). That is why MISD stays a niche/theoretical box on our grid — it buys safety, not performance, so none of the speedup formulas below apply to it.

Level 2 — Application

Exercise 2.1

A SISD CPU adds a 16-element array. One ADD takes $T = 2 ns$ . How long is the total? (Here $N$ = number of data items = 16.)

Recall Solution

Why $N \cdot T$ ? In SISD each add must finish before the next starts (the running sum depends on the last result), so the times add up. $T_{SISD} = N \cdot T = 16 \times 2 ns = 32 ns .$

Exercise 2.2

A SIMD unit has 4 lanes. It adds the same 16-element array (independent adds, no running dependency). One broadcast add takes $T = 2 ns$ . How many broadcasts, and what is the total time and speedup?

Recall Solution

Step — how many broadcasts? Each broadcast handles 4 lanes at once.

Reading the figure: the four rows on the left are the 4 lanes (green label) — the parallel hardware channels. The 16 numbered blue tiles are the data items 0–15; they are packed into 4 columns, and each column is one broadcast. The orange arrow above each column marks a single instruction being fired at all four lanes of that column at once. So the picture shows why 16 items become exactly 4 broadcasts of 4 lanes each.

broadcasts = ⌈ 16/4 ⌉ = 4.

(Using the ceiling symbol defined at the top:

16/4 = 4.0

exactly, so rounding up leaves it at

4

.) Step — total time. Each broadcast costs

T

4 \times 2 ns = 8 ns

. Step — speedup (baseline SISD time over accelerated SIMD time):

Speedup = \frac{T _{SISD}}{T _{SIMD}} = \frac{32}{8} = 4.

This equals the lane count — exactly what we expect when the data divides evenly.

Exercise 2.3

Same 4-lane SIMD unit, but now 18 elements. How many broadcasts? What fraction of lanes are wasted on the last broadcast?

Recall Solution

Why ceiling? 18 does not divide by 4, so we need a partial final group. Recall $⌈ x ⌉$ rounds up. $⌈ 18/4 ⌉ = ⌈ 4.5 ⌉ = 5 broadcasts .$ The last broadcast carries only $18 - 4 \times 4 = 2$ items, leaving $4 - 2 = 2$ lanes idle. Wasted fraction of that broadcast $= 2/4 = 0.5 = 50%$ .

Level 3 — Analysis

Exercise 3.1

A program is 90% parallelizable ( $P = 0.9$ ). Amdahl's Law says (here $N$ = number of cores) $S (N) = \frac{1}{( 1 - P ) + \frac{P}{N}} .$ Compute the speedup with $N = 4$ cores and with $N = \infty$ cores.

Recall Solution

What each piece means: $1 - P = 0.1$ is the serial part that never speeds up; $P / N$ is the parallel part shrinking as cores grow. $N = 4$ : $S (4) = \frac{1}{0.1 + \frac{0.9}{4}} = \frac{1}{0.1 + 0.225} = \frac{1}{0.325} \approx 3.077.$ $N \to \infty$ : the term $P / N \to 0$ , so $S (\infty) = \frac{1}{1 - P} = \frac{1}{0.1} = 10.$ Even with infinite cores you cannot beat $10 \times$ — the serial 10% is a hard ceiling.

Exercise 3.2

The curve below plots Amdahl's speedup $S (N)$ against core count $N$ for $P = 0.9$ . Study the figure first, then answer: why does adding cores past a point give almost nothing?

Reading the figure before you answer: the horizontal axis is $N$ = number of cores; the vertical axis is the speedup $S (N)$ . The blue curve is $S (N)$ for $P = 0.9$ . The orange dot marks our $N = 4$ answer ( $\approx 3.08$ ). The red dashed horizontal line is the ceiling $1/ (1 - P) = 10$ . Notice the blue curve rises steeply at first, then bends over and hugs the red line without ever touching it.

Recall Solution

Why it must flatten: early cores each remove a big chunk of runtime; later cores shave the already-tiny parallel remainder while the fixed serial slice $(1 - P)$ stays untouched. In the algebra, $P / N \to 0$ as $N$ grows, so $S (N) \to 1/ (1 - P)$ — the constant serial term dominates and the curve levels off at that ceiling. The orange dot ( $N = 4$ ) is already about a third of the way to the red ceiling; doubling to 8 cores barely moves it, which is exactly the flattening the picture shows.

Exercise 3.3

Two designs finish a fixed job:

Design A: 8-lane SIMD, program 100% data-parallel.
Design B: 8-core MIMD, program only 60% parallel ( $P = 0.6$ ). Which is faster (higher speedup)? By how much?

Recall Solution

SIMD (A): 100% parallel, 8 lanes → ideal speedup $= 8$ (this is the $P = 1$ edge case: $S = N$ ). MIMD (B): $S (8) = \frac{1}{0.4 + \frac{0.6}{8}} = \frac{1}{0.4 + 0.075} = \frac{1}{0.475} \approx 2.105.$ A wins, and $8/2.105 \approx 3.80 \times$ faster than B here.

Level 4 — Synthesis

Exercise 4.1

You must render 1000 identical particles (same physics equation each) and run one AI opponent (a totally different algorithm). Which architecture for which part, and why?

Recall Solution

Particles: same instruction on 1000 data items → SIMD (a GPU). This is textbook data parallelism. AI opponent: a distinct algorithm, unrelated instructions → give it its own MIMD core (a CPU thread). Real systems do both: MIMD CPU cores dispatch work, one of which drives a SIMD GPU. The two classifications are not rivals; they stack.

Exercise 4.2

A job runs in 100 ms on one core. 30 ms of it is stubbornly serial. What is the largest $P$ , and the best possible speedup as $N \to \infty$ ?

Recall Solution

Note on symbols: here it is convenient to normalize the baseline runtime to $1$ . We call that normalized whole $T_{0} = 1$ (a fresh symbol — do not confuse it with $T$ , the single-operation time from the vocabulary). Fractions of $T_{0}$ are then just the parallel/serial shares. Find $P$ : parallel time $= 100 - 30 = 70$ ms, so $P = \frac{70}{100} = 0.7, 1 - P = 0.3.$ Ceiling: $S (\infty) = \frac{1}{1 - P} = \frac{1}{0.3} \approx 3.33.$ No amount of hardware finishes faster than $100/3.33 \approx 30$ ms — the serial 30 ms is the floor.

Level 5 — Mastery

Exercise 5.1

Design target: speed up a workload by exactly $5 \times$ . Measurement shows $P = 0.85$ . (a) Is $5 \times$ even reachable? (b) If yes, how many cores $N$ are needed?

Recall Solution

(a) Ceiling check first. $S (\infty) = 1/ (1 - 0.85) = 1/0.15 \approx 6.67$ . Since $5 < 6.67$ , the target is reachable. (b) Solve Amdahl for $N$ given $S (N) = 5$ . We isolate $N$ one motivated step at a time: $5 = \frac{1}{0.15 + \frac{0.85}{N}} .$ Step 1 — flip both sides. A speedup of 5 means the bracket underneath must equal $1/5$ ; inverting a fraction just reads "if the whole is 5, the part is one-fifth." So $0.15 + \frac{0.85}{N} = \frac{1}{5} = 0.2.$ Step 2 — peel off the serial term. The fixed $0.15$ (the serial slice) is not affected by cores, so we move it aside to see what the parallel term must contribute: $\frac{0.85}{N} = 0.2 - 0.15 = 0.05.$ Step 3 — solve for $N$ . The parallel work $0.85$ must be squeezed down to $0.05$ , and $N$ is the squeeze factor, so $N = 0.85/0.05$ : $N = \frac{0.85}{0.05} = 17.$ You need 17 cores. (Fewer and you fall short; this is the exact break-even.)

Exercise 5.2

Combined machine: a program spends 40% of its time in a SIMD-friendly loop (8 lanes, ideal), 40% in MIMD-parallel tasks run on 4 cores ( $P = 1$ within that part), and 20% is purely serial. Take the whole serial baseline as the normalized time $T_{0} = 1$ . Find the total speedup.

Recall Solution

Idea — shrink each slice by its own factor, then add the times. (All slices are fractions of the normalized baseline $T_{0} = 1$ ; this $T_{0}$ is a fresh normalization symbol, not the single-operation time $T$ .)

Serial slice: $0.20$ , speedup 1 → time $0.20$ .
SIMD slice: $0.40$ , speedup 8 → time $0.40/8 = 0.05$ .
MIMD slice: $0.40$ , speedup 4 → time $0.40/4 = 0.10$ . New total time $= 0.20 + 0.05 + 0.10 = 0.35$ . Overall speedup $= \frac{1}{0.35} \approx 2.857$ (baseline time $T_{0} = 1$ over accelerated time $0.35$ ). The serial 20% dominates the leftover time — Amdahl's lesson generalized to three streams.

Recall One-line self-check

Which single quantity caps every MIMD speedup no matter how many cores? ::: The serial fraction $1 - P$ ; the ceiling is $1/ (1 - P)$ .