Flynn's Classification of Computer Architecture (7M)

Proposed by Michael J. Flynn (1966) - classifies parallel architectures based on number of Instruction streams vs Data streams.

Streams = independent sequence of instructions / data as seen by CPU.

                    Single Data (SD)
                    One data stream
                   ┌─────────────────
                   │
Single Instruction │   SISD
Single instruction │
stream             │   (von Neumann)
                   │
-------------------+---------------------------------
                   │
Multiple Instruction│  MISD
Multiple instruction│ (rare - systolic)
stream             │
                   └─────────────────
                    Multiple Data (MD)
                    Multiple data streams
Actually 2x2 grid:
         ┌─────────────┬──────────────┐
         │  SD         │  MD          │
─────────┼─────────────┼──────────────┤
 SI      │  SISD       │  SIMD        │
─────────┼─────────────┼──────────────┤
 MI      │  MISD       │  MIMD        │
         └─────────────┴──────────────┘

1. SISD - Single Instruction Single Data

One instruction stream, one data stream. Sequential.

• Architecture: Conventional Von Neumann uniprocessor. One CU fetches one instruction, one ALU operates on one data element at a time. (No parallelism)
• Execution: IF -> ID -> EX -> MEM -> WB single thread.
• Example: Intel 8086, 80386 uniprocessor, ARM single-core, IBM 360. Old mainframes.
• Diagram:

  ┌────┐      ┌─────┐      ┌─────┐      ┌─────┐
  │ CU |----->| PU  |----->| MU  |  IS  DS -> Single pipeline
  └────┘      └─────┘      └─────┘
   (IS= Instruction Stream, DS=Data Stream, PU=Processing Unit, MU=Memory)

• Performance: Limited by clock, CPI, pipelining is still SISD (ILP but not classified separately by Flynn). Speedup via pipelining/superscalar still logically SISD.

2. SIMD - Single Instruction Multiple Data

One instruction executed on multiple data elements in parallel (Lockstep). Data parallelism.

• Architecture: One CU broadcasts same instruction to multiple Processing Elements (PEs)/ALUs, each with own data. Requires array of processors + interconnection network (shared memory or mesh).
• Execution: Fetch once, decode once, execute simultaneously on N data:
  for (i=0..N-1) C[i] = A[i] + B[i] single instruction ADD does all.
• Examples:
  • Vector processors: Cray-1, CDC STAR-100, TI ASC
  • Array processors: ILLIAC-IV (64 PEs), CM-2, DAP
  • Modern: GPU warp (SIMT - extension), Intel SSE/AVX (single core SIMD within register), AVX-512 executes 16 floats per instruction, Multimedia extensions MMX.
• Diagram:

          ┌────┐
          │ CU |---- IS (same instruction broadcast) ----+
          └────┘                                         |
      ┌──────┼──────┬───────┐
      v      v      v       v
    ┌────┐┌────┐┌────┐  ┌────┐
    │PE0 ││PE1 ││PE2 │..│PEN │ each PE has own data DS0..DSN
    │ALU ││ALU ││ALU │  │ALU │
    └────┘└────┘└────┘  └────┘
      ↕     ↕     ↕       ↕  Data Memory Module 0..N or interleaved

• Use: Matrix operations, image processing, graphics, scientific loops where same operation applied to large dataset. Excellent speedup for vectorizable code; branch divergence hurts (masking).
• Types: Word-slice vs bit-slice, true array vs vector/pipelined.

3. MISD - Multiple Instruction Single Data

Multiple instruction streams on same single data stream. Rare/ theoretical.

• Architecture: Multiple CUs each with distinct instruction on same data item, pipelined through stages. Data flows through chain of processors.
• Example / Interpretation:
  • Pipeline / Systolic array where data flows X -> PE1 (Op1) -> PE2 (Op2) -> PE3 (Op3) each stage different instruction but same datum stream - e.g., real-time signal processing, fault-tolerant systems with redundant execution for voting (N-version).
  • Carnegie Mellon C.mmp (conceived but no commercial)
  • Some view pipeline within single CPU as MISD-like (IF,ID,EX operate on same instruction stream overlapped) but not true.
• Diagram:

 DS ---->┌────┐    ┌────┐    ┌────┐
         │PE0 │--->│PE1 │--->│PE2 │----> Result
 IS0---->|CU0 | IS1|CU1 | IS2|CU2 |

• Use: Almost no general-purpose machine purely MISD; considered for specialized: multiple frequency filters on same sample stream, cryptographic pipelines.

4. MIMD - Multiple Instruction Multiple Data

Multiple instruction streams, multiple data streams. True parallelism - autonomous processors.

• Architecture: Multiple independent processors (each with own CU+ALU+Memory/Local) work on own instruction & data. Two flavors:
  • Shared Memory (Tightly coupled): SMP (Symmetric Multiprocessors) - bus/cache coherent shared address space. E.g., Multicore CPU (Intel i7 8 cores), Xeon server.
  • Distributed Memory (Loosely coupled): Message-passing - cluster, network of workstations (NOW), supercomputer. E.g., Beowulf cluster, IBM BlueGene, NUMA.
• Execution: MIMD can execute completely independent tasks (MIMD - multiple Programs) or cooperate on single problem (parallel programs) via synchronization (lock, barrier, MPI_Send).
• Examples: Multicore processors, Multiprocessors, Clusters, Grids, Multi-computer (Cray T3D, Intel Paragon).
• Diagram:

  ┌────┐  ┌────┐          ┌────┐  ┌────┐
  │CU0 │->│PE0 │->DS0     │CU1 │->│PE1 │->DS1
  └────┘  └────┘          └────┘  └────┘
     IS0     \ shared/ \     IS1
              Distribution Network (Bus/Crossbar/Network)
  ┌────┐  ┌────┐          ┌────┐  ┌────┐
  │CUN │->│PEN │->DSN  etc.
  └────┘  └────┘

• Use: General-purpose parallel computing - database servers, OS multitasking, HPC. Most flexible; speedup limited by Amdahl's law: Speedup = 1 / (f + (1-f)/N).

Comparison Table

Class	Instr Streams	Data Streams	Parallelism	Examples	Use Case
SISD	1	1	None (sequential)	8086, ARM single	Basic PC
SIMD	1	N	Data parallel	ILLIAC, GPU warp, AVX	Vector/matrix
MISD	N	1	Pipeline on data	Systolic (rare)	Fault tolerance, pipeline
MIMD	N	N	Task parallel	Multicore, Cluster	General parallel

Extended Classifications (Johnson, later): SISD vs pipelines etc., but Flynn remains standard.

For exam: Draw 4 quadrants diagram + small block for each type with CU/PE and arrows.