Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 67 ยท CPU Design

Pipeline Hazards: Structural, Data and Control

Learn the three kinds of pipeline hazards, how stalls, forwarding and scheduling fix them, and watch them appear in a Python pipeline simulator.

An ideal pipeline finishes one instruction per cycle. Real programs do not cooperate: one instruction needs the result of the one just before it, two instructions want the same hardware at the same moment, and a branch makes the CPU fetch instructions it should not have. These situations are hazards. Each one forces the pipeline to wait, producing empty slots called bubbles or stalls, and each stall raises the CPI above 1.

There are three kinds: structural hazards (a resource conflict), data hazards (a value is not ready yet) and control hazards (the next instruction is not known yet). You will meet them in order, see how hardware and software fix them, and watch each one appear in a Python simulator of the five-stage pipeline from Instruction Pipelining.

The simulator

The simulator has two parts. First, a tiny interpreter runs a program on our RISC instruction set and records the trace: the instructions that actually executed, in order, with their destination register, source registers and whether a branch was taken. Second, a scheduler assigns each instruction a clock cycle for every stage, following the rules of an in-order five-stage pipeline:

  • IF, ID, EX, MEM and WB take one cycle each. The register file is written in the first half of a cycle and read in the second half, so an instruction can read in the very cycle in which an earlier instruction writes.
  • An instruction that must wait stays in ID, and everything behind it waits too.
  • Without forwarding, a value is usable only after the producer's WB stage.
  • With forwarding, an ALU result is usable in the cycle after the producer's EX; a loaded value, in the cycle after its MEM.
  • A branch is resolved at the end of EX; a jump is known after ID.

Stalled cycles are drawn with a * (for example ID*). The scheduler is the same in all three TryIts below; only the options and programs change.

Data hazards

A data hazard appears when an instruction needs a register that an earlier, still unfinished instruction will write. The common kind is read after write (RAW): the second instruction must read the value the first one produces. Consider:

TEXT
ADDI r1, r0, 5
ADDI r2, r1, 3     ; reads r1, produced one instruction earlier
ADD  r3, r2, r1    ; reads r2 (just produced) and r1
SW   r3, 0(r0)     ; reads r3 (just produced)

Every instruction depends on the one before it. In a pipeline the first instruction does not write r1 until its WB stage, which is three cycles after the second instruction wants to read it in ID.

flowchart LR
  subgraph I1["ADDI r1, r0, 5"]
    direction LR
    A1["IF"] --> A2["ID"] --> A3["EX"] --> A4["MEM"] --> A5["WB: r1 written"]
  end
  subgraph I2["ADDI r2, r1, 3"]
    direction LR
    B1["IF"] --> B2["ID: needs r1"]
  end
  A5 -. "too late" .-> B2

The value of r1 is written in WB, but the next instruction needs it in ID, three cycles earlier.

There are two fixes. Stall (hardware inserts bubbles until the value is written back) is simple but slow. Forwarding (also called bypassing) adds extra wires and multiplexers that carry a result straight from the end of EX, or from the MEM stage, back to the ALU input of the next instruction, without waiting for the register file. The first TryIt detects the dependencies, then schedules the program without and with forwarding.

Python Data hazards: stalls versus forwarding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without forwarding, the four instructions take 14 cycles with 6 stall cycles: each dependent instruction sits in ID until its producer has written back, and its successors queue up behind it in IF. With forwarding they take 8 cycles, the ideal 4 + 4 for the pipeline fill, and no stalls. (The CPI printed does not count the 4 fill cycles: 1.00 means one instruction per cycle once the pipeline is running.) The detector reports each dependency with its distance: the closer the producer, the longer the wait. Forwarding costs wires and multiplexers in front of the ALU, but it is so valuable that essentially every pipelined CPU has it.

The load-use hazard

Forwarding cannot fix everything. A load gets its data only at the end of MEM, which is one stage later than an ALU result is ready. If the very next instruction needs the loaded value in EX, that value does not exist yet, and the pipeline must stall one cycle even with forwarding. This is the load-use hazard.

The compiler or assembly programmer can often hide it: put an independent instruction between the load and its use. This is instruction scheduling, and it changes timing without changing the result.

Python The load-use hazard and instruction scheduling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The original order loses one cycle to the load-use hazard (the ADD shows ID*): 9 cycles for 4 instructions. Swapping the second and third instructions gives the load time to finish, and the same four instructions take 8 cycles with identical results. Without forwarding the same programs need 10 and 9 cycles, so the two techniques combine: forwarding removes most stalls, and scheduling removes the one that forwarding cannot.

Structural hazards

A structural hazard happens when two instructions need the same hardware in the same cycle. The classic example is a pipeline with only one memory for both instructions and data. A load or store in its MEM stage and the fetch of a later instruction in its IF stage both want to use the memory port at the same time. One of them must wait.

The fix is more hardware: separate instruction and data memories (or, in modern CPUs, separate L1 instruction and data caches, as described in the Von Neumann lesson), and a register file with two read ports and a separate write port. Pipelines are designed so that each stage uses its own hardware, which is why our datapath has two memories.

Control hazards

A control hazard is caused by branches. The CPU must keep fetching, but the next address is not known until the branch is resolved. In our pipeline, BEQ compares in EX, so by the time its outcome is known, two more instructions have already entered IF and ID. If the branch is taken, they are on the wrong path and must be flushed, replaced by bubbles. That makes the branch penalty two cycles. A J is known after ID and costs one.

flowchart LR
  B["BEQ in EX<br/>outcome known"] -->|"not taken"| K["wrong-path guesses were right:<br/>no cost"]
  B -->|"taken"| F["flush 2 fetched instructions<br/>fetch from the target"]

With "predict not taken", only taken branches pay the penalty.

There are three simple policies:

  1. Stall until the branch is resolved. Safe, but every branch costs two cycles.
  2. Predict not taken: keep fetching the next instructions and flush them only if the branch is taken. Not-taken branches are free.
  3. Smarter prediction: guess taken or not taken from history. That is the subject of Branch Prediction.

The last TryIt looks at both a structural and a control hazard. Part one shows a load followed by independent instructions in a machine with a single shared memory. Part two runs a loop on the pipeline with the two branch policies and prints the CPI of each.

Python Structural and control hazards

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In part one, the load's MEM stage falls in the same cycle as the fetch of the fourth instruction. With a shared memory, the fetch has to wait, and a one-cycle bubble appears in the chart for the instructions behind it. With separate instruction and data memories the program takes 9 cycles, with one shared memory it takes 10.

Part two runs a loop whose J is taken on every iteration. Counting from the output: each of the 4 iterations has a jump costing 1 bubble, and the last BEQ is taken and costs 2, so "predict not taken" loses 6 cycles. The stall policy also charges 2 cycles to each of the 4 not-taken branches, which is 8 additional lost cycles. The CPI is 1.67 for the stall policy (39 cycles) and 1.29 for predict-not-taken (31 cycles), so even a trivial guess is much better than always waiting. (The CPI does not count the 4 fill cycles.)

Our model keeps the numbers simple. Real pipelines have more forwarding paths, handle exceptions, and deal with caches that miss (a load that misses can stall the pipeline for hundreds of cycles). But the three categories of hazard are the same.

Putting it together: CPI with stalls

All hazards add up in the CPI:

CPI = 1 + (stall cycles per instruction)

For example, with 20% loads of which half are followed immediately by an instruction that uses the loaded value (0.2 x 0.5 x 1 stall = 0.1 stalls per instruction), 15% branches of which 40% are taken at a 2-cycle penalty (0.15 x 0.4 x 2 = 0.12), the pipeline CPI is about 1.22. Pipelining still beats the single-cycle design in most cases, but the extra hardware (forwarding, hazard detection, flushes) has a price. The next lesson examines the biggest remaining source of stalls: Branch Prediction.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which kind of hazard is caused by two instructions needing the same hardware in the same cycle?

    A structural hazard is a resource conflict, such as one memory port used for both a data access and an instruction fetch.
  2. 2. What does forwarding (bypassing) do?

    Forwarding wires carry EX or MEM results back to the ALU inputs so a dependent instruction does not wait for write back.
  3. 3. Why can a load-use hazard not be removed completely by forwarding?

    Memory data arrives one stage later than an ALU result, so a dependent next instruction must stall one cycle.
  4. 4. What is the best way to remove a load-use stall in software?

    Placing an independent instruction in the gap gives the load time to finish, without changing the program's result.
  5. 5. A branch is resolved in EX of a 5-stage pipeline, and the CPU predicts not taken. What happens when the branch IS taken?

    Two instructions behind the branch were already fetched and decoded; they are discarded and fetching restarts at the branch target.

Summary

  • Hazards stop an ideal pipeline from finishing one instruction per cycle: structural (resource conflict), data (value not ready) and control (next address unknown).
  • Data hazards (read after write) are mostly solved by forwarding; a load followed by an instruction that uses its value still costs one stall, which compilers can hide by reordering.
  • Structural hazards are removed with more hardware, such as separate instruction and data memories.
  • Control hazards cost a branch penalty (2 cycles when resolved in EX); predicting not taken makes not-taken branches free.
  • Total CPI is 1 plus the average stall cycles per instruction.

Continue with Branch Prediction.