Pipeline Hazard Resolution Techniques

Pipelining is a fundamental technique for boosting processor performance, but its efficiency depends entirely on successfully navigating hazards—situations where the next instruction cannot execute in its designated clock cycle. Without effective hazard resolution, the pipeline would stall constantly, negating its performance benefits. Mastering the core techniques of data forwarding, pipeline stalls, and branch prediction is what transforms a theoretical pipeline into a high-performance, practical reality.

Understanding Pipeline Hazards and Their Consequences

A hazard is any condition that prevents the next instruction from executing in its planned cycle. They are categorized into three types, each requiring a specific resolution strategy. Data hazards occur when instructions need data that is not yet available because a prior instruction is still in the pipeline. The most common subtype is the Read-After-Write (RAW) hazard, where an instruction tries to read a register before a preceding instruction has written to it. Control hazards, also called branch hazards, arise from branches and jumps, where the instruction fetch stage cannot know which instruction to fetch next until the branch is resolved. Structural hazards occur when two instructions need the same hardware resource simultaneously, though these are largely designed out of modern pipelines through resource duplication.

The ultimate impact of unresolved hazards is wasted clock cycles, or stalls (also called pipeline bubbles). These stalls directly increase the average number of clock cycles per instruction (CPI), moving it away from the ideal pipeline CPI of 1. The goal of all hazard resolution techniques is to minimize this CPI penalty, maximizing instruction throughput.

Data Forwarding: The Primary Weapon Against Data Hazards

Data forwarding (often called bypassing) is the most critical technique for resolving RAW data hazards without stalling. The core idea is simple but powerful: instead of waiting for a result to be written back to the register file, the result is fed directly from the output of one pipeline stage to the input of another stage that needs it.

Consider two instructions in a classic 5-stage (IF, ID, EX, MEM, WB) pipeline:

ADD R1, R2, R3   # Writes result of R2+R3 to R1 in WB stage
SUB R4, R1, R5   # Needs the new value of R1 in its ID stage (for operand read)

Without forwarding, the SUB instruction must stall in the ID stage until the ADD completes its WB stage. With forwarding, the result from the ADD's EX stage output (available at the end of the EX cycle) is fed directly to the SUB's EX stage input at the beginning of the next cycle. This completely eliminates the stall.

Implementing forwarding requires additional forwarding paths (multiplexers and wiring) and a hazard detection unit. This unit monitors the source registers of instructions in the ID stage and compares them against the destination registers of instructions in later stages (EX, MEM). If a match is detected and the later instruction will actually write that register (i.e., it is not a no-op like a branch), the unit selects the forwarded data via control signals to the multiplexers instead of the data coming from the register file.

Pipeline Stalls: When Forwarding Is Not Enough

While forwarding solves most RAW hazards, it is insufficient in two key scenarios. First, a load-use hazard occurs when an instruction tries to use data loaded from memory by an immediately preceding LW (load word) instruction. The data from a load is only available at the end of the MEM stage, but the next instruction's EX stage needs it at the start of its cycle. Even with forwarding, this creates a one-cycle delay. The pipeline must insert a single stall cycle, often called a pipeline bubble, for the dependent instruction.

Second, forwarding cannot resolve hazards where an instruction depends on a result from two or more cycles earlier if the pipeline lacks sufficient forwarding paths. In such cases, a deliberate stall is necessary. Implementing a stall involves the hazard unit preventing the PC from updating and the IF/ID register from changing (so the current instruction is re-fetched), while injecting a no-op (an instruction that does nothing) into the pipeline by zeroing out the control lines for the ID stage. This bubble then propagates through the pipeline, allowing the needed data to become available.

Branch Prediction: Mitigating Control Hazards

Control hazards present a different challenge. In a simple pipeline, every branch instruction forces a stall until the branch target address and condition are computed in the ID or EX stage. This can waste multiple cycles per branch, devastating performance. Branch prediction aims to guess the outcome of a branch (taken or not taken) and its target address before it is resolved, allowing the fetch stage to continue speculatively.

The simplest form is static prediction, where the hardware always guesses the same way (e.g., "always not taken"). A more effective, common method is dynamic branch prediction, which uses runtime history. A Branch History Table (BHT) is a small memory that stores the recent behavior (taken/not taken) of branches based on their address. A 1-bit predictor remembers the last outcome; a 2-bit saturating counter predictor requires two wrong guesses to change its prediction, making it more stable for loop branches.

When a prediction is made, instructions from the predicted path are fetched and executed speculatively. If the prediction is correct, performance is gained. If it is wrong, a misprediction penalty is incurred: the speculatively executed instructions must be flushed from the pipeline (their effects nullified), and fetching must restart from the correct address. The goal is to maximize prediction accuracy to minimize this flush penalty. Advanced predictors like local and global history predictors correlate the branch's behavior with patterns in its own history or the history of other branches.

Common Pitfalls

Overlooking the Need for a Stall After a Load: A common error is assuming forwarding can solve all data dependencies. The load-use case is a critical exception that always requires at least a one-cycle stall, even in a perfectly forwarded pipeline. Failing to implement this stall results in incorrect program execution, as stale data will be used.

Incorrect Forwarding Mux Priority: When multiple later instructions in the pipeline are writing to the same register, the forwarding logic must have a defined priority. The most recent instruction (the one closest to the WB stage) must take priority, as its result is the correct architectural value. Improper priority leads to forwarding stale data from an older instruction.

Forgetting to Flush on Misprediction: When a branch prediction is found to be wrong, it is not enough to simply start fetching the correct instruction. The pipeline must flush all instructions that were fetched and speculatively executed down the wrong path. This means clearing or invalidating the partial results in the pipeline registers behind the branch. Neglecting this flush corrupts the architectural state.

Ignoring the Impact on CPI: When analyzing pipeline performance, it's easy to calculate cycles in isolation. The real measure is the aggregate impact on CPI. You must quantify the total stall cycles from load-use hazards and branch mispredictions. The final average CPI becomes $CPI=CP{I}_{ideal}+Stal{l}_{cycles}$. For a pipelined processor, $CP{I}_{ideal}$ is 1, so the equation is $CPI=1+Stal{l}_{cycles}$. Effective hazard resolution aims to minimize the stall term.

Summary

• Data forwarding bypasses results directly from the output of one pipeline stage to the input of another, eliminating most stalls caused by Read-After-Write (RAW) data hazards without needing to wait for register file write-back.
• Pipeline stalls (bubbles) are intentionally inserted when forwarding is insufficient, most critically for the mandatory one-cycle stall following a load instruction that is immediately used by the next instruction.
• Branch prediction reduces control hazard penalties by guessing the direction and target of a branch before it is resolved, allowing speculative execution; incorrect predictions incur a misprediction penalty requiring a pipeline flush.
• The combined effectiveness of these techniques is measured by their impact on the average clock cycles per instruction (CPI), with the goal of keeping the actual CPI as close to the ideal pipeline CPI of 1 as possible.
• Successful implementation requires a hazard detection unit to manage forwarding multiplexer control and stall insertion, as well as logic to handle speculative execution and flushing for branch prediction.