Flynn's taxonomy (SISD - SIMD - MIMD) — Hinglish notes

6.1.1 · Hardware › Parallelism & Multicore

Core Principle: Do Orthogonal Axes

Isse hume chaar fundamental categories milti hain: SISD, SIMD, MISD, MIMD.

Yeh Do Axes Kyun?

Iska genius yeh hai ki yeh recognize karta hai ki parallelism do levels par ho sakti hai:

Instruction-level: System ke alag-alag parts alag-alag instructions execute karte hain
Data-level: Ek hi instruction ek saath multiple data elements par apply hoti hai

Traditional soch: "Parallel hai ya nahi?" (binary). Flynn: "Parallel kis dimension mein?" (structured).

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

1. SISD: Single Instruction, Single Data

Yeh design kyun?

Simplicity: Ek control unit, ek ALU, seedha pipeline
Determinism: Instruction N hamesha complete hoti hai instruction N+1 se pehle
Kam hardware cost: Koi coordination overhead nahi

Andar se kaisa dikhta hai:

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 (jahan T = ek ADD operation ka time)

Yeh step kyun? Har iteration complete hona zaroori hai agle se pehle kyunki sum pichle result par depend karta hai. Koi parallelism nahi.

Real examples: Original 8086, early ARM cores, simple microcontrollers (Arduino Uno ka ATmega328P).

2. SIMD: Single Instruction, Multiple Data

Yeh design kyun?

Data parallelism: Jab same operation bahut saare data points par apply hoti hai (images, vectors, audio samples)
Efficiency: N operations ke liye ek instruction fetch/decode → kam instruction bandwidth
Predictability: Saare PUs synchronized rehte hain (lockstep execution)

Andar se kaisa dikhta hai:

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

First principles se derivation:

N elements ke liye SISD time: Har ek ke liye duration T ka ek operation → Total = N·T
N elements ke liye SIMD time: Saare N operations parallel mein ek broadcast mein execute → Total = T
Speedup = N (perfect parallelism assume karte hue, koi overhead nahi)

Yeh kyun kaam karta hai? Jab data elements independent hain (array[0] aur array[1] ke beech koi dependency nahi), toh hum unhe ek saath process kar sakte hain.

Worked example SIMD in Action: Same Array Sum

// Conceptual SIMD pseudocode (like SSE/AVX)
__m128 vec_sum = _mm_setzero_ps();  // Zero vector
for (int i = 0; i < 4; i += 4) {
    __m128 vec_data = _mm_load_ps(&array[i]);  // Load 4 floats
    vec_sum = _mm_add_ps(vec_sum, vec_data);    // 4 adds in parallel
}

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 (SISD se 4× faster!)

Yeh step kyun? Ek instruction chaar PUs ko broadcast karne ka matlab hai hum sirf ek baar fetch/decode karte hain lekin chaar baar execute karte hain. Chaar additions same clock cycle mein hote hain kyunki woh independent hain.

Real examples:

GPUs: Hazaaron SIMD cores (CUDA cores, shader units)
x86 Extensions: SSE (128-bit, 4 floats), AVX-512 (512-bit, 16 floats)
ARM NEON: Multimedia ke liye mobile SIMD

Kyun sahi lagta hai: Hardware sach mein 8 elements ek saath process kar sakta hai, toh theoretically 8× speedup milna chahiye.

Theek kya hai: SIMD speedup ke liye zaroori hai:

Data parallelism: Operations independent hone chahiye (koi sum += sum + x nahi)
Alignment: Data memory mein sahi se packed hona chahiye (SSE ke liye 16-byte boundaries)
Vector length: Agar 10 elements hain aur 8 lanes hain, toh 2 iterations chahiye (overhead)
Load/store overhead: Vector registers mein data laana-lejana free nahi hai

Real speedup: Achhe code par typically 2-4×, rarely poora N×.

3. MIMD: Multiple Instruction, Multiple Data

Yeh design kyun?

Task parallelism: Alag-alag threads alag-alag kaam karte hain (ek graphics render karta hai, ek physics handle karta hai, ek AI karta hai)
Flexibility: Har core bilkul independent code chala sakta hai
General-purpose: Data parallelism (identical code chalake) aur task parallelism dono handle karta hai

Andar se kaisa dikhta hai:

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

Har pair (CU, PU) essentially ek independent processor hai.

Worked example MIMD in Action: Web Server

// Core 1: Handle HTTP request
void handle_request(Request r) {
    parse_headers(r);
    query_database(r);
    send_response(r);
}
 
// Core 2: Process image upload (different code!)
void process_image(Image img) {
    resize(img);
    apply_filter(img);
    save_to_disk(img);
}
 
// Core 3: Run garbage collector
void gc_cycle() {
    mark_reachable_objects();
    sweep_garbage();
}

MIMD yahan kyun? Yeh teen tasks bilkul alag algorithms hain. SIMD help nahi kar sakta (koi common instruction nahi), lekin MIMD inhe parallel mein chala sakta hai.

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: Hazaaron nodes, har ek ek MIMD processor

MIMD Sub-Categories

1. Shared Memory (SMP - Symmetric Multiprocessing)

Saare cores same RAM access karte hain
Example: Aapke laptop ka quad-core CPU
Challenge: Cache coherence (agar Core 1 X=5 likhta hai, toh Core 2 ko woh dikhna chahiye)

2. Distributed Memory (MP - Massively Parallel Processing)

Har core ke paas private RAM hoti hai
Example: Supercomputer clusters
Challenge: Explicit message passing (MPI libraries)

Jahan:

$S (N)$ = N cores ke saath speedup
$P$ = code ka woh fraction jo parallelizable hai (0 se 1)
$1 - P$ = serial fraction (ek core par chalna zaroori hai)

First principles se derivation:

Step 1: 1 core ke saath total time = T

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

Step 2: N cores ke saath time

Parallel portion N× faster chalti hai: $\frac{P \cdot T}{N}$
Serial portion unchanged rehti hai: $(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}}$

Yeh kyun important hai: Agar code ka 5% serial hai ( $P = 0.95$ ), toh infinite cores ke saath bhi max speedup sirf $\frac{1}{0.05} = 20 \times$ hai. Serial bottleneck dominate karta hai.

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

4 cores ke saath sirf 3.08× kyun? Woh 10% serial part saare cores ko wait karwata hai. Agar serial part 10 seconds leta hai, toh parallel part (originally 1 core par 90 seconds) ab $\frac{90}{4} = 22.5$ seconds leta hai. Total: 32.5 seconds vs. original 100 seconds → 3.08× speedup.

100 cores ke saath: $S (100) = \frac{1}{0.1 + \frac{0.9}{100}} = \frac{1}{0.109} \approx 9.17 \times$

Diminishing returns: 96 aur cores add karna (4 → 100) sirf 6× aur speedup deta hai kyunki aap serial ceiling ko hit kar rahe ho.

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

Itni rare kyun? Multiple alag operations ko same data element par simultaneously justify karna mushkil hai. Aap typically ya toh:

Operations sequentially apply karoge (pipelining), ya
Same operation alag data par apply karoge (SIMD)

Theoretical example: Fault-tolerant systems jahan 3 processors same input par alag algorithms chalate hain aur result par vote karte hain (reliability ke liye redundancy).

Practical relevance: Pipeline processors ko kabhi-kabhi (galat tarike se) MISD kaha jaata hai kyunki alag stages same data process karti hain, lekin woh zyada accurately temporal parallelism hai (ek instruction complete hoti hai jab doosri shuru hoti hai).

Comparison Table

Category	Instruction Streams	Data Streams	Parallelism 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 Ek 12-Saal Ke Bacche Ko Samjhao

Socho tum ek kitchen mein sandwiches bana rahe ho:

SISD = Tum ek waqt mein ek sandwich banate ho, har step khud karte ho. Slow lekin simple.

SIMD = Tumhare paas ek magic knife hai jo ek baar mein 10 sandwiches kaat sakti hai jab tum slice karo. Same action (slicing), lekin bahut saari sandwiches par ek saath.