Question bank — Flynn's taxonomy (SISD - SIMD - MIMD)

A GPU is a MIMD machine because it has thousands of cores. ::: False. Thousands of cores does not equal thousands of instruction streams; a GPU broadcasts one instruction to a group of lanes at once (NVIDIA calls such a lock-stepped group of 32 lanes a warp), so within that group it is SIMD (data-parallel), not MIMD. SISD hardware can never run more than one program. ::: False. A single SISD core time-slices: the OS rapidly switches between programs. Only one instruction executes per moment, so it is still Single-Instruction — concurrency is an illusion of scheduling, not real parallelism. SIMD always gives an exact N× speedup with N lanes. ::: False. N× is the ideal ceiling. Load/store overhead, misalignment, leftover elements when the array length is not a multiple of N, and any data dependency all pull the real speedup down to typically 2–4×. MIMD hardware can do everything SIMD can do. ::: True in capability, but not in efficiency. Each MIMD core running the same instruction on different data mimics SIMD, yet it pays N separate fetch/decode costs instead of one broadcast — so it wastes instruction bandwidth SIMD saves. A dual-core laptop running one single-threaded program behaves like SISD for that program. ::: True. If the program never spawns a second instruction stream, only one core drives it: one instruction stream on its data at a time — that is SISD behaviour regardless of how many cores sit idle. The classification depends on the software, not the hardware. ::: Partly false. Flynn classifies the hardware's capability (how many instruction/data streams it can run). But whether that capability is used depends on software — a MIMD chip running serial code delivers SISD performance.

"MISD is the most common category because pipelining is everywhere." ::: Wrong. MISD (many instructions, one data element) is the rarest, near-theoretical box; pipelining is not MISD because a pipeline processes a stream of different data, not one datum through many independent instruction streams. "Broadcasting one instruction to 4 units means the control unit works 4× harder." ::: Wrong — it works less. The whole point of SIMD is that fetch/decode happens once and drives all 4 lanes, so control-unit effort per data element drops, not rises. "In SIMD the four additions finish in four cycles, one lane per cycle." ::: Wrong. The lanes run in lockstep within the same cycle, not one after another. That simultaneity is exactly what separates SIMD from a SISD loop. "Amdahl's Law says with enough cores, speedup is unlimited." ::: Wrong. As the number of cores $N$ grows without bound, $S(N)$ approaches $\frac{1}{1-P}$ (in plain text: 1 divided by the serial fraction), a hard ceiling. A program that is 10% serial can never exceed 10× speedup, no matter the core count. "SIMD needs cache coherence between its lanes." ::: Wrong. Cache coherence is a MIMD shared-memory problem, where independent cores may write the same address. SIMD lanes are driven by one control unit in lockstep and don't independently write shared state that way. "Distributed-memory MIMD cores share one RAM, so message passing is optional." ::: Wrong. Distributed memory means each core has private RAM; there is no shared address space, so explicit message passing (e.g. MPI) is required, not optional.

Why did Flynn use two axes instead of just "parallel vs not"? ::: Because parallelism can live in two independent dimensions — same instruction across many data (data-level) versus many instructions running independently (instruction-level). One binary label can't distinguish a GPU from a multicore CPU; two axes can. Why is SIMD ideal for images and audio but poor for a web server? ::: Images/audio apply the same operation to millions of uniform elements (data parallelism), which SIMD's single broadcast exploits perfectly. A web server runs different algorithms per request (task parallelism), so there's no common instruction to broadcast. Why can't SISD parallelise the loop sum += array[i]? ::: Because each iteration reads the sum written by the previous one — a data dependency. Element order matters, so the additions cannot happen simultaneously without changing the result. Why does SIMD lower instruction bandwidth? ::: One instruction is fetched and decoded, then reused across N lanes. So N data operations cost only one instruction transfer from memory, cutting fetch/decode traffic by a factor of N. Why is cache coherence a MIMD-specific headache? ::: Only MIMD has multiple independent control units writing to a shared memory. If core 1 writes X=5 in its cache, core 2 must be forced to see it — a coordination problem that SISD (one writer) and SIMD (one instruction stream) simply don't have.

What is MISD, and why is it nearly empty? ::: MISD = Multiple Instruction, Single Data: many different instruction streams all crunching the same data element. It's the fourth logical box but has almost no real machines; the closest niche is fault-tolerant redundancy (several units checking one datum). What happens in SIMD when your array has 10 elements but only 8 lanes? ::: You need two passes: one full 8-wide operation plus a partial pass handling the remaining 2. The tail wastes lanes (masking or scalar cleanup), so the effective speedup falls below the ideal N×. If $P$ (the parallel fraction) = 0, what does Amdahl's Law predict? ::: $S(N)=\frac{1}{(1-0)+0}=1$ (plain text: 1 / (1 + 0) = 1). No speedup at all — a purely serial program gains nothing from extra cores, which is the whole cautionary point of the law. If $P=1$ (perfectly parallel), what is the speedup on N cores? ::: $S(N)=\frac{1}{0+1/N}=N$ (plain text: 1 / (1/N) = N) — the ideal linear speedup. This is the unreachable best case, since real code always has some serial setup, I/O, or synchronisation. Is a single-core CPU using an internal pipeline still SISD? ::: Yes. A pipeline overlaps stages of different instructions, but from Flynn's viewpoint there is still one instruction stream feeding one data stream. Pipelining is instruction-level overlap, not a new stream, so the SISD label stands. Can the same physical chip act as SIMD in one moment and MIMD in another? ::: Yes. A modern GPU or CPU can run different cores on independent kernels (MIMD) while each core internally broadcasts one instruction across its lanes (SIMD). Flynn's boxes describe modes of execution, and hardware can switch between them. Where does a modern multicore CPU with SIMD vector units (e.g. AVX) sit? ::: It is MIMD at the core level (each core has its own instruction stream) and SIMD within each core (AVX applies one instruction to a packed vector). Real chips are hybrids, so Flynn labels a dominant mode, not an exclusive one.