Pipeline Hazards and Data Dependencies

A hazard is a major barrier in pipelining that, if left unaddressed, will result in the incorrect execution of a program. Hazards invariably involve conflicts — whether they are resource conflicts, data conflicts, or transfer-of-control conflicts.

Pipeline Hazards and Data Dependencies

To address these hazards and prevent a calamity in execution, pipelines rely on a mechanism called a stall. A stall consists of “recycling” a pipeline stage; rather than advancing an instruction to the next phase, the stage reperforms its operation in the next clock cycle. Because an instruction in a stalled stage cannot advance, all the instructions in the pipeline stages behind it must also stall. This cascading delay creates what is known as a pipeline bubble. Even though the stalled stages cannot make meaningful progress, the hardware circuits are automatons that must do something every time the clock pulses. Therefore, when the pipeline stalls, the hardware handles this by inserting a NOOP (no-operation) instruction — an instruction of all zeros that performs no work and changes no registers — allowing the stages to safely cycle without corrupting data.

There are three major types of pipelining hazards:

1. Structural Hazards
2. Data Hazards
3. Control Hazard

1. Structural Hazards

A structural hazard occurs when there is a resource conflict in the hardware. The hardware simply cannot support all possible combinations of instructions executing simultaneously.

• Cache/Memory Example: In a non-Harvard architecture (where instructions and data share a single unified cache), a structural hazard occurs if an instruction in the Instruction Fetch (IF) stage attempts to read the cache at the same time an earlier instruction in the Memory (MEM) stage attempts to read or write data to that same cache.
• Register File Example: Consider an architecture where the Program Counter (PC) is mapped to a general-purpose register (such as R15 in ARM). If a branch instruction in the MEM stage attempts to update the PC while an ALU instruction in the Write-Back (WB) stage attempts to update another register (like R1), both instructions will attempt to write to the register file at the same time. If the register file only has a single write port, they will collide, creating a structural hazard.

2. Data Hazards and Data Dependencies

A data hazard is a data access-related conflict that will produce an incorrect value if unresolved. The absolute precondition for a data hazard is a data dependency. A data dependency occurs when two or more instructions need to act on a common operand. Dependencies are an unavoidable feature of programming, and there are several types:

1. True Data Dependency: This occurs when an instruction consumes a data item that was produced by a prior instruction. For example, if instruction 1 is a1 = a0 + 1 and instruction 2 is a2 = a1 + 1, the second instruction has a true data dependency on the first because it needs the value of a1.
2. False / Name Dependencies: These occur when two instructions use the same register name, but no actual data flows between them. Because we only have a limited number of registers (e.g., 32 in RISC-V), programmers and compilers are forced to reuse them, creating these pseudo-dependencies. They can theoretically be fixed by “register renaming” (picking a different register). There are two types of False Data Dependencies:

• Output Dependency: An instruction produces a data item that was also produced by a prior instruction. Example: addw x2, x3, x4 followed by subw x2, x5, x6. Both instructions write their result to x2, but no data flows between them.
• Anti-Dependency: An instruction produces a data item that was consumed by a prior instruction. Example: mulw x1, x2, x3 followed by subw x2, x4, x5. The subtraction writes to x2 only after the multiplication reads from x2.

Transitive (Indirect) Dependencies: These are first-order dependencies that form an indirect chain across multiple instructions (e.g., Instruction C depends on B, and B depends on A, meaning C has a transitive dependency on A).

Specific Types of Data Hazards (RAW, WAW, WAR)

Whether a data dependency actually transforms into a pipeline data hazard depends entirely on the hardware’s execution order. There are three types of data hazards:

1. RAW (Read After Write): Based on a True Data Dependency. The programmer intended for a read to take place after a write. A RAW hazard occurs if the pipeline overlaps execution such that the read accidentally happens before the write is finished. In our standard RISC-V pipeline, this is the most common hazard and the primary reason we must stall.
2. WAW (Write After Write): Based on an Output Dependency. The programmer intended for one write to happen after another write. A WAW hazard occurs if the pipeline jumbles the order and the second write happens before the first, leaving the wrong final value in the register. Simple pipelines do not suffer from WAW hazards, but advanced pipelines (like varying latency or dynamically scheduled pipelines) do.
3. WAR (Write After Read): Based on an Anti-Dependency. The programmer intended for a write to happen after a read. A WAR hazard occurs if the pipeline executes out of order and allows the write to happen before the read takes place, causing the reader to ingest the new (wrong) value. Our standard pipeline naturally avoids WAR hazards because reads always happen early (in ID) and writes always happen late (in WB).

3. Control Hazards

A control hazard involves a transfer-of-control conflict that disrupts the normal sequential flow of the program. The precondition is a control dependency, which dictates that any instruction immediately following a branch (the fall-through) or any instruction that is the target of a branch is control-dependent on that branch. Because the pipeline evaluates the branch condition and updates the Program Counter later in the pipeline (often in the EX or MEM stage), the pipeline will have already fetched the wrong instructions, necessitating a stall or a flush (converting the incorrectly fetched instructions into NOOPs)

Resolving Data Hazards

When the pipeline’s Instruction Decode (ID) stage detects a data dependency, it must intervene. The professor details three major techniques to resolve these hazards:

1. Stalling (The Bulletproof Method)

The most reliable, foolproof method to resolve a hazard is to simply stall the pipeline. The ID stage does the heavy lifting: it decodes the operands, checks all currently executing instructions for dependencies, and if it detects that an instruction will not produce its result in time, it forces the current instruction to recycle in the ID stage.

Standard RISC-V (No forwarding)

2. Forwarding Through the Register File

This is a less draconian workaround than a full stall. In the standard pipeline, an instruction writing to the register file (in the WB stage) and an instruction reading from it (in the ID stage) might collide. To resolve this without a stall, the pipeline modifies the hardware timing: the WB stage is programmed to write to the register file on the rising edge (the first half) of the clock pulse, and the ID stage reads on the falling edge (the second half). This allows the ID stage to cleanly ingest the freshly written data in the same clock cycle. To fully grasp the performance benefit of this technique, one must perform CPI and speedup computations: by calculating the Base CPI (without pipelining), the CPI of the standard stalling pipeline, and the new CPI using register forwarding, you can quantitatively measure the exact speedup gained by saving these stall cycles.

Forwarding through the register file.

3. Full Forwarding / Bypassing (Short-Circuiting)

To eliminate even more stalls, pipelines use full forwarding (or bypassing). Instead of waiting for the WB stage to write to the register file, the Execute (EX) stage bypasses the register file entirely and grabs its required operand directly from the pipeline latches (the temporary buffers sitting between pipeline stages, such as the EX/MEM latch). To implement this, the hardware requires two major additions: new multiplexers placed at the ALU inputs to select between the standard register file and the pipeline latches, and new control logic in the ID stage to detect the hazard and trigger the multiplexer routing.

Full Forwarding / Bypassing (Short-Circuiting)

How data hazard handling shapes pipeline performance

The same four instructions. Three different hardware decisions. A measurable difference in every clock cycle that follows.

The three pipeline diagrams above each execute the same instruction sequence, addw, subw, or, and , but handle RAW (read-after-write) data hazards differently. The cost shows up directly in clock cycle count, CPI, and ultimately, how fast your processor finishes real work.

In Standard RISC-V (no forwarding), all 4 instructions complete at clock cycle 12, as 4 stall bubbles are inserted to resolve RAW hazards.

With Forwarding Through the Register File, the dual-edge register file eliminates 2 stalls, and all 4 instructions complete at clock cycle 10.

With Full Forwarding/Bypassing, the forwarding unit eliminates all stalls, and all 4 instructions complete at clock cycle 8 — the fastest of the three techniques.

Performance comparison of three data hazard handling techniques on the same 4-instruction sequence. CPI is calculated as total clock cycles divided by completed instruction count. Speedup is measured against a non-pipelined baseline of 20 clock cycles (4 instructions × 5 pipeline stages). Each stall bubble adds 0.25 to the CPI — full forwarding eliminates all stalls, cutting CPI in half compared to no forwarding.

Each stall cycle costs exactly 0.25 CPI. With 4 instructions in flight, every bubble inserted into the pipeline adds one full clock cycle to completion time — raising CPI by 1/4. No forwarding accumulates 4 stalls; register-file forwarding resolves the WB→ID hazard using dual-edge clocking, cutting that to 2; full bypassing feeds results directly from EX/MEM pipeline registers back to the EX stage input, reaching zero stalls.

Full forwarding delivers 50% more speedup than no forwarding (2.50× vs 1.67×) against a non-pipelined baseline. Even the cheaper register-file forwarding technique achieves a clean 2.00× — double the throughput — at the cost of only a dual-edge register file design, making it a compelling middle ground when full bypassing hardware is too expensive.

The penalty scales with program size. In real workloads with thousands of dependent instructions, the gap between these three approaches widens dramatically. Full forwarding is the reason modern out-of-order processors can sustain near-CPI-1 performance on code with heavy data dependencies.

Cache and Memory Effects on Bypassing

It is critical to note that forwarding and bypassing do not eliminate all stalls. If a dependency relies on a load instruction, and that load experiences a cache miss, the data must be fetched from main memory or even the hard drive. Because memory accesses can take hundreds or even millions of clock cycles (in the event of a page fault), the pipeline must still fall back on stalling to handle these massive memory latencies.

Resolving Control Hazards

Addressing control hazards requires us to resolve conflicts caused by transfer-of-control instructions (branches and jumps) that disrupt the normal sequential flow of a program. Because these instructions alter the Program Counter (PC), the pipeline risks fetching and executing the wrong instructions. Here is a detailed breakdown of the solutions used to mitigate these hazards.

1. Stalls, NOPs, and Flushing

In the standard RISC-V pipeline, the execution of a branch instruction is split across stages: the branch condition is checked in the EX (Execute) stage, but the Program Counter (PC) is not actually updated until the MEM (Memory) stage.

Because the PC isn’t updated immediately, the pipeline will mistakenly continue to fetch the subsequent sequential instructions. To prevent these incorrect instructions from corrupting the register file or memory, the foolproof solution is to stall the pipeline.

The pipeline achieves this stall by flushing the incorrectly fetched instructions. Flushing simply means converting an on-the-fly instruction into a NOP (No-Operation). A NOP is an instruction that does absolutely no work and changes no registers or memory locations. In RISC-V, there isn’t a dedicated NOP opcode; instead, the hardware creates a proxy for a NOP by issuing an ALU command that targets the hardwired zero register, such as add x0, x0, x0.

Control hazard caused by a bnez x1, 400 instruction (fall-through case). The processor cannot confirm the branch outcome until EX (CC3), and the PC is not updated until MEM (CC4) — forcing NOP bubbles into the two slots that were speculatively fetched. Only at CC5 (WB) can a valid instruction fetch resume. This results in a 2-cycle penalty for every unresolved branch.

Consider the instruction bnez x1, 400. When this enters the pipeline, the processor has no choice but to keep fetching the next sequential instructions — addw x2,x3,x4 and addw x10,x11,x12 — even though it does not yet know whether the branch will be taken or not.

By CC3 (EX stage), the processor finally evaluates the branch condition. In the fall-through case, the condition is not satisfied — meaning we do not jump to address 400, and the sequentially fetched instructions are actually the correct ones to execute. However, the processor still cannot be sure of this until CC4 (MEM stage), where the program counter is updated. Only at CC5 (WB stage) can a valid instruction fetch begin for the downstream instructions.

This uncertainty forces the pipeline to insert NOP (No Operation) bubbles into the stages that were speculatively filled. As seen in the diagram, the instructions fetched at CC2 and CC3 enter the pipeline as IF/NOP, stall through NOP cycles, and only resume meaningful progress once the branch outcome is confirmed. The pink arrow in the diagram marks this as a flush — the speculative instructions are squashed and replaced with NOPs to prevent incorrect state changes.

The key takeaway: every conditional branch that cannot be resolved early costs the pipeline penalty cycles equal to the number of stages before the branch outcome is known. In this standard 5-stage pipeline, there is a 2-cycle penalty per branch, regardless of whether the branch is taken or falls through.

2. The Delayed Branch

A less draconian workaround to avoid wasting clock cycles on NOPs is the delayed branch. This strategy changes the fundamental rules of programming: it dictates that the instruction immediately following a branch instruction always executes, regardless of whether the branch is taken or not.

The space immediately following the branch instruction is known as the branch delay slot, and the instruction placed there is the branch delay instruction. Because this instruction executes for free while the branch is resolving, the compiler or assembly programmer must find a valid, useful instruction to fill this slot. There are four ways to fill the branch delay slot:

1. A fall-through instruction: Taking an instruction from the path where the branch is not satisfied. This instruction must be safe to execute even if the branch actually is taken.
2. The target instruction: Taking an instruction from the branch’s target address. This must be safe to execute even if the branch ends up falling through.
3. A prior instruction: Hoisting an instruction from before the branch. This is only valid if moving it doesn’t alter the branch condition or introduce RAW/WAW/WAR data hazards.
4. A NOP: If the compiler cannot find a safe instruction using the first three methods, it is forced to insert a NOP, forfeiting the performance benefit.

Variant: The Cancelling Branch

If we fill the branch delay slot with an instruction that turns out to be unsafe for the actual path taken, we can use a variant called the cancelling branch. This mechanism adds hardware logic allowing the CPU to convert an executing instruction into a NOP dynamically on the fly. The cancellation takes place later in the pipeline, specifically in the EX stage, because that is when the CPU officially evaluates the branch condition and determines the definitive direction the code will flow.

The Cancelling Branch

3. Predictive Branching (Predict Taken vs. Predict Not Taken)

Predictive branching relies on special branch instructions that provide a “hint” to the CPU about what the programmer expects to happen.

• Predict Taken: The CPU hints that the branch will likely jump to its target. However, in the standard RISC-V pipeline, predict taken is completely unbeneficial. Even if the CPU assumes the branch will jump, it cannot fetch the target instruction early because the target address is encoded as an offset and is not actually calculated until the EX stage. Because the target is unknown during the IF (Instruction Fetch) stage, the pipeline gains no performance benefit and must still stall.
• Predict Not Taken: The CPU hints that the branch condition will be false, meaning the program will just fall through to the next sequential instruction. This is highly beneficial for RISC-V because the fall-through instruction is naturally the one being fetched next. If the prediction is correct, the instruction flows smoothly through the pipe with a 0-cycle penalty, achieving optimal performance. If the prediction is wrong, the CPU simply uses the cancelling branch feature to convert the mistakenly fetched instructions into NOPs.

Code Studies on Branches

To understand how effective these predictions are, computer architects rely on code studies:

• Roughly 12% to 20% (about 1 out of every 5 to 8 instructions) of all executed code consists of transfer-of-control instructions.
• Surprisingly, about 75% of conditional branches are forward branches (e.g., jumping over an if block or a divide-by-zero guard), and their targets can often be expressed in 4 bits or less.
• However, overall, 66% of all branches are taken. For backward branches (which are almost exclusively loops), an overwhelming 85% are taken.

This presents a major dilemma: the only prediction scheme that benefits our RISC-V pipe is Predict Not Taken, but statistics prove that branches are actually taken 66% of the time, meaning our prediction would fail the vast majority of the time.

Static vs. Dynamic Prediction

All of the methods discussed above — Delayed Branching, Cancelling Branches, and Predictive Branching — fall under the category of static branch prediction. Static prediction means that the prediction strategy is fixed and determined entirely ahead of time (before runtime) by the programmer or the compiler, rather than responding to the immediate state of the machine.

Because static prediction is severely limited by general code statistics, modern CPUs rely on dynamic branch prediction, where the CPU makes predictions on the fly based on the current runtime behavior of the program. We will talk about dynamic prediction mechanisms in a later post.

🔙 Back to all notes 𝕏 Let’s Connect

Backlinks: *Computer Architecture Notes: A Quantitative Guide to Modern Computing*