Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Multiprocessors and Flynn's taxonomy

Flynn's taxonomy classifies computer architectures by number of instruction and data streams (SISD, SIMD, MISD, MIMD); this note explains each class, how multiprocessors fit, key performance formulas (speedup, efficiency, Amdahl-related ideas), and exam-style examples and questions.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Many real-world systems use more than one processing element. Understanding Flynn's taxonomy helps an engineer classify a design (vector units, GPUs, multicore CPUs, clusters) and choose the right programming, memory and coherence model. It also helps estimate performance gains and limits when parallelizing software.

Key ideas

Start from the basic notion: a stream is a sequence of items processed over time. Flynn's taxonomy classifies systems by how many instruction streams and data streams can be active concurrently.

  • Instruction stream — a sequence of machine instructions fetched and executed by a control unit.
  • Data stream — a sequence of data elements consumed by instructions.

Flynn's four classes (exact definitions):

  • SISD (Single Instruction, Single Data): One instruction stream operates on one data stream. This is the traditional uniprocessor von Neumann machine executing one instruction at a time on one data item.
  • SIMD (Single Instruction, Multiple Data): One instruction stream controls multiple processing elements, each operating on different data elements in lockstep. Used for vector processors and GPUs. Assumes the same operation applies to many data items simultaneously.
  • MISD (Multiple Instruction, Single Data): Multiple instruction streams operate on the same data stream. This class is rare in practice; sometimes used as a conceptual model for certain fault-tolerant systems (e.g., multiple different algorithms checking a single data source).
  • MIMD (Multiple Instruction, Multiple Data): Multiple autonomous processors execute different instruction streams on different data streams. This includes multicore CPUs and distributed-memory clusters.

Assumptions and implications often used in exams:

  • In SIMD, synchronization is implicit at the instruction level (lockstep execution). Draw a single control unit feeding identical instruction words to multiple PEs; label data lanes D0..D(N-1) and PEs PE0..PE(N-1).
  • In MIMD, processors are independent — they may synchronize via message passing or shared memory; draw several processors each with local memory (for distributed memory) or several processors connected to a shared memory bus (for shared-memory UMA).

Memory and coherence (brief, referenced topics):

  • Multiprocessors may be shared-memory (processors see a common address space) or distributed-memory (each processor has local memory and communicates by messages). See the topics UMA and NUMA for shared-memory variants and Cache coherence for consistency issues.

Performance concepts to derive in exams:

  • Speedup (how much faster a parallel system is versus baseline serial execution). Derive from definitions of time.
  • Efficiency (speedup per processor) and its relation to overhead.
  • Amdahl-like reasoning: maximum possible speedup is limited by the serial fraction of a program.

Diagrams to draw (describe exactly):

  1. Diagram for SIMD machine: draw one box labelled "Control Unit (instruction stream)" with an arrow feeding N boxes labelled "PE0, PE1, ... PE(N-1)". Draw each PE with its own data input D0..D(N-1) coming from a vector memory; label the single instruction word bus.
  2. Diagram for MIMD shared-memory multiprocessor: draw 4 processor boxes labelled P0..P3 each connected to a central box labelled "Shared Memory" by lines representing a bus or interconnect. Optionally show caches between processors and shared memory and label "coherence needed".
  3. Diagram for MIMD distributed-memory (cluster): draw processors with local memories and arrows between them labelled "message passing (MPI)".

Notes on practical mapping:

  • GPUs are SIMD-like or SPMD (single program, multiple data) at the programmer level: many threads running the same kernel but can diverge.
  • Modern multicore CPUs are MIMD; within a core vector units implement SIMD operations.

Where to derive step-by-step in exams: derive speedup from time definitions and show how serial fraction limits speedup (short derivation of Amdahl's formula is commonly expected). Also derive efficiency formula and overhead decomposition T_parallel = T_1/p + Toverhead, where T_1 is the time to execute the parallelizable work on one processor (s).

Formulas

S = T_serial / T_parallel — S is speedup (dimensionless). T_serial is execution time on best-known serial implementation (s). T_parallel is time on the parallel system (s). Applies to wall-clock execution time comparison.

E = S / p — E is efficiency (dimensionless). p is number of processors. Applies when measuring per-processor utilization.

T_parallel = T_serial * (f_serial + f_parallel / p) + Toverhead — T_parallel (s). f_serial = fraction of work that is strictly serial (dimensionless), f_parallel = fraction that is parallelizable, f_serial + f_parallel = 1, p = processors, Toverhead = additional parallel overhead time (s). Applies when separating serial and parallel parts and accounting for overhead.

S_max = 1 / f_serial — theoretical maximum speedup ignoring overhead (dimensionless). Derived from letting p -> infinity in Amdahl's model.

Efficiency E = (1 / p) * (1 / (f_serial + f_parallel / p + Toverhead/T_serial)) — from substituting T_parallel into S and dividing by p. Units dimensionless.

Note: These formulas assume a fixed problem size (strong scaling). For weak scaling (problem size grows with p), Gustafson's law is appropriate (see related topics). A common form is S_G = p - (p - 1) * f_serial (dimensionless) under weak-scaling assumptions.

Worked examples

Example 1 — Numerical speedup and efficiency (university exam style). Problem: A program has 25% serial fraction (f_serial = 0.25). Best serial run time T_serial = 200 s. Run on p = 8 processors with negligible overhead. Compute speedup and efficiency, and the theoretical maximum speedup. Steps:

  1. Use Amdahl's formula for no overhead: T_parallel = T_serial * (f_serial + f_parallel / p). Here f_parallel = 0.75.
  2. T_parallel = 200 * (0.25 + 0.75/8) = 200 * (0.25 + 0.09375) = 200 * 0.34375 = 68.75 s.
  3. Speedup S = T_serial / T_parallel = 200 / 68.75 = 2.909090... ≈ 2.909. S = 2.909.
  4. Efficiency E = S / p = 2.909 / 8 = 0.3636 ≈ 36.36%. E ≈ 36.36%.
  5. Theoretical maximum speedup S_max = 1 / f_serial = 1 / 0.25 = 4. S_max = 4. Final answers: T_parallel = 68.75 s, S = 2.909, E = 36.36%, S_max = 4.

Example 2 — Classify architectures (theory/diagram answer). Problem: For each of these descriptions, state Flynn class and justify in one sentence: a) A GPU kernel where thousands of threads execute the same instruction sequence on different pixels. b) A 4-core CPU where each core runs different processes and communicates via shared memory. c) A fault-tolerant unit where the same sensor reading is processed by three different algorithms to cross-check results. Answers (model): a) SIMD — single instruction stream issued (kernel), multiple data items (pixels) processed in parallel; GPU implements this with many lanes. b) MIMD — multiple independent instruction streams on different data; cores may run different programs. c) MISD (rare) — multiple instruction streams converging on the same data stream for diversity; describes an MISD-like use for fault tolerance.

Example 3 — Trace of SIMD vector add (algorithmic). Problem: Add two length-4 vectors A and B element-wise using a 4-lane SIMD processor. Show steps where lanes operate in lockstep. Trace (step-by-step):

  1. Control unit issues "ADD" instruction with vector register operands A_reg and B_reg.
  2. PE0 computes C0 = A0 + B0, PE1 computes C1 = A1 + B1, PE2 computes C2 = A2 + B2, PE3 computes C3 = A3 + B3 simultaneously.
  3. Results written back to C_reg[0..3]. End state: C contains element-wise sums. Note: show diagram with one instruction bus to 4 PEs and data lanes labelled.

Common mistakes

  • Forgetting overhead (communication, synchronization) when computing T_parallel; this leads to overestimated speedups.
  • Calling GPU "pure SIMD" without noting SPMD programming model and possible divergence penalties — exam answers should mention divergence cost when threads in a SIMD group take different control paths.
  • Giving MISD examples from regular CPU pipelines — a CPU pipeline is still SISD at the architectural level, not MISD.

For your exam

Typical question types:

  • Definitions: Define SISD, SIMD, MISD, MIMD and give practical examples — include diagrams.
  • Short notes: Compare SIMD vs MIMD, discuss shared vs distributed memory and coherence issues (reference Cache coherence topic).
  • Derivations: Derive Amdahl's formula for speedup and show maximum speedup for p -> infinity.
  • Numericals: Compute T_parallel, speedup and efficiency given f_serial, T_serial and p; include overhead when specified.
  • Diagrams: Draw and label SIMD and MIMD architectures and show where cache coherence is needed. What a full-marks answer includes:
  • Precise definitions with bolded taxonomy term and clear example devices (GPU, vector processor, multicore CPU, redundancy checker).
  • Diagrams as described above with labels for control unit, PEs, data lanes, shared memory, caches and interconnect.
  • Correct formulas with units, and step-by-step numerical calculation carrying units to final answers.
  • Stated assumptions (fixed problem size, overhead present or negligible).

Quick check

  1. What does SIMD stand for and give one hardware example.
  2. If T_serial = 120 s and f_serial = 0.1, what is the theoretical maximum speedup?
  3. Which Flynn class best describes a 16-core CPU where each core runs different threads and shares a cache? Answers: 1) Single Instruction, Multiple Data — example: GPU or vector processor. 2) S_max = 1 / f_serial = 10. 3) MIMD.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?