Pipelining Hazards and Performance

TL;DR

Pipelining speeds up instruction execution by overlapping stages, but sometimes instructions can't proceed as planned due to hazards. These hazards—structural, data, and control—force stalls, reducing the performance benefits of pipelining. Understanding and mitigating these hazards is crucial for efficient processor design.

1. The Mental Model

Imagine an assembly line where each worker does one small task on a product. Pipelining is like that, with each instruction moving through different stages. Hazards are like unexpected slowdowns or blockages on the line that stop the smooth flow of products (instructions).

2. The Core Material

Pipelining aims to complete one instruction per clock cycle, achieving an ideal CPI (Cycles Per Instruction) of 1. However, this ideal isn't always met because of hazards, which are situations that prevent the next instruction in the pipeline from executing in its designated clock cycle. When a hazard occurs, the pipeline has to stall (pause) or flush (discard) instructions, which adds cycles and increases the effective CPI.

There are three main types of hazards:

Structural Hazards

A structural hazard occurs when two instructions need the same hardware resource at the same time. Think of two products on an assembly line needing the same tool at the exact same moment.

• Example: If your processor has only one memory unit that handles both instruction fetches and data accesses (loads/stores). An instruction in the 'Instruction Fetch' (IF) stage might try to access memory at the same time a 'Memory Access' (MEM) stage instruction tries to write data to memory.
• Mitigation:
  • Duplication of resources: Provide separate instruction and data caches/memories (Harvard architecture). This is the most common solution.
  • Increased bandwidth: Design memory that can handle multiple accesses simultaneously.

Data Hazards

Photo by panumas nikhomkhai on Pexels

A data hazard arises when an instruction depends on the result of a previous instruction that hasn't yet been computed and written back. This is like one worker needing a part that the previous worker hasn't finished making yet.

Data hazards are often classified as:

• RAW (Read After Write): True Dependency: An instruction tries to read a register before a previous instruction has written to it. This is the most common type.
• WAR (Write After Read): Anti-dependency: An instruction tries to write to a register before a previous instruction has read its old value. Less common in simple pipelines, often due to register renaming.

• WAW (Write After Write): Output Dependency: An instruction tries to write to a register before a previous instruction has written its result to the same register. Less common in simple pipelines, often due to out-of-order execution or register renaming.

• Mitigation for RAW Hazards (most critical):

  • Pipeline Stalls (Bubbles): Insert 'NOP' (No Operation) instructions or simply stall the pipeline until the data is ready. This is simple but inefficient.
  • Forwarding/Bypassing: The most common and effective solution. The result of an instruction is forwarded directly from an earlier pipeline stage (e.g., EX or MEM) to a later stage that needs it, without waiting for it to be written back to the register file.
  • Compiler Scheduling: The compiler can reorder instructions to move independent instructions between dependent ones, reducing stalls.

Control Hazards (Branch Hazards)

Photo by João Jesus on Pexels

A control hazard occurs when the pipeline doesn't know which instruction to fetch next because a branch instruction's outcome (taken or not taken) isn't decided until later in the pipeline. This is like an assembly line needing to decide which path to take, but the decision-maker is far down the line.

• Example: If you have an if statement, the processor doesn't know which block of code to execute until the branch condition is evaluated, usually in the EX stage. Meanwhile, instructions after the branch are already being fetched.
• Mitigation:
  • Stall until Branch Resolution: Simplest but very costly, especially for short pipelines.
  • Predict Not Taken: Assume the branch isn't taken and continue fetching instructions sequentially. If the prediction is wrong, flush the pipeline and refetch from the correct target.
  • Predict Taken: Assume the branch is taken and fetch from the target address. Requires knowing the target address early (e.g., using a Branch Target Buffer - BTB).
  • Branch Prediction: Use hardware mechanisms (like a Branch Predictor) to guess the outcome of a branch based on past behavior. If the prediction is wrong, a pipeline flush occurs (all incorrectly fetched instructions are discarded), leading to a misprediction penalty.
  • Delayed Branch: The compiler inserts useful (independent) instructions immediately after the branch that will execute regardless of the branch outcome. This "fills" the delay slots.

Here's how pipeline stages and hazards relate:

graph TD
    IF[Instruction Fetch] --> ID[Instruction Decode/Register Fetch]
    ID --> EX[Execute]
    EX --> MEM[Memory Access]
    MEM --> WB[Write Back]

    IF -- Structural Hazard (Mem) --> IF
    ID -- Data Hazard (RAW) --> EX
    EX -- Data Hazard (Forwarding) --> EX
    EX -- Control Hazard (Branch Outcome) --> IF

In this diagram:
* Normal flow is left to right.
* Arrows pointing backward or to earlier stages indicate a hazard requiring a stall or flush.
* The "Forwarding" arrow from EX back to EX (or ID, not explicitly shown but implied) represents data being made available earlier.

Performance Impact

The performance of a pipelined processor is often measured by its effective CPI.
$$ \text{Effective CPI} = \text{Ideal CPI (usually 1)} + \text{Stall Cycles Per Instruction} $$
Stall cycles per instruction are caused by hazards. Minimizing these stall cycles directly improves performance.

3. Worked Example

Let's consider a simple 5-stage pipeline (IF, ID, EX, MEM, WB) without forwarding initially, and then with forwarding.

Scenario 1: No Forwarding

ADD R1, R2, R3    ; R1 = R2 + R3
SUB R4, R1, R5    ; R4 = R1 - R5
AND R6, R1, R7    ; R6 = R1 & R7

Let's trace SUB R4, R1, R5: It needs R1.
* ADD writes to R1 in its WB stage.
* SUB reads R1 in its ID stage.

Without forwarding, SUB must wait until ADD completes its WB stage.

• ADD finishes WB in cycle 5. R1 is updated.
• SUB needs R1 in ID in cycle 3. It stalls for 2 cycles until ADD writes R1 back.
• AND also needs R1. It too stalls.

Total cycles: 8. The SUB instruction introduces a 2-cycle stall. The AND instruction introduces another 2-cycle stall (even though it's dependent on the same R1, it needs to wait for R1 to be available for its ID stage).

Scenario 2: With Forwarding
The result of ADD R1, R2, R3 is available at the end of its EX stage (cycle 3) and can be forwarded.

• ADD produces R1 at the end of cycle 3 (EX stage).
• SUB needs R1 in its EX stage in cycle 4. The value is forwarded directly from ADD's EX stage to SUB's EX stage. No stall!
• AND also needs R1 in its EX stage in cycle 5. The value is forwarded. No stall!

Total cycles: 6. Forwarding eliminated the stalls and significantly improved performance.

4. Key Takeaways

• Pipelining aims for an ideal CPI of 1, but hazards prevent this.
• Structural hazards occur when multiple instructions need the same hardware resource simultaneously.
• Data hazards arise when an instruction needs data not yet produced by a prior instruction, primarily RAW dependencies.
• Control hazards happen with branches, as the next instruction to fetch depends on an outcome determined later in the pipeline.
• Forwarding (bypassing) is a critical technique to mitigate data hazards by providing results directly from earlier pipeline stages.
• Branch prediction attempts to guess branch outcomes to reduce control hazard penalties; mispredictions cause costly flushes.
• Pipeline stalls (bubbles) are introduced when hazards cannot be fully resolved, increasing the effective CPI.
• Minimizing stall cycles is key to achieving maximum performance benefits from pipelining.

Common Mistakes to Avoid

• Confusing hazard types: Remember: structural = hardware conflict, data = value dependency, control = branch uncertainty.
• Underestimating stall costs: Even a single stall cycle for a common instruction can significantly impact overall performance.
• Ignoring compiler's role: The compiler can optimize instruction ordering to reduce certain hazards (e.g., reordering for RAW dependencies).
• Thinking forwarding solves all data hazards: Forwarding helps RAW hazards where the producer is just a few stages ahead; it can't fix all data dependencies instantly.
• Forgetting misprediction penalties: Incorrect branch predictions don't just delay; they also waste work by flushing the pipeline.

5. Now Try It

Consider the following MIPS-like code snippet executing on a 5-stage pipeline (IF, ID, EX, MEM, WB) with forwarding.

LW R1, 0(R2)      ; Load Word R1 = Memory[R2 + 0]
ADD R3, R1, R4    ; R3 = R1 + R4
What kind of hazard does the `ADD` instruction face with respect to `LW`? How many cycles would this program take to execute compared to an ideal scenario without hazards?

**What to do:**
1.  Identify the type of hazard between `LW R1, 0(R2)` and `ADD R3, R1, R4`.
2.  Determine if forwarding can resolve this hazard.
3.  Draw a pipeline diagram (like the one in Section 3, but simplified to show only cycles and stages) for these two instructions to show exactly when the result of `LW` is available and when `ADD` needs it.
4.  Calculate the total number of clock cycles required for these two instructions to complete, assuming the pipeline starts empty and no other instructions are involved.

**What success looks like:**
You'll identify a data hazard. You'll explain why this specific hazard cannot be fully resolved by standard forwarding alone (the "load-use" delay). Your pipeline diagram will correctly show a 1-cycle stall for the `ADD` instruction, and you'll conclude that the execution takes 6 cycles (for two instructions) instead of the ideal 5 cycles.