Pipelining & Parallel Processing: Hazards, Flynn’s Taxonomy & Real-World Speedups

TAKEAWAYS:

• Pipelining improves CPU throughput by overlapping instruction execution stages (fetch, decode, execute, memory, write-back) but introduces hazards that require stalls, forwarding, or branch prediction.
• Flynn’s taxonomy classifies parallel systems by instruction and data streams: SISD (single-core CPU), SIMD (GPUs, vector processors), MISD (rare), and MIMD (multi-core CPUs, cloud servers).
• Pipeline hazards—structural (resource conflicts), data (read-after-write dependencies), and control (branches)—are mitigated by techniques like register renaming, delayed branching, and speculative execution.
• Vector processing (SIMD) accelerates math-heavy tasks (e.g., video encoding, scientific simulations) by processing multiple data elements in parallel with a single instruction.
• Parallel processing benefits include faster execution, energy efficiency, and scalability, but faces challenges like Amdahl’s Law and load balancing.
• Real-world examples: YouTube’s transcoding uses SIMD for parallel video encoding; eSewa’s payment processing relies on MIMD servers; Ncell’s call routing uses pipelined switches for low-latency connections.

1. Why Pipelining? The Need for Speed

Modern CPUs execute billions of instructions per second (GIPS), but a single instruction can take hundreds of clock cycles if executed sequentially. Pipelining solves this by overlapping execution stages, like an assembly line where each worker handles one task at a time.

stateDiagram-v2
    [*] --> Fetch: "PC → IR"
    Fetch --> Decode: "Opcode → Control Signals"
    Decode --> Execute: "ALU/Registers"
    Execute --> Memory: "Load/Store"
    Memory --> Writeback: "Write to Register"
    Writeback --> [*]
    note right of Fetch: Stage 1: Fetch instruction from memory
    note right of Decode: Stage 2: Decode opcode and address
    note right of Execute: Stage 3: Execute ALU operations
    note right of Memory: Stage 4: Access memory (if needed)
    note right of Writeback: Stage 5: Write result to register

Key Idea:

• Throughput (instructions/second) increases linearly with pipeline depth.
• Latency (time per instruction) remains similar to a non-pipelined CPU.
• Example: A 5-stage pipeline with 1ns per stage processes 1 instruction every 1ns (vs. 5ns sequentially).

2. Pipeline Stages in Detail

A classic 5-stage pipeline (used in RISC architectures like MIPS) breaks execution into:

Visual Trace:

Cycle | F    | D          | E          | M       | W
------|------|------------|------------|---------|-------
1     | L1   |            |            |         |
2     | L2   | Decode L1   |            |         |
3     | L3   | Decode L2   | Execute L1 |         |
4     | L4   | Decode L3   | Execute L2 | M L1    |
5     | L5   | Decode L4   | Execute L3 | M L2    | W L1

• Throughput: 1 instruction per cycle (after pipeline fills).
• Latency: 5 cycles (same as non-pipelined).

3. Pipeline Hazards: The Speed Bumps

Hazards occur when a later instruction depends on an earlier one, forcing stalls (idle cycles). There are three types:

A. Structural Hazards

Cause: Two instructions need the same resource simultaneously (e.g., memory or ALU). Example:

• ADD R1, R2, R3 (needs ALU) and LW R4, 0(R5) (needs memory) in the same cycle. Solution:
• Hardware duplication: Add more ALUs/memory ports (e.g., superscalar CPUs).
• Stall: Delay the second instruction.

stateDiagram-v2
    [*] --> ALU_Busy: "ADD R1, R2, R3"
    ALU_Busy --> Stall: "LW R4, 0(R5) waits"
    Stall --> ALU_Free: "Cycle lost"
    ALU_Free --> [*]

B. Data Hazards

Cause: An instruction depends on the result of a previous instruction not yet written back. Types:

1. RAW (Read-After-Write): ADD R1, R2, R3 → SUB R4, R1, R5 (R1 not ready).
2. WAW (Write-After-Write): Two instructions write to the same register.
3. WAR (Write-After-Read): An instruction reads a register before it’s written.

Solutions:

• Forwarding (Bypassing): Copy data directly from EX/M to EX/W stage.

  graph LR
    EX["Execute: ADD R1, R2, R3"] -->|"Forward"| MEM["Memory: SUB R4, R1, R5"]
    MEM --> WB["Writeback: R1 = 10"]

• Stall: Insert a bubble (NOOP) to let the result propagate.
• Register Renaming: Assign temporary registers to break dependencies.

Worked Example (RAW Hazard):

ADD R1, R2, R3   ; Cycle 1: F, 2: D, 3: E, 4: M, 5: W
SUB R4, R1, R5   ; Needs R1 from ADD, but ADD writes back in cycle 5.

Fix: Stall SUB until cycle 4 (forwarding) or cycle 5 (no forwarding).

C. Control Hazards

Cause: Branches/jumps change the PC, flushing the pipeline. Example:

BEQ R1, R2, LOOP ; Branch if R1 == R2

Solutions:

• Delayed Branch: Execute the next instruction regardless (used in MIPS).
• Branch Prediction: Guess the outcome (e.g., predict "not taken").
• Speculative Execution: Execute both paths, discard the wrong one later.

Branch Prediction Accuracy:

4. Reducing Hazards: Real Techniques

5. Parallel Processing: Flynn’s Taxonomy

Parallelism exploits multiple processing units to speed up tasks. Michael Flynn classified systems into four types:

classDiagram
    class System {
        <<abstract>>
        +Instruction Stream
        +Data Stream
    }
    class SISD {
        +Single Instruction, Single Data
        +Example: Single-core CPU
    }
    class SIMD {
        +Single Instruction, Multiple Data
        +Example: GPUs, vector processors
    }
    class MISD {
        +Multiple Instruction, Single Data
        +Example: Rare (e.g., fault-tolerant systems)
    }
    class MIMD {
        +Multiple Instruction, Multiple Data
        +Example: Multi-core CPUs, clusters
    }
    System <|-- SISD
    System <|-- SIMD
    System <|-- MISD
    System <|-- MIMD

Real-World SIMD Example:

• YouTube’s Video Encoding: Uses SIMD instructions (e.g., AVX-512) to encode multiple pixels in parallel, reducing transcoding time by 10x.
• Ncell’s Call Routing: SIMD processes multiple voice packets simultaneously in base stations.

6. Vector Processing (SIMD in Depth)

Vector processors (e.g., early Cray supercomputers) use SIMD to process arrays of data with a single instruction. Modern CPUs have SIMD extensions:

• MMX (Intel, 1996): 64-bit multimedia instructions.
• SSE/AVX (Intel/AMD): 128-bit/256-bit/512-bit operations.
• NEON (ARM): Used in mobile CPUs for photo/video processing.

Example: Dot Product Calculation

; Pseudocode for SIMD dot product (4 floats at once)
VLD1.64 {Q0}, [R0]   ; Load 4 floats from memory into Q0
VLD1.64 {Q1}, [R1]   ; Load 4 floats from memory into Q1
VMUL.F32 Q2, Q0, Q1  ; Multiply corresponding elements
VPADD.F32 D0, D0, D1 ; Sum results

Speedup: Processes 4 floats in 1 cycle vs. 4 cycles sequentially.

7. Parallel Processing in Nepal: Real Applications

Worked Example: Ncell’s Call Routing

• Problem: A base station must route 10,000 calls/sec with <10ms latency.
• Solution: Uses SIMD processors to handle 100 calls per cycle (100MHz clock).
• Pipeline: Each call goes through:
  1. Fetch (SIMD load call data)
  2. Decode (SIMD check routing table)
  3. Execute (SIMD assign channel)
  4. Memory (SIMD update switch table)
  5. Writeback (SIMD send to tower)

8. Pipelining vs. Parallel Processing: Comparison

Amdahl’s Law: $$\text{Speedup}=\frac{1}{(1-P)+\frac{P}{N}}$$

• $P$ = Fraction of work parallelizable.
• $N$ = Number of processors. Example: If 20% of code is sequential, max speedup with 8 cores is 1.25x (not 8x!).

9. Advanced Topics: Superscalar and VLIW

A. Superscalar CPUs

• Idea: Execute multiple instructions per cycle (e.g., Intel Pentium, Core i7).
• Techniques:
  • Dynamic Scheduling: Hardware reorders instructions to avoid stalls.
  • Out-of-Order Execution: Completes independent instructions early.
  • Wide Issue: 3–4-wide (e.g., Apple M1 has 8-wide decode).

B. Very Long Instruction Word (VLIW)

• Idea: Compiler packs multiple operations into a single wide instruction (e.g., TI C6x DSPs).
• Pros: No hardware hazard detection needed.
• Cons: Hard to program; limited to specialized domains (DSPs, embedded).

10. Exam Tip: How to Score Full Marks

1. Define Clearly:
   • Start every answer with a one-sentence definition (e.g., "Pipelining is a technique to overlap instruction execution stages to improve CPU throughput.").
2. Draw Diagrams:
   • For hazards, show a pipeline stall diagram (like the stateDiagram above).
   • For Flynn’s taxonomy, use a 4-box table (SISD/SIMD/MISD/MIMD).
3. Compare RISC/CISC:
   • Always mention pipelining support in RISC vs. CISC when asked to differentiate.
4. Real-World Links:
   • Tie hazards to eSewa’s transaction processing (data hazards in concurrent writes) or Ncell’s call drops (control hazards in branch mispredictions).
5. Math for Speedup:
   • If asked about Amdahl’s Law, show the formula and plug in numbers (e.g., 80% parallelizable → max 5x speedup with 8 cores).
6. Avoid Vague Terms:
   • ❌ "Pipelining reduces latency." → ✅ "Pipelining reduces latency per instruction but increases throughput by overlapping stages."

11. Common Pitfalls in Exams

• Confusing Hazards:
  • Structural = hardware conflict (e.g., two instructions needing the ALU).
  • Data = dependency (e.g., ADD before SUB using its result).
  • Control = branches (e.g., BEQ flushing the pipeline).
• Ignoring Solutions:
  • Always mention how hazards are resolved (e.g., forwarding for RAW, BTB for control).
• Overlooking Flynn’s Taxonomy:
  • Memorize the four types and one real-world example per type (e.g., SIMD = GPUs).
• Assuming All Parallelism Helps:
  • Amdahl’s Law limits speedup for sequential code. Always calculate!

12. Practice Questions (Self-Check)

1. Short Answer:
   • What is the difference between a structural hazard and a data hazard? Give an example of each.
2. Diagram:
   • Draw a 5-stage pipeline and show how a BEQ instruction causes a control hazard.
3. Calculation:
   • If a program is 60% parallelizable, what is the maximum speedup with 16 processors? (Use Amdahl’s Law.)
4. Application:
   • How does Khalti’s payment processing use parallel processing? Classify it using Flynn’s taxonomy.

13. Summary Table: Key Concepts