Flynn's taxonomy (SISD - SIMD - MIMD)

The Core Principle: Two Orthogonal Axes

This gives us four fundamental categories: SISD, SIMD, MISD, MIMD.

Why These Two Axes?

The genius is recognizing that paralelism can happen at two levels:

• Instruction-level: Different parts of the system execute different instructions
• Data-level: The same instruction applies to multiple data elements simultaneously

Traditional thinking: "Is it parallel or not?" (binary). Flynn: "Parallel in what dimension?" (structured).

1. SISD: Single Instruction, Single Data

Why this design?

• Simplicity: One control unit, one ALU, straightforward pipeline
• Determinism: Instruction N always completes before instruction N+1 starts
• Low hardware cost: No coordination overhead

What it looks like internally:

Control Unit (CU) → Issues ONE instruction
        ↓
Processing Unit (PU) → Operates on ONE data element
        ↓
Memory → Holds program + data sequentially

Execution trace (4 elements: [10, 20, 30, 40]):

Cycle 1: Fetch ADD, Decode, Execute: sum = 0 + 10 = 10
Cycle 2: Fetch ADD, Decode, Execute: sum = 10 + 20 = 30
Cycle 3: Fetch ADD, Decode, Execute: sum = 30 + 30 = 60
Cycle 4: Fetch ADD, Decode, Execute: sum = 60 + 40 = 100

Total time: 4 × T (where T = time for one ADD operation)

Why this step? Each iteration must complete before the next starts because sum depends on the previous result. No parallelism.

Real examples: Original8086, early ARM cores, simple microcontrollers (Arduino Uno's ATmega328P).

2. SIMD: Single Instruction, Multiple Data

Why this design?

• Data parallelism: When the same operation applies to many data points (images, vectors, audio samples)
• Efficiency: One instruction fetch/decode for N operations → lower instruction bandwidth
• Predictability: All PUs stay synchronized (lockstep execution)

What it looks like internally:

Control Unit (CU) → Broadcasts ONE instruction
        ↓
PU₁    PU₂    PU₃    PU₄  → All execute same operation
 ↓      ↓      ↓
Data₁  Data₂  Data₃  Data₄ → Different data elements

Derivation from first principles:

• SISD time for N elements: Each requires one operation of duration T → Total = N·T
• SIMD time for N elements: All N operations execute in parallel in one broadcast → Total = T
• Speedup = N (assuming perfect parallelism, no overhead)

Why this works? When data elements are independent (no dependencies between array[0] and array[1]), we can process them simultaneously.

Execution trace (same 4 elements: [10, 20, 30, 40]):

Cycle 1: Broadcast ADD instruction
  PU₁: 0 + 10 = 10┐
  PU₂: 0 + 20 = 20 ├─ All happen simultaneously
  PU₃: 0 + 30 = 30 │
  PU₄: 0 + 40 = 40 ┘

Total time: 1 × T (4× faster than SISD!)

Why this step? Broadcasting one instruction to four PUs means we fetch/decode once but execute four times. The four additions happen in the same clock cycle because they're independent.

Real examples:

• GPUs: Thousands of SIMD cores (CUDA cores, shader units)
• x86 Extensions: SSE (128-bit, 4 floats), AVX-512 (512-bit, 16 floats)
• ARM NEON: Mobile SIMD for multimedia

Why it feels right: The hardware can process 8 elements simultaneously, so theoretically 8× speedup.

The fix: SIMD speedup requires:

1. Data parallelism: Operations must be independent (no sum += sum + x)
2. Alignment: Data must be packed correctly in memory (16-byte boundaries for SSE)
3. Vector length: If you have 10 elements and 8 lanes, you need 2 iterations (overhead)
4. Load/store overhead: Moving data to/from vector registers isn't free

Real speedup: Typically 2-4× on good code, rarely the full N×.

3. MIMD: Multiple Instruction, Multiple Data

Why this design?

• Task parallelism: Different threads do different work (one renders graphics, one handles physics, one does AI)
• Flexibility: Each core can run completely independent code
• General-purpose: Handles both data paralelism (by running identical code) and task parallelism

What it looks like internally:

CU₁ → PU₁ (Instruction A on Data₁)
CU₂ → PU₂ (Instruction B on Data₂)
CU₃ → PU₃ (Instruction C on Data₃)
CU₄ → PU₄ (Instruction D on Data₄)

Each pair (CU, PU) is essentially an independent processor.

Why MIMD here? These three tasks are completely different algorithms. SIMD can't help (no common instruction), but MIMD runs them in parallel.

Execution trace (conceptual, 3 time slices):

Time 0-10ms:
  Core 1: parse_headers()     ← Different instruction
  Core 2: resize()            ← Different instruction  
  Core 3: mark_reachable()    ← Different instruction

All executing simultaneously, each at their own pace.

Real examples:

• Modern CPUs: Intel Core i7 (4-8 cores), AMD Ryzen (8-16 cores)
• Servers: Dual-socket Xeon (48+ cores)
• Supercomputers: Thousands of nodes, each a MIMD processor

MIMD Sub-Categories

1. Shared Memory (SMP - Symmetric Multiprocessing)

• All cores access the same RAM
• Example: Your laptop's quad-core CPU
• Challenge: Cache coherence (if Core 1 writes X=5, Core 2 must see it)

2. Distributed Memory (MP - Massively Parallel Processing)

• Each core has private RAM
• Example: Supercomputer clusters
• Challenge: Explicit message passing (MPI libraries)

Where:

• $S(N)$ = speedup with N cores
• $P$ = fraction of code that's paralelizable (0 to 1)
• $1-P$ = serial fraction (must run one core)

Derivation from first principles:

Step 1: Total time with1 core = T

• Parallel portion: $P \cdot T$
• Serial portion: $(1-P) \cdot T$

Step 2: Time with N cores

• Parallel portion runs N× faster: $\frac{P \cdot T}{N}$
• Serial portion unchanged: $(1-P) \cdot T$
• Total: $T(N) = (1-P) \cdot T + \frac{P \cdot T}{N}$

Step 3: Speedup = $\frac{T}{T(N)} = \frac{T}{(1-P) \cdot T + \frac{P \cdot T}{N}} = \frac{1}{(1-P) + \frac{P}{N}}$

Why this matters: If5% of code is serial ($P=0.95$), even with infinite cores, max speedup is $\frac{1}{0.05} = 20×$. The serial bottleneck dominates.

With 4 cores: $S(4) = \frac{1}{0.1 + \frac{0.9}{4}} = \frac{1}{0.1 + 0.225} = \frac{1}{0.325} \approx 3.08×$

Why only 3.08× with 4 cores? That10% serial part forces all cores to wait. If the serial part takes 10 seconds, the parallel part (originally 90seconds on 1 core) now takes $\frac{90}{4} = 22.5$ seconds. Total: 32.5 seconds vs. 100 seconds original → 3.08× speedup.

With 100 cores: $S(100) = \frac{1}{0.1 + \frac{0.9}{100}} = \frac{1}{0.109} \approx 9.17×$

Diminishing returns: Adding 96 more cores (4 → 100) only gains 6× more speedup because you're hitting the serial ceiling.

4. MISD: Multiple Instruction, Single Data (Rare)

Why so rare? It's hard to justify multiple different operations on the same data element simultaneously. You'd typically:

• Apply operations sequentially (pipelining), or
• Apply the same operation to different data (SIMD)

Theoretical example: Fault-tolerant systems where 3 processors run different algorithms on the same input and vote on the result (redundancy for reliability).

Practical relevance: Pipeline processors are sometimes (incorrectly) called MISD because different stages process the same data, but they're more accurately temporal paralelism (one instruction completes as another starts).

Comparison Table

Category	Instruction Streams	Data Streams	Paralelism Type	Example Hardware	Typical Use
SISD	1	1	None (serial)	Old CPUs, microcontrollers	General computing (simple tasks)
SIMD	1	Multiple	Data parallelism	GPUs, SSE/AVX, NEON	Graphics, audio, vector math
MIMD	Multiple	Multiple	Task + Data parallelism	Multi-core CPUs, clusters	Servers, scientific computing
MISD	Multiple	1	Temporal (rare)	Fault-tolerant systems	Redundancy, error checking

Recall Explain to a 12-Year-Old

Imagine you're in a kitchen making sandwiches:

SISD = You make one sandwich at a time, doing every step yourself. Slow but simple.

SIMD = You have a magic knife that cuts10 sandwiches at once when you slice down. Same action (slicing), but on many sandwiches simultane

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, computer banate waqt ek fundamental sawaal aata hai—kya hum ek brain se ek kaam karvayein, ya ek brain se bahut saare same kaam, ya phir bahut saare brains se alag-alag kaam? Flynn's Taxonomy humein iss cheez ko samajhne ki ek clean language deti hai. Yahan do independent axes hote hain: Instruction Stream (kitne instruction sequences chal rahe hain—single ya multiple) aur Data Stream (kitne data elements process ho rahe hain—single ya multiple). Inhi do axes ko combine karke chaar categories banti hain: SISD, SIMD, MISD, aur MIMD. Matlab sawaal sirf "parallel hai ya nahi" nahi, balki "parallel kis dimension mein hai" ban jaata hai—yahi Flynn ka genius hai.

Ab thoda intuition banate hain. SISD matlab classic von Neumann machine—ek instruction, ek data, ek time pe. Jaise array ka sum nikalna, jahan har iteration pichle result pe depend karta hai, isliye N elements ke liye N×T time lagta hai, koi parallelism nahi. SIMD mein ek hi instruction ko multiple data elements pe ek saath apply kiya jaata hai—ek control unit sabhi processing units ko same operation broadcast karta hai. Isse ideal case mein speedup exactly N ho jaata hai, kyunki N operations ek hi broadcast mein parallel chal jaate hain. MIMD mein multiple cores alag-alag programs chalate hain, jaise aapke modern multicore CPUs.

Ye kyun matter karta hai? Kyunki isse decide hota hai ki kaunsa hardware aapke workload ke liye sahi hai. GPUs SIMD machines hain—isiliye wo millions of pixels ya matrix operations, deep learning waale kaam itni tezi se karte hain. Modern CPUs MIMD hain, aur aapka purana calculator SISD tha. Toh agar aap image processing, graphics, ya ML jaise data-heavy kaam kar rahe ho, toh SIMD/GPU chahiye; agar alag-alag independent tasks chala rahe ho toh MIMD. Yahi practical decision hardware selection aur performance optimization mein aapki madad karta hai.