In Pipelining Basics we assumed a perfect world: a new instruction enters the pipeline every cycle and finishes one cycle after the previous one, giving CPI = 1. Real programs are not so polite. An instruction may need a value the previous instruction has not written yet; two instructions may want the same piece of hardware in the same cycle; a branch may change which instruction should come next before the pipeline knows it.
These situations are called hazards. When a hazard occurs, the pipeline must hold some instructions back for a cycle or more, which inserts stalls (bubbles) and raises the CPI above 1. In this chapter we classify hazards (structural, data and control), learn to spot RAW, WAR and WAW dependences, draw timing diagrams with stalls, and calculate the cost of hazards in cycles, CPI and speedup. The techniques for reducing that cost (forwarding, branch prediction and others) are the subject of the next chapter, Handling Hazards: Stalls, Forwarding & Branch Prediction.
What Is a Hazard?
Pipeline hazard: a situation that prevents the next instruction in the instruction stream from executing in its designated clock cycle. Hazards reduce the performance of a pipeline below the ideal speedup.
There are three classes:
Hazard | Cause | Everyday analogy |
|---|---|---|
Structural | Two instructions need the same hardware resource in the same cycle | A combined washer-dryer: you cannot wash load 2 while drying load 1 |
Data | An instruction needs a result that an earlier instruction still in the pipeline has not produced yet | You cannot fold a load that has not finished drying |
Control (branch) | The pipeline does not yet know which instruction to fetch next, because a branch has not been resolved | You do not know which basket to start on until someone tells you which load is urgent |
Throughout this chapter we use the classic 5-stage pipeline IF, ID, EX, MEM, WB with these standard assumptions (state them in exam answers too):
Source registers are read in ID; results are written in WB.
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 being written in WB in the same cycle.
No forwarding (operand bypassing) unless stated; that comes in the next chapter.
In timing diagrams, st marks a stall cycle (a bubble): the instruction is held and does no useful work in that cycle.
Structural Hazards
A structural hazard happens when the hardware cannot support all combinations of instructions in the same cycle.
Example: a single memory port. Suppose instructions and data share one memory with one port. A load accesses data memory in its MEM stage (cycle 4 for the first instruction), which is exactly when the fourth instruction wants to be fetched:
Cycle: 1 2 3 4 5 6 7 8 9
lw r1, 0(r2) IF ID EX MEM WB
add r3, r4, r5 IF ID EX MEM WB
sub r6, r7, r8 IF ID EX MEM WB
or r9, r10, r11 st IF ID EX MEM WB
^
cycle 4: memory busy with lw's data access, fetch must wait
Total: 9 cycles instead of the ideal 4 + 4 = 8. One stall.
Other common structural hazards: a single register-file write port shared by instructions that finish in different stages, or a non-pipelined functional unit (for example a divider that takes 20 cycles) needed by two instructions in a row.
Why are structural hazards usually designed away? Because the fix is just more hardware: separate instruction and data caches (a Harvard-style split at the L1 level, as in Von Neumann vs Harvard Architecture), more register-file ports, or fully pipelined functional units. Designers accept a structural hazard only when the extra hardware would be too costly for how rarely the conflict occurs.
Data Dependences: RAW, WAR and WAW
Before talking about data hazards, we classify the dependences between instructions. Consider instruction i that comes before instruction j in the program:
Name | Also called | Condition | Danger if order is not respected |
|---|---|---|---|
RAW (Read After Write) | True dependence, flow dependence | j reads a register that i writes | j reads the old value before i writes the new one |
WAR (Write After Read) | Anti-dependence | j writes a register that i reads | j overwrites it before i has read it, so i reads a value from the future |
WAW (Write After Write) | Output dependence | i and j write the same register | Writes complete in the wrong order, leaving i's (older) value in the register |
(RAR, read after read, is not a hazard: reading twice changes nothing.)
Why the difference matters: RAW is a true dependence: data really flows from i to j, and j cannot run until the value exists. WAR and WAW are name dependences: they exist only because two instructions happen to reuse the same register name. If the second instruction used a different register, the dependence would vanish. That is exactly what register renaming does in out-of-order processors (see Instruction-Level Parallelism & Superscalar Processors).
Worked Example 1: Find All Dependences
I1: R1 = R2 + R3
I2: R4 = R1 * R5
I3: R2 = R6 - R7
I4: R4 = R8 + R9
I5: R10 = R4 + R2
Check every pair (earlier, later) for each register:
Pair | Register | Type | Reason |
|---|---|---|---|
I1 → I2 | R1 | RAW | I1 writes R1, I2 reads it |
I1 → I3 | R2 | WAR | I1 reads R2, I3 later writes it |
I2 → I4 | R4 | WAW | Both write R4 |
I3 → I5 | R2 | RAW | I3 writes R2, I5 reads it |
I4 → I5 | R4 | RAW | I5 reads the R4 written by I4 (the latest writer) |
Note that I2 → I5 is not a RAW dependence on R4: I4 writes R4 in between, so I5 gets I4's value, not I2's. A careful answer always uses the most recent earlier writer. (We found exactly these five dependences by checking all pairs with a short script.)
Which Dependences Cause Hazards in the 5-Stage Pipeline?
RAW: yes. The consumer reads registers in ID (stage 2), but the producer writes in WB (stage 5), three stages later.
WAR: no. All instructions read in stage 2 and write in stage 5, in program order, so an earlier instruction always reads before a later one writes.
WAW: no. All writes happen in the same stage (WB) in program order.
WAR and WAW hazards appear in pipelines where instructions can complete out of order: for example when a long floating-point multiply (many EX cycles) is followed by a short integer add writing the same register, or in out-of-order processors. In GATE questions, read carefully whether the pipeline is the simple in-order kind.
Data Hazards (RAW) and Their Cost
Consider this sequence:
add r1, r2, r3 # writes r1 in WB
sub r4, r1, r5 # needs r1
and r6, r1, r7 # needs r1
or r8, r2, r9
xor r10, r1, r11 # needs r1
If nothing is done, sub would read r1 in cycle 3, but add writes it only in cycle 5: sub would compute with the stale value. The simplest correct solution is to stall sub until it can read the new value. With the write-first-half, read-second-half register file, it may read r1 in cycle 5:
Cycle: 1 2 3 4 5 6 7 8 9 10 11
add r1,r2,r3 IF ID EX MEM WB
sub r4,r1,r5 IF st st ID EX MEM WB
and r6,r1,r7 IF ID EX MEM WB
or r8,r2,r9 IF ID EX MEM WB
xor r10,r1,r11 IF ID EX MEM WB
Total 11 cycles instead of the ideal 5 + 4 = 9: 2 stall cycles. The later readers of r1 (and, xor) need no extra stalls, because by the time they reach ID, r1 has already been written. (We show the bubbles just before ID so that ID is drawn in the cycle where the correct value is actually read. Some books draw IF ID st st EX instead; the cycle count is the same.)
How Many Stalls? The Distance Rule
If the consumer is d instructions after the producer (d = 1 means the very next instruction), and there are no other stalls in between:
Distance d | Stalls (split-cycle register file) | Stalls (no split: read must be one cycle after write) |
|---|---|---|
1 (adjacent) | 2 | 3 |
2 | 1 | 2 |
3 | 0 | 1 |
4 or more | 0 | 0 |
Why: the producer issued in cycle c writes in WB at cycle c + 4. The consumer at distance d would normally be in ID at cycle c + d + 1. It needs ID ≥ c + 4 (split-cycle), so it stalls max(0, 3 - d) cycles. Without the split-cycle trick it needs ID ≥ c + 5, so max(0, 4 - d). We verified every entry of this table with a cycle-by-cycle simulator.
Worked Example 2: Count the Cycles
Problem. How many cycles does this code take on the 5-stage pipeline without forwarding (split-cycle register file)?
I1: lw r1, 0(r2)
I2: add r3, r1, r4 # RAW on r1 from I1 (distance 1)
I3: sub r5, r3, r1 # RAW on r3 from I2 (distance 1); r1 from I1 (distance 2)
I4: sw r5, 4(r2) # RAW on r5 from I3 (distance 1)
Solution. Each instruction depends on the one just before it, so each needs 2 stalls. Note that I3's dependence on r1 (from I1) is already satisfied by the stalls caused for I2, so it adds nothing extra.
Cycle: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lw r1,0(r2) IF ID EX MEM WB
add r3,r1,r4 IF st st ID EX MEM WB
sub r5,r3,r1 IF st st ID EX MEM WB
sw r5,4(r2) IF st st ID EX MEM WB
Total = 14 cycles = ideal 4 + 4 = 8, plus 6 stalls. Effective CPI for these 4 instructions in the steady state is (4 + 6)/4 = 2.5 instead of 1. The next chapter shows how forwarding brings this down dramatically.
Control Hazards
A branch decides the next PC, but that decision is made only when the branch reaches some stage (it must read registers, compare them and compute the target). Meanwhile the IF stage must fetch something every cycle.
If the pipeline simply stalls (or fetches and then discards) until the outcome is known, the cost per branch is:
Branch penalty = (number of the stage where the branch is resolved) - 1 cycles
resolved in ID (stage 2) -> 1 cycle
resolved in EX (stage 3) -> 2 cycles
resolved in MEM (stage 4) -> 3 cycles
Branch resolved at the end of EX:
Cycle: 1 2 3 4 5 6 7
beq r1,r2,L IF ID EX MEM WB
next (or target) st st IF ID EX MEM ...
^ correct PC known now
Because about 15 to 25% of instructions in typical programs are branches or jumps, control hazards are often the biggest pipeline loss, and deeper pipelines (later resolution) make it worse. That is why so much effort goes into branch prediction (next chapter).
Worked Example 3: Branch in a Pipeline (GATE 2013)
Problem. An instruction pipeline has five stages: FI (fetch), DI (decode), FO (fetch operand), EI (execute) and WO (write operand), with stage delays 5, 7, 10, 8 and 6 ns. There are intermediate buffers after each stage, each with a delay of 1 ns. A program of 12 instructions I1 to I12 is executed. I4 is the only branch instruction and its target is I9. If the branch is taken during the execution of this program, what is the time needed to complete the program?
The pipeline has no branch prediction. The standard assumption (used in the accepted answer, 165 ns) is that the target address is known only when the branch completes its EI stage, so the fetch of I9 waits until then.
Solution.
Clock period = max(5, 7, 10, 8, 6) + 1 = 11 ns
Executed instructions: I1, I2, I3, I4, then I9, I10, I11, I12
(I5 to I8 are skipped because the branch is taken)
Cycle: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I1 FI DI FO EI WO
I2 FI DI FO EI WO
I3 FI DI FO EI WO
I4 FI DI FO EI WO
I9 FI DI FO EI WO
I10 FI DI FO EI WO
I11 FI DI FO EI WO
I12 FI DI FO EI WO
I4 is in EI in cycle 7, so I9 can be fetched only in cycle 8.
Cycles 5, 6 and 7 are lost (any instructions fetched there are discarded).
I12 is fetched in cycle 11 and finishes WO in cycle 15.
Total time = 15 x 11 ns = 165 ns
Check with the formula: ideal cycles for 8 executed instructions = 5 + 8 - 1 = 12; plus a branch penalty of 4 - 1 = 3 (resolved in stage 4) gives 15 cycles.
Measuring the Cost of Hazards
With stalls, CPI is no longer 1:
CPI (pipelined) = ideal CPI + average stall cycles per instruction
= 1 + stalls per instruction
Speedup over non-pipelined = pipeline depth / (1 + stalls per instruction)
(assuming balanced stages, equal clock, and non-pipelined CPI = depth)
Stalls from branches per instruction = branch frequency x branch penalty
Worked Example 4: CPI With Hazards
Problem. On a 5-stage pipeline, 20% of instructions are branches with a 2-cycle penalty, and data hazards cause on average 0.5 stall cycles per instruction. Structural hazards are absent. Find the CPI and the speedup over an equivalent non-pipelined processor (CPI 5, same clock).
Branch stalls per instruction = 0.20 x 2 = 0.4
Data stalls per instruction = 0.5
CPI = 1 + 0.4 + 0.5 = 1.9
Speedup = 5 / 1.9 = 2.63 (instead of the ideal 5)
Hazards cost almost half the benefit of pipelining here. This is the motivation for every technique in the next chapter.
Summary Table of Hazards
Hazard | Cause | Example | Simplest remedy (cost) | Better remedies (next chapter) |
|---|---|---|---|---|
Structural | Resource conflict | Single memory port for IF and MEM | Stall the later instruction | Duplicate or pipeline the resource (split I/D caches) |
Data (RAW) | Value not yet written |
| Stall until WB (up to 2 cycles here) | Forwarding, instruction scheduling by the compiler |
Data (WAR, WAW) | Register name reuse with out-of-order completion | Long FP op and short integer op writing the same register | Stall | Register renaming |
Control | Next PC unknown | Conditional branch | Stall until resolved (penalty = resolve stage - 1) | Earlier resolution, prediction, delayed branch |
Common Mistakes
Counting a RAW dependence on an older writer when a newer instruction has written the same register in between.
Calling WAR or WAW "true" dependences. Only RAW is a true (data-flow) dependence; WAR and WAW are name dependences.
Claiming WAR/WAW hazards occur in the simple in-order 5-stage pipeline. They do not; all reads happen in ID and all writes in WB, in program order.
Ignoring the register-file assumption. Split-cycle read/write gives 2 stalls for adjacent RAW; without it, 3. State which you use.
Adding stalls twice. When an instruction depends on two earlier ones, the stalls for one may already cover the other (I3 in Worked Example 2).
Forgetting the branch's own fill cycles or charging the penalty for non-taken branches when the question says the pipeline fetches sequentially and only taken branches cost cycles.
GATE and Interview Questions
Name the three types of pipeline hazards and give one example each.
Structural: a load's MEM and a later instruction's IF both need a single-ported memory. Data: add r1,r2,r3 followed by sub r4,r1,r5 (RAW on r1). Control: a conditional branch whose outcome is not known when the next instruction must be fetched.
Identify the dependences: I1: R3 = R1 + R2; I2: R1 = R3 * R4; I3: R3 = R5 - R6.
I1 → I2 RAW on R3; I1 → I2 WAR on R1 (I1 reads R1, I2 writes it); I1 → I3 WAW on R3; I2 → I3 WAR on R3 (I2 reads R3, I3 writes it).
In the 5-stage pipeline without forwarding (split-cycle register file), how many stalls does add r1,r2,r3; nop; sub r4,r1,r5 need?
The distance is 2, so 1 stall.
A pipeline resolves branches in the 3rd stage and stalls on every branch. 25% of instructions are branches and there are no other stalls. What is the CPI?
Penalty = 3 - 1 = 2 cycles. CPI = 1 + 0.25 x 2 = 1.5.
A 6-stage pipeline has 0.4 stall cycles per instruction on average. What is the speedup over a non-pipelined machine with the same clock and CPI 6?
6 / (1 + 0.4) = 4.29.
Why are WAR and WAW called false dependences?
No data flows between the two instructions; they only conflict because they use the same register name. Giving the later instruction a different physical register (register renaming) removes the conflict completely.
Summary
A hazard stops the next instruction from executing in its planned cycle, forcing stalls and raising CPI above 1.
Structural hazards come from resource conflicts and are usually removed by adding hardware.
Data dependences are RAW (true), WAR (anti) and WAW (output). In the in-order 5-stage pipeline only RAW causes hazards: adjacent RAW costs 2 stalls without forwarding (split-cycle register file).
Control hazards cost (resolution stage - 1) cycles per branch if the pipeline simply waits; in the GATE 2013 example this gave 15 cycles = 165 ns.
CPI = 1 + stall cycles per instruction; speedup = depth / (1 + stalls per instruction). Our example lost nearly half of the ideal speedup (2.63 instead of 5).
Next, in Handling Hazards: Stalls, Forwarding & Branch Prediction, we learn how real processors detect hazards in hardware and recover most of this lost performance.