Spotting a hazard is only half the job. In Pipeline Hazards we learned to recognise structural, data and control hazards. This chapter is about what the hardware (and the compiler) actually does about them, so that the pipeline gives correct results while losing as few cycles as possible.
There are really only three tools, and every technique in this chapter is one of them or a mix:
- Wait: stall the pipeline until the hazard disappears. Always correct, always slow.
- Bypass: get the needed value from wherever it already exists inside the pipeline instead of waiting for it to reach the register file (forwarding).
- Guess: assume an outcome (for example, "this branch is not taken"), keep working, and throw the work away if the guess was wrong (branch prediction).
We will use the classic 5-stage pipeline throughout: IF (instruction fetch), ID (decode and register read), EX (ALU), MEM (data memory) and WB (register write-back). We also assume the usual register-file trick: the register file is written in the first half of a cycle and read in the second half, so an instruction in ID can read a value that another instruction is writing in WB in the same cycle.
Stalls (Pipeline Interlocks and Bubbles)
The simplest fix for any hazard is to make the later instruction wait. The hardware that detects the hazard and holds the instruction back is called an interlock, and the empty slot that travels down the pipeline in its place is called a bubble (effectively a NOP).
A stall is a cycle in which an instruction is held in its stage (and the instructions behind it are held too) while a bubble is sent into the next stage. Each stall cycle adds one cycle to the total execution time.
In hardware, a stall in ID is created by three actions in the same cycle:
- do not update the PC (so the same instruction is fetched again),
- do not update the IF/ID pipeline register (so the stalled instruction stays in ID),
- set all control signals in the ID/EX register to 0 (so a harmless bubble moves into EX).
Example 1: Stalling Only (No Forwarding)
Consider this code. The register written by each instruction is the first operand.
I1: lw r1, 0(r2)
I2: add r3, r1, r4 ; needs r1 from I1
I3: sub r5, r3, r6 ; needs r3 from I2
I4: and r7, r1, r5 ; needs r5 from I3
I5: or r8, r5, r7 ; needs r7 from I4Without forwarding, a consumer can only read a register in ID when the producer is in WB of the same cycle (or later). In the diagram, -- marks a stall cycle: the instruction has been fetched but has to wait before it can successfully read its operands.
Cycle 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
lw r1,0(r2) IF ID EX MEM WB
add r3,r1,r4 IF -- -- ID EX MEM WB
sub r5,r3,r6 IF -- -- ID EX MEM WB
and r7,r1,r5 IF -- -- ID EX MEM WB
or r8,r5,r7 IF -- -- ID EX MEM WBEach back-to-back dependence costs 2 stall cycles (the consumer's ID must line up with the producer's WB). Four such dependences give 8 stalls and 17 cycles, instead of the ideal 5 + 4 = 9 cycles. Notice that and r7,r1,r5 also needs r1, but by then r1 has long been written, so only the dependence on r5 matters.
Rule of thumb without forwarding (split-cycle register file): if the consumer is the very next instruction, 2 stalls; if one instruction lies in between, 1 stall; if two or more lie in between, no stall.
Operand Forwarding (Bypassing)
Look again at add r3,r1,r4 followed by sub r5,r3,r6. The value of r3 is computed by the ALU at the end of add's EX stage. The sub needs it at the start of its own EX stage, which is the very next cycle. The value exists; it is sitting in the EX/MEM pipeline register. Waiting two more cycles for it to travel through MEM and WB into the register file is pure waste.
Operand forwarding (bypassing) adds extra data paths and multiplexers so that a result can be sent directly from a pipeline register (EX/MEM or MEM/WB) to the ALU inputs of a later instruction, without waiting for it to be written into the register file.
+------------------------------------------+
| forward from MEM/WB (result 2 back) |
| +--------------------------------+ |
| | forward from EX/MEM (1 back) | |
v v | |
ID/EX ---> [ MUX ] ---> +-----+ | |
regs | ALU | ---> EX/MEM ------+---> MEM/WB ---+
ID/EX ---> [ MUX ] ---> +-----+ |
^ ^ |
| +------------ (same two sources) ----------------+
forwarding unit chooses: register file / EX/MEM / MEM/WBHow the Forwarding Unit Decides
The forwarding unit compares register numbers held in the pipeline registers. For the first ALU input (source register Rs1 of the instruction now in EX) the logic is:
EX hazard (producer is 1 instruction ahead):
if (EX/MEM.RegWrite and EX/MEM.Rd != 0 and EX/MEM.Rd == ID/EX.Rs1)
ForwardA = from EX/MEM
MEM hazard (producer is 2 instructions ahead):
else if (MEM/WB.RegWrite and MEM/WB.Rd != 0 and MEM/WB.Rd == ID/EX.Rs1)
ForwardA = from MEM/WB
else ForwardA = from register file
(The same logic, with Rs2, controls ForwardB.)Three details are worth understanding:
- RegWrite must be 1: a store or branch has a field in the Rd position but writes no register, so it must not trigger forwarding.
- Rd != 0: register 0 is hard-wired to zero in MIPS and RISC-V. An instruction that "writes" r0 must not forward a non-zero value.
- EX/MEM has priority: if both pipeline registers hold a write to the same register (for example
add r1,..,add r1,..,sub ..,r1,..), the more recent value, in EX/MEM, is the correct one.
Example 1 Again, With Forwarding
Cycle 1 2 3 4 5 6 7 8 9 10
lw r1,0(r2) IF ID EX MEM WB
add r3,r1,r4 IF -- ID EX MEM WB
sub r5,r3,r6 IF ID EX MEM WB
and r7,r1,r5 IF ID EX MEM WB
or r8,r5,r7 IF ID EX MEM WBFrom 17 cycles down to 10 cycles with just 1 stall. The three ALU-to-ALU dependences are fully covered by forwarding. One stall remains, and it cannot be removed by forwarding alone. That is the load-use hazard.
The Load-Use Hazard
A load gets its data from memory at the end of MEM. The instruction right after it wants the data at the start of its EX, which is the same cycle as the load's MEM. Forwarding cannot send a value backwards in time:
Cycle 1 2 3 4 5
lw r1,0(r2) IF ID EX MEM WB data ready at END of cycle 4
add r3,r1,r4 IF ID EX needs r1 at START of cycle 4 -> impossible
With one stall:
lw r1,0(r2) IF ID EX MEM WB
add r3,r1,r4 IF -- ID EX EX in cycle 5: r1 forwarded from MEM/WBLoad-use hazard: an instruction uses the destination register of a load that is immediately before it. In the classic 5-stage pipeline it costs exactly 1 stall cycle even with full forwarding. If one independent instruction separates the load and the use, no stall is needed.
The hazard detection unit checks this in ID:
if (ID/EX.MemRead and
(ID/EX.Rd == IF/ID.Rs1 or ID/EX.Rd == IF/ID.Rs2))
stall the pipeline for one cycleCompiler Fix: Instruction Scheduling
If the compiler can find an independent instruction to place between the load and its use, the stall disappears. This is called static instruction scheduling. Consider code for c = a + b; e = d + a; (all in memory at offsets of r10):
Original Reordered (lw r4 moved up)
lw r1, 0(r10) ; a lw r1, 0(r10)
lw r2, 4(r10) ; b lw r2, 4(r10)
add r3, r1, r2 lw r4, 12(r10)
sw r3, 8(r10) ; c add r3, r1, r2
lw r4, 12(r10) ; d sw r3, 8(r10)
add r5, r4, r1 add r5, r4, r1
sw r5, 16(r10) ; e sw r5, 16(r10)| Version | No forwarding | With forwarding |
|---|---|---|
| Original order | 19 cycles (8 stalls) | 13 cycles (2 stalls: two load-use pairs) |
| Reordered | 16 cycles (5 stalls) | 11 cycles (0 stalls) |
With forwarding plus scheduling we reach the ideal: 7 instructions in 5 + 6 = 11 cycles. The reordering is legal because lw r4 does not depend on, and is not depended on by, the two instructions it jumps over (it reads only r10 and writes r4, which neither of them touches).
Handling Structural Hazards
A structural hazard happens when two instructions need the same hardware in the same cycle. There are only two answers:
- Stall one of them. For example, if a single memory port serves both instruction fetch and data access, a load in MEM blocks the IF of a later instruction for that cycle.
- Duplicate the resource. This is why real pipelines have separate instruction and data caches (a Harvard-style split at the L1 level), a register file with two read ports and one write port, and separate adders for PC + 4 and branch targets.
Designers usually choose duplication for common cases and accept occasional stalls for rare ones (for example, a single non-pipelined divider).
Handling Control Hazards
A branch decides which instruction comes next, but the decision (condition and target) is known only some stages after the branch is fetched. Meanwhile the IF stage must fetch something every cycle. The number of cycles lost when the pipeline has fetched the wrong instructions is the branch penalty.
| Branch resolved at end of | Instructions fetched after branch before outcome is known | Penalty (cycles) |
|---|---|---|
| ID (stage 2) | 1 | 1 |
| EX (stage 3) | 2 | 2 |
| MEM (stage 4) | 3 | 3 |
In general, if the branch outcome and target are known at the end of stage k, the penalty is k - 1 cycles. That is why designs move the comparison and the target adder into ID: it cuts the penalty to 1 cycle (at the cost of new data hazards, because the comparator in ID needs its operands earlier).
1. Stall (Freeze) on Every Branch
Stop fetching until the branch is resolved. Simple, but every branch pays the full penalty whether taken or not.
2. Predict Not Taken
Keep fetching sequentially (PC + 4) as if the branch will not be taken. If it is not taken, nothing is lost. If it is taken, the wrongly fetched instructions are flushed (turned into bubbles) and fetch restarts at the target. This is safe because the wrong-path instructions have not yet reached MEM or WB, so they have not changed any state.
Branch resolved in EX, branch TAKEN, predict-not-taken:
Cycle 1 2 3 4 5 6 7 8
beq r1,r2,L IF ID EX MEM WB
next (i+1) IF ID xx flushed
next (i+2) IF xx flushed
L: target IF ID EX MEM WB
^ 2 cycles lost3. Predict Taken
Assume the branch is taken. This helps only if the target address is available early (for example from a branch target buffer, discussed below), because otherwise you cannot fetch from the target anyway.
4. Delayed Branch
Early RISC machines (MIPS, SPARC) changed the rules: the instruction(s) immediately after a branch, in the branch delay slot, are always executed, whether the branch is taken or not. The compiler's job is to fill the slot with useful work:
Before After filling the delay slot
add r4, r5, r6 beq r1, r2, L
beq r1, r2, L add r4, r5, r6 ; delay slot: always runs
nop ; wasted slot ...The add can be moved because the branch does not depend on r4. If no safe instruction can be found, the compiler must put a NOP in the slot. Delayed branches made sense for short 5-stage pipelines with a 1-cycle penalty, but they do not scale to deep or superscalar pipelines, so modern ISAs (including RISC-V) do not use them.
5. Dynamic Branch Prediction
Instead of a fixed guess, the hardware remembers what each branch did recently and predicts the same behaviour again. This is the subject of the next section.
Dynamic Branch Prediction
A branch history table (BHT), also called a branch prediction buffer, is a small memory indexed by the low-order bits of the branch's address. Each entry holds a few bits of history about branches that map to it.
1-Bit Predictor
Each entry stores the last outcome: predict whatever happened last time. Problem: a loop branch is mispredicted twice per loop execution. On the last iteration it is predicted taken but falls through (miss 1); this flips the bit to "not taken", so the next time the loop starts, the first iteration's branch is predicted not taken but is taken (miss 2).
2-Bit Saturating Counter
Each entry is a 2-bit counter with four states. A prediction is changed only after two consecutive mispredictions, so one odd outcome (like a loop exit) does not destroy a strong bias.
T T T T
+----+ ---> +----+ ---> +----+ ---> +----+ --+
| 00 | | 01 | | 10 | | 11 | | T (stays)
+----+ <--- +----+ <--- +----+ <--- +----+ <-+
^ | N N N
+--+ N (stays)
Strong NT Weak NT Weak T Strong T
predict NOT TAKEN predict TAKEN| Counter | Meaning | Prediction | On taken | On not taken |
|---|---|---|---|---|
| 00 | Strongly not taken | N | 01 | 00 |
| 01 | Weakly not taken | N | 10 | 00 |
| 10 | Weakly taken | T | 11 | 01 |
| 11 | Strongly taken | T | 11 | 10 |
Worked Example: 1-Bit vs 2-Bit
An inner loop runs 4 iterations, so its branch produces the pattern T T T N. The outer loop runs the inner loop 3 times, giving 12 outcomes: T T T N T T T N T T T N. Start the 1-bit predictor at N and the 2-bit counter at 00.
| # | Actual | 1-bit state / prediction | 1-bit result | 2-bit counter / prediction | 2-bit result |
|---|---|---|---|---|---|
| 1 | T | N | Miss | 00 / N | Miss |
| 2 | T | T | Hit | 01 / N | Miss |
| 3 | T | T | Hit | 10 / T | Hit |
| 4 | N | T | Miss | 11 / T | Miss |
| 5 | T | N | Miss | 10 / T | Hit |
| 6 | T | T | Hit | 11 / T | Hit |
| 7 | T | T | Hit | 11 / T | Hit |
| 8 | N | T | Miss | 11 / T | Miss |
| 9 | T | N | Miss | 10 / T | Hit |
| 10 | T | T | Hit | 11 / T | Hit |
| 11 | T | T | Hit | 11 / T | Hit |
| 12 | N | T | Miss | 11 / T | Miss |
1-bit: 6 mispredictions. 2-bit: 5 mispredictions, and of those, two are warm-up misses at the start. In the steady state the 1-bit predictor misses twice per inner-loop run (the exit and the re-entry), while the 2-bit predictor misses only once (the exit). For a 10-iteration loop run 5 times (50 branches), you can check that a 1-bit predictor gives 9 misses (starting at T) and a 2-bit predictor gives only 5 (starting at 11).
The 2-bit predictor is not magic. On a strictly alternating pattern T N T N ..., a 1-bit predictor is wrong every time (after at most one warm-up branch), and a 2-bit counter that starts at 01 is also wrong every time (it bounces 01 → 10 → 01 ...). Patterns like this need predictors that use the history of recent branches, described next.
Beyond 2-Bit Counters
- Correlating (two-level) predictors use the outcomes of the last few branches (a global history register) together with the branch address to choose a counter. They capture patterns such as "if the previous branch was taken, this one is not". The gshare scheme XORs the global history with the PC bits.
- Tournament predictors keep two predictors (for example a local and a global one) plus a chooser that learns which one is more accurate for each branch.
- Branch target buffer (BTB): a cache, looked up in IF using the PC, that stores the target address of recently taken branches. A BTB hit lets the processor fetch from the predicted target in the very next cycle, so a correctly predicted taken branch costs 0 cycles.
- Return address stack: a small stack that pushes the return address on each call and pops it on each return, because a return's target changes depending on the caller and a BTB predicts it poorly.
Measuring the Cost: CPI With Stalls
For a pipeline whose ideal CPI is 1:
CPI = 1 + (stall cycles per instruction)
= 1 + sum over each hazard type of (frequency x penalty)
Speedup over the unpipelined machine (balanced stages, no latch overhead)
= pipeline depth / CPISolved Problem 1: Comparing Branch Strategies
Question. In a 5-stage pipeline, 20% of instructions are conditional branches, and 60% of branches are taken. The branch is resolved at the end of MEM (penalty 3). Find the CPI for (a) stalling on every branch, (b) predict-not-taken, (c) a predictor that is correct 90% of the time with a BTB (a correct prediction costs nothing, a wrong one costs 3). Then repeat (a) and (b) with the branch resolved in ID.
Solution.
(a) stall always : CPI = 1 + 0.20 x 3 = 1.60
(b) predict NT : CPI = 1 + 0.20 x 0.60 x 3 = 1.36 (only taken branches pay)
(c) 90% predictor : CPI = 1 + 0.20 x 0.10 x 3 = 1.06
Resolved in ID (penalty 1):
(a) stall always : CPI = 1 + 0.20 x 1 = 1.20
(b) predict NT : CPI = 1 + 0.20 x 0.60 x 1 = 1.12
Speedup of the pipeline over a non-pipelined machine (5 stages, MEM resolution):
(a) 5 / 1.60 = 3.13 (b) 5 / 1.36 = 3.68 (c) 5 / 1.06 = 4.72The lesson: even a modest fraction of branches with a 3-cycle penalty throws away over a third of the pipeline's benefit. This is why branch handling gets so much attention, and why deeper pipelines (bigger penalties) need much better predictors.
Solved Problem 2: Loads and Branches Together
Question. A program has 25% loads, and 40% of loads are immediately followed by an instruction that uses the loaded value. Branches are 20% of instructions, 60% taken, predict-not-taken, resolved in EX (penalty 2). Full forwarding is present. Clock = 2 GHz. Find the CPI and the time to run 109 instructions.
Solution.
Load-use stalls = 0.25 x 0.40 x 1 = 0.10
Branch stalls = 0.20 x 0.60 x 2 = 0.24
CPI = 1 + 0.10 + 0.24 = 1.34
Cycles = 1.34 x 10^9
Time = 1.34 x 10^9 / (2 x 10^9) = 0.67 sSolved Problem 3: Counting Stalls
Question. How many cycles does this sequence take on the 5-stage pipeline (i) with no forwarding, (ii) with full forwarding?
lw r1,0(r2) / add r3,r1,r4 / sub r5,r3,r6 / and r7,r1,r5 / or r8,r5,r7Solution. This is Example 1. (i) Every instruction depends on the one right before it, so each of the 4 dependences costs 2 stalls: 9 + 8 = 17 cycles. (ii) Only the load-use pair (lw → add) stalls, for 1 cycle: 9 + 1 = 10 cycles.
Summary Table of Techniques
| Hazard | Technique | Who does it | Cost / remaining penalty |
|---|---|---|---|
| Structural | Stall, or duplicate the resource (split I/D cache, more ports) | Hardware | Area for duplication; stalls if not duplicated |
| Data (ALU → ALU) | Forwarding from EX/MEM and MEM/WB | Hardware | 0 stalls |
| Data (load → use) | Forwarding + 1 stall (interlock) | Hardware | 1 stall if adjacent |
| Data (load → use) | Instruction scheduling | Compiler | 0 if an independent instruction is found |
| Control | Stall until resolved | Hardware | Full penalty on every branch |
| Control | Predict not taken + flush | Hardware | Penalty only on taken branches |
| Control | Delayed branch | Compiler + ISA | 0 if slot filled, else a NOP |
| Control | Dynamic prediction + BTB | Hardware | Penalty only on mispredictions |
Common Mistakes
- Saying forwarding removes every data stall. The load-use case still needs 1 stall in the 5-stage pipeline, because the data does not exist until the end of MEM.
- Forgetting the split-cycle register file. Without forwarding, an adjacent dependence costs 2 stalls (not 3) when WB writes in the first half and ID reads in the second half. Read the question: if it says the register file cannot do this, the count changes.
- Charging the branch penalty to every branch under predict-not-taken. Only taken branches (the mispredicted ones) pay.
- Getting the penalty off by one. If the branch resolves at the end of stage k, the penalty is k - 1, not k.
- Forwarding from a store or to r0. The forwarding unit must check RegWrite and Rd != 0.
- Moving an instruction into a delay slot that changes a register the branch reads. That changes the branch outcome; such an instruction is not a legal filler.
- Assuming a 2-bit predictor always beats a 1-bit one. On some patterns (strict alternation) both can be wrong every time.
GATE and Interview Questions
Q1. Why can't forwarding eliminate the load-use stall in the 5-stage pipeline?
The loaded value is available only at the end of the load's MEM stage, but the next instruction needs it at the start of its EX stage, which is the same cycle. A value cannot be forwarded to a cycle before it exists, so one bubble is needed; after that, the value is forwarded from MEM/WB.
Q2. A 6-stage pipeline resolves branches at the end of stage 4. 25% of instructions are branches, 50% of them taken. Find the CPI with predict-not-taken and with stall-always.
Penalty = 4 - 1 = 3. Predict-not-taken: CPI = 1 + 0.25 x 0.5 x 3 = 1.375. Stall-always: CPI = 1 + 0.25 x 3 = 1.75.
Q3. Without forwarding, with a register file that writes in the first half and reads in the second half, how many stalls occur between I1: add r1,r2,r3 and I3: sub r4,r1,r5 if I2 is independent?
1 stall. The sub would normally be in ID two cycles after add's ID, i.e. in add's MEM cycle; it must wait one more cycle to line up with add's WB.
Q4. What does the forwarding unit check, and why does EX/MEM get priority over MEM/WB?
It checks that the earlier instruction writes a register (RegWrite = 1), that its Rd is not register 0, and that Rd matches a source register of the instruction in EX. If both EX/MEM and MEM/WB match, the EX/MEM value is newer (it came from the more recent instruction), so it must be used.
Q5. Why is a loop branch mispredicted twice per loop execution by a 1-bit predictor but only once by a 2-bit predictor?
The 1-bit predictor flips to "not taken" at the loop exit, so it also mispredicts the first branch of the next loop execution. The 2-bit counter only drops from strongly taken to weakly taken on the exit, still predicting taken, so the re-entry is predicted correctly.
Q6. What is the purpose of a branch target buffer if we already have a branch history table?
The BHT only predicts the direction (taken or not). To fetch from the target in the next cycle, the processor also needs the target address while the branch is still in IF, before it has been decoded. The BTB provides that address, making correctly predicted taken branches free.
Q7. How is a stall actually implemented in hardware?
The hazard detection unit prevents the PC and the IF/ID register from being written (so the same instructions stay in IF and ID) and forces the control signals going into ID/EX to zero, so a bubble (NOP) moves into EX.
Summary
- Hazards are handled by waiting (stalls), bypassing (forwarding) or guessing (prediction), with help from the compiler (scheduling, delay slots).
- A stall freezes PC and IF/ID and inserts a bubble into ID/EX. Without forwarding, an adjacent dependence costs 2 stalls with a split-cycle register file.
- Forwarding from EX/MEM and MEM/WB removes all ALU-to-ALU stalls. The load-use hazard still costs 1 stall, which compiler scheduling can hide.
- Structural hazards are solved by stalling or by duplicating resources (split I/D caches, extra ports).
- Branch penalty = (stage where branch resolves) - 1. Options: stall, predict not taken, predict taken, delayed branch, and dynamic prediction with 1-bit or 2-bit counters, correlating predictors and a BTB.
- CPI = 1 + sum of (frequency x penalty) over all hazards; speedup = depth / CPI. In our example, branch handling alone moved the speedup from 3.13 to 4.72.
- Even with all these tricks, a simple pipeline completes at most one instruction per cycle. To go beyond that, the processor must start several instructions at once, which is the topic of Instruction-Level Parallelism & Superscalar Processors.