Pipelining, Hazards, Performance Metrics & Enhancement

TAKEAWAYS:

• Pipelining overlaps instruction execution stages to increase throughput, but introduces hazards that stall the pipeline.
• Data hazards (RAW, WAR, WAW) occur when instructions depend on uncompleted results; control hazards arise from branches; structural hazards happen when hardware resources conflict.
• Performance metrics like CPI (Cycles Per Instruction), clock cycles, and MIPS (Million Instructions Per Second) quantify CPU efficiency.
• Techniques like forwarding, delay slots, branch prediction, and speculative execution mitigate hazards and enhance performance.
• Superscalar and out-of-order execution allow multiple instructions to execute simultaneously, improving efficiency.
• Real-world applications include Google’s Tensor Processing Units (TPUs) for AI workloads, WhatsApp’s server pipelines for message processing, and Ncell’s 4G/5G base stations for handling concurrent data streams.

---

1. Introduction to Pipelining

Pipelining is a technique where multiple instructions are overlapped in execution by dividing the instruction processing into smaller stages. Each stage performs a specific task, and the next instruction moves to the next stage while the previous one completes.

Why Pipelining?

• Increases throughput: More instructions complete per unit time.
• Reduces average instruction latency: While individual instructions may take the same time, the system processes multiple instructions simultaneously.
• Efficient resource utilization: Different parts of the CPU (ALU, registers, memory) work concurrently.

Stages of a Classic 5-Stage Pipeline

A typical pipeline consists of the following stages (visualized below):

Stages Explained:

1. IF (Instruction Fetch): Fetch the instruction from memory.
2. ID (Instruction Decode): Decode the instruction and read registers.
3. EX (Execute): Perform arithmetic/logic operations or address calculation.
4. MEM (Memory Access): Access memory (for load/store instructions).
5. WB (Write Back): Write the result back to the register file.

Example: Consider executing the following instructions in a 5-stage pipeline:

LW $t0, 0($t1)   ; Load Word
ADD $t2, $t0, $t3 ; Add
SW $t2, 4($t1)   ; Store Word

• Cycle 1: IF for LW, ID for ADD, EX for SW, MEM for ADD, WB for LW.
• Cycle 2: IF for ADD, ID for SW, EX for ADD, MEM for SW, WB for ADD.
• Cycle 3: IF for SW, ID for (none), EX for SW, MEM for (none), WB for SW.

Throughput Calculation:

• Non-pipelined: 3 cycles per instruction → 3 instructions in 9 cycles.
• Pipelined: 1 instruction per cycle → 3 instructions in 5 cycles (after the initial 3 cycles).

---

2. Hazards in Pipelining

Hazards occur when an instruction in a later stage depends on the result of an instruction in an earlier stage, causing stalls or incorrect execution.

Types of Hazards

---

Data Hazards in Detail

1. Read-After-Write (RAW) Hazard

• Definition: An instruction tries to read a register before the previous instruction has written to it.
• Example:

  ADD $t0, $t1, $t2  ; Writes to $t0 in WB stage
  SUB $t3, $t0, $t4  ; Reads $t0 in ID stage (before WB of ADD)
  

• Solution:
  • Forwarding (Bypassing): Directly pass the result from EX/WB to ID without waiting.
  • Stall (Bubble): Insert a NOP to delay the dependent instruction.

2. Write-After-Read (WAR) Hazard

• Definition: An instruction writes to a register before a later instruction reads it.
• Example:

  SUB $t3, $t0, $t4  ; Reads $t0 in ID stage
  ADD $t0, $t1, $t2  ; Writes to $t0 in WB stage (before SUB reads it)
  

• Solution: Reorder instructions or use forwarding.

3. Write-After-Write (WAW) Hazard

• Definition: Two instructions write to the same register, and the second write overwrites the first.
• Example:

  ADD $t0, $t1, $t2  ; Writes to $t0 in WB stage
  OR  $t0, $t3, $t4  ; Writes to $t0 in WB stage (overwrites ADD)
  

• Solution: Reorder instructions or use forwarding.

---

Control Hazards

Control hazards occur due to branches or jumps. The pipeline does not know the target address until the branch instruction is executed, causing stalls.

Example (Branch Instruction):

BEQ $t0, $t1, label  ; Branch if $t0 == $t1

• Problem: The pipeline fetches the next instruction before knowing if the branch is taken.
• Solutions:
  • Delayed Branch: Place useful instructions in the delay slot (after the branch).
  • Branch Prediction: Predict whether the branch will be taken or not (e.g., always taken, always not taken, or based on history).
  • Speculative Execution: Execute instructions after the branch before confirming the branch outcome.

---

Structural Hazards

Structural hazards occur when two instructions need the same resource simultaneously (e.g., two MEM instructions trying to access memory in the same cycle).

Example:

LW $t0, 0($t1)   ; Memory access in MEM stage
SW $t2, 4($t1)   ; Memory access in MEM stage (conflict)

Solutions:

• Pipeline Stalls: Delay one of the instructions.
• Dual-Port Memory: Allow multiple memory accesses simultaneously.
• Separate Data/Instruction Caches: Reduce contention.

---

3. Performance Metrics

Performance is measured using several key metrics:

Example Calculation:

• A CPU executes 100 instructions in 200 cycles.
  • CPI = 200 cycles / 100 instructions = 2 cycles/instruction.
  • If clock frequency = 2 GHz (0.5 ns per cycle), then:
    • MIPS = 100 instructions / (2 × 0.5 ns) = 100,000,000 instructions/second = 100 MIPS.

---

4. Performance Enhancement Techniques

To improve pipeline performance, several techniques are used:

1. Forwarding (Bypassing)

• Definition: Directly passes the result from the EX or MEM stage to the ID stage, avoiding stalls.
• Example:

  ADD $t0, $t1, $t2  ; Result ready in EX stage
  SUB $t3, $t0, $t4  ; Reads $t0 in ID stage (forwarded from EX of ADD)
  

• Advantage: Reduces stalls caused by RAW hazards.

---

2. Delayed Branches

• Definition: Places useful instructions in the delay slot (the instruction immediately after a branch).
• Example:

  BEQ $t0, $t1, label  ; Branch
  ADD $t2, $t3, $t4    ; Delay slot instruction (executed regardless of branch)
  label: ...
  

• Advantage: Reduces branch penalty by keeping the pipeline busy.

---

3. Branch Prediction

• Definition: Predicts whether a branch will be taken or not before execution.
• Techniques:
  • Static Prediction: Always predict taken/not taken (simple but inaccurate).
  • Dynamic Prediction: Uses branch history (e.g., last 2 bits) to predict.
  • Speculative Execution: Executes instructions after the branch before confirming the outcome.
• Example:
  • In WhatsApp’s server pipelines, branch prediction is used to handle millions of concurrent message routing decisions efficiently.

---

4. Superscalar Execution

• Definition: Executes multiple instructions per cycle by having multiple execution units (e.g., ALUs, FPUs).
• Example:
  • A CPU with 4 execution units can execute 4 instructions simultaneously if no dependencies exist.
• Advantage: Increases throughput without increasing clock speed.

---

5. Out-of-Order Execution

• Definition: Allows instructions to execute as soon as their operands are ready, rather than in program order.
• Example:

  ADD $t0, $t1, $t2  ; Depends on $t1 and $t2
  LW  $t1, 0($t3)    ; Loads $t1 (takes longer)
  SUB $t4, $t0, $t5  ; Depends on $t0 (can execute after ADD completes)
  

  • The SUB instruction can execute as soon as ADD completes, even if LW is still in progress.
• Advantage: Hides memory latency and improves performance.

---

6. Very Long Instruction Word (VLIW)

• Definition: Compiles multiple instructions into a single wide instruction to exploit ILP (Instruction-Level Parallelism).
• Example:
  • A VLIW instruction might encode 4 operations to be executed in parallel.
• Advantage: Simplifies hardware design for parallel execution.

---

5. Real-World Applications

1. Google’s Tensor Processing Units (TPUs)

• Application: AI/ML workloads (e.g., Google Search, YouTube recommendations).
• Pipelining Idea Used:
  • Matrix multiplication pipelines: Break down large matrix operations into smaller stages (e.g., fetch, multiply, accumulate) to process multiple operations simultaneously.
  • Speculative execution: Predicts likely branches in neural network computations to keep pipelines busy.

2. WhatsApp’s Server Pipelines

• Application: Real-time message processing for billions of users.
• Pipelining Idea Used:
  • Message routing pipelines: Messages are processed in stages (authentication → encryption → delivery) with overlapping execution.
  • Branch prediction: Handles conditional logic (e.g., "if message is a media file, route to CDN") efficiently.

3. Ncell’s 4G/5G Base Stations

• Application: Handling thousands of concurrent data streams.
• Pipelining Idea Used:
  • Packet processing pipelines: Each data packet is processed in stages (decoding → routing → encryption) with pipelined execution.
  • Out-of-order execution: Prioritizes critical packets (e.g., VoIP) over less urgent data.

4. Daraz’s Order Fulfillment System

• Application: E-commerce order processing.
• Pipelining Idea Used:
  • Order processing stages: Payment verification → inventory check → shipping dispatch (overlapped execution).
  • Branch prediction: Predicts common paths (e.g., "if payment fails, cancel order").

---

6. Worked Example: Pipelined Execution with Hazards

Problem: Execute the following instructions in a 5-stage pipeline and identify hazards:

LW  $t0, 0($t1)   ; Load Word
ADD $t2, $t0, $t3 ; Add
SW  $t2, 4($t1)   ; Store Word

Solution:

Explanation:

• Cycle 3: ADD tries to read $t0 in ID stage, but LW writes to $t0 in WB stage → RAW hazard.
• Solution: Insert a NOP (No Operation) in Cycle 4 to delay SW and allow LW to complete.

Throughput:

• Without stalls: 3 instructions in 5 cycles (1 instruction per cycle after Cycle 3).
• With stalls: 3 instructions in 7 cycles (due to 2 NOPs).

---

7. Comparison: Pipelining vs. Non-Pipelining

---

8. Advanced Techniques: Superscalar vs. Out-of-Order Execution

Example (Out-of-Order Execution):

LW  $t0, 0($t1)   ; Takes 3 cycles (memory latency)
ADD $t2, $t0, $t3 ; Can execute as soon as $t0 is ready (after LW completes)
SUB $t4, $t5, $t6 ; Independent, can execute anytime

• Order of Execution:
  1. LW starts (Cycle 1).
  2. SUB executes immediately (Cycle 1, if no dependencies).
  3. ADD executes as soon as LW completes (Cycle 3).

---

9. Real Picture: Modern CPU Pipeline

---

10. Exam Tip

What Examiners Look For

1. Definitions:

   • Clearly define pipelining, hazards (RAW, WAR, WAW, control, structural), and performance metrics (CPI, MIPS).
   • Example: "Pipelining is a technique to overlap instruction execution stages to increase throughput."

2. Hazard Identification and Solutions:

   • For any given instruction sequence, identify hazards and propose solutions (stalls, forwarding, reordering).
   • Example: In ADD $t0, $t1, $t2 followed by SUB $t3, $t0, $t4, identify the RAW hazard and explain forwarding or stall.

3. Performance Calculations:

   • Calculate CPI, MIPS, and throughput given clock cycles and instructions.
   • Example: "A CPU executes 50 instructions in 100 cycles with a 2 GHz clock. Calculate CPI and MIPS."

4. Real-World Applications:

   • Relate pipelining concepts to Google TPUs, WhatsApp servers, or Ncell 4G base stations.
   • Example: "Explain how branch prediction in WhatsApp’s message routing pipeline reduces latency."

5. Comparison Tables:

   • Compare pipelining vs. non-pipelining, superscalar vs. out-of-order execution, or forwarding vs. stalls.
   • Example:

     Technique	Pros	Cons
     Forwarding	No stalls, fast	Complex hardware
     Stalls	Simple to implement	Reduces throughput

6. Worked Examples:

   • Always draw a pipeline diagram (like the 5-stage pipeline above) and fill in cycles for hazard analysis.
   • Example: For LW, ADD, SW, show stalls and explain why.

Common Mistakes to Avoid

• Ignoring hazards: Always check for RAW, WAR, WAW, control, and structural hazards in instruction sequences.
• Incorrect CPI calculation: Remember, CPI = Total Cycles / Total Instructions (not per instruction).
• Overlooking real-world ties: Examiners love Google TPUs, WhatsApp, or Ncell examples—always link theory to practice.
• Forgetting forwarding: Many hazards can be resolved with forwarding, not just stalls.

Quick Revision Checklist

Before the exam, ensure you can: ✅ Explain the 5 stages of a pipeline and their roles. ✅ Identify all 3 types of hazards and their solutions. ✅ Calculate CPI, MIPS, and throughput for given scenarios. ✅ Draw a pipeline diagram with stalls for a given instruction sequence. ✅ Compare superscalar vs. out-of-order execution. ✅ Relate pipelining to real-world systems (Google, WhatsApp, Ncell).

---

Final Note: Pipelining is about overlapping execution but requires careful hazard management. Master the stages, hazards, and solutions, and you’ll ace this unit! 🚀