Pipelining & Parallelism: Hazards, Speedup, Flynn’s Taxonomy & Multicore

1. Pipelining: The Assembly Line of Computers

1.1 How Pipelining Works

Pipelining divides instruction execution into stages, like an assembly line. Each stage processes a different instruction simultaneously while passing partial results to the next stage.

graph LR
    A["IF: Instruction Fetch"] --> B["ID: Instruction Decode"]
    B --> C["EX: Execute"]
    C --> D["MEM: Memory Access"]
    D --> E["WB: Write Back"]
    E --> A

Stages in a 5-stage pipeline:

1. IF (Instruction Fetch): Fetch opcode from memory.
2. ID (Instruction Decode): Decode opcode, read registers.
3. EX (Execute): Perform ALU operations (e.g., ADD R1, R2, R3).
4. MEM (Memory Access): Load/store data (if needed).
5. WB (Write Back): Write result to register.

Example: Fetching ADD R1, R2, R3 while decoding SUB R4, R5, R6, executing ADD, etc.

1.2 Pipelining Hazards & Solutions

Hazards occur when stages cannot proceed as planned. There are three types:

stateDiagram-v2
  [*] --> IF
  IF --> ID: Fetch
  ID --> EX: Decode
  EX --> MEM: Execute
  MEM --> WB: Memory Access
  WB --> [*]: Write Back
  EX --> EX: Data Hazard (stall)
  EX --> EX: Forwarding (bypass)
  EX --> EX: Branch Prediction

Worked Example (Data Hazard):

LW R1, 0(R2)   // Load word from memory to R1 (takes 2 cycles)
ADD R3, R1, R4 // Needs R1 (ready in cycle 3)

• Problem: ADD needs R1 in cycle 2, but LW writes R1 in cycle 3 → stall.
• Solution: Forward R1 from MEM stage to EX stage (bypass).

1.3 Speedup & Efficiency

Ideal speedup = Number of pipeline stages (e.g., 5-stage → 5× faster). Real-world speedup is lower due to hazards: $$\text{Speedup}=\frac{\text{Number of stages}}{1+\text{Average stalls per instruction}}$$ Example: A 5-stage pipeline with 1 stall every 10 instructions: $$\text{Speedup}=\frac{5}{1+0.1}=4.55\times$$

2. Flynn’s Taxonomy: Classifying Parallel Computers

Flynn’s taxonomy categorizes computers by instruction stream (I) and data stream (D) parallelism:

Real-World Tie-In:

• YouTube’s transcoding uses SIMD to encode multiple video streams simultaneously on GPUs.
• eSewa’s payment processing uses MIMD: multiple servers handle different transactions in parallel.

3. Multicore & Multiprocessor Systems

3.1 Shared Memory vs. Distributed Memory

Amdahl’s Law: Limits speedup due to sequential bottlenecks. $$\text{Speedup}=\frac{1}{(1-P)+\frac{P}{N}}$$ Where:

• $P$ = Fraction of code parallelizable
• $N$ = Number of cores

Example: If 80% of code is parallelizable ($P=0.8$) on 4 cores: $$\text{Speedup}=\frac{1}{0.2+0.2}=2.5\times$$

3.2 Real-World: Ncell’s Load Balancing

Ncell’s 4G base stations use multicore processors to handle:

• SIMD: Parallel signal processing for multiple users.
• MIMD: Different cores manage handover, billing, and encryption.

4. Pipelining in I/O Systems

4.1 Programmed I/O vs. Interrupt-Driven I/O vs. DMA

Example (DMA in eSewa): When you pay via eSewa, the DMA controller transfers transaction data directly to memory without CPU intervention, reducing latency.

In the Real World

1. YouTube (SIMD):

   • Uses GPU pipelines (SIMD) to encode videos in parallel. A single RTX 3060 can transcode 4K video streams simultaneously using AV1 encoding (SIMD instructions like AVX-512).

2. eSewa (MIMD + Pipelining):

   • MIMD: Multiple servers handle payments, KYC, and notifications in parallel.
   • Pipelining: Transaction processing stages (authentication → deduction → confirmation) overlap like an assembly line.

3. Ncell 5G Base Stations (Multicore + SIMD):

   • Quad-core ARM processors run:
     • Core 1: Signal modulation (SIMD for parallel users).
     • Core 2: Handover management (MIMD).
     • Core 3: Encryption (AES-NI SIMD).
     • Core 4: Billing (sequential).

Exam Tip

1. Pipelining Questions:

   • Always draw the 5-stage pipeline diagram for any hazard question.
   • For speedup: State the formula and plug in numbers (e.g., "3 stalls per 10 instructions → speedup = 5/1.3 ≈ 3.85×").

2. Flynn’s Taxonomy:

   • Memorize the table (SISD/SIMD/MISD/MIMD) and match examples (GPU = SIMD, cloud = MIMD).
   • Common pitfall: Confusing SIMD (same instruction, multiple data) with MIMD (multiple instructions, multiple data).

3. Multicore:

   • Amdahl’s Law is tested: If 90% is parallelizable, even 100 cores give only 10× speedup.
   • NUMA vs. UMA: NUMA has non-uniform access times (critical for databases like eSewa).

4. I/O Methods:

   • Programmed I/O is busy-waiting (bad for high-speed devices like SSDs).
   • DMA is used in network cards, GPUs, and storage controllers (e.g., NVMe SSDs).

Label stages IF/ID/EX/MEM/WB with arrows showing overlap. (Image: Inductiveload, Public domain, via Wikimedia Commons)

In the real world

• YouTube (SIMD): Uses NVIDIA GPUs (e.g., RTX 3060) with AV1 encoding to process 4K video streams in parallel via SIMD instructions like AVX-512, reducing transcoding time by ~80% compared to single-core CPUs.
• eSewa (MIMD + Pipelining): MIMD distributes transactions across servers (e.g., Core 1: Authentication, Core 2: Deduction, Core 3: Confirmation), while pipelining overlaps stages (e.g., KYC check → payment → notification) to handle 10,000+ transactions/sec.
• Ncell 5G (Multicore + SIMD): Quad-core ARM processors in base stations use SIMD for parallel signal processing (e.g., FFT for 4G/5G modulation) and MIMD for handover management, reducing latency by ~30% vs. single-core systems.