Skip to content
Tutorials Center
My learning

Topics

Lesson 60 of 67 ยท Projects

Project: A Pipeline Hazard Visualizer

Parse small assembly programs, find data hazards, and draw five-stage pipeline charts with and without forwarding, including load-use and branch stalls.

A pipeline diagram is the best tool for understanding why some instruction sequences run at one instruction per cycle while others crawl. Drawing them by hand is slow and error-prone, so in this project you write a program that does it. You give it a few lines of assembly, and it finds the data hazards, works out which instructions must wait, and prints a cycle-by-cycle chart, once without forwarding and once with.

It applies Instruction Pipelining and Pipeline Hazards. By the end you will have a tool that answers the question every exam and every architect asks: how many cycles does this code take?

The model

The visualizer simulates a classic five-stage in-order pipeline:

Stage Name What happens
IF Instruction fetch read the instruction at the PC
ID Instruction decode decode and read the source registers
EX Execute ALU work, address calculation, branch decision
MEM Memory access loads and stores use memory
WB Write back write the result into the register file

Four rules keep the model small but honest:

  1. One instruction per stage per cycle, strictly in order. An instruction that must wait holds up everything behind it.
  2. Registers are written in the first half of a cycle and read in the second half. So an instruction in ID may read a value that its producer writes in WB during the same cycle.
  3. Without forwarding, a consumer must wait in ID until the cycle in which its producer is in WB.
  4. With forwarding, results are routed straight from the pipeline registers into the ALU inputs. An ALU result is available to the very next instruction with no delay. A load result only exists after MEM, so a consumer right behind a load must wait one extra cycle (the load-use hazard).

The project also models the branch penalty: the pipeline does not know a branch is taken until it executes, so the instructions fetched after it are wrong. The visualizer treats the next instruction as fetched only after the branch leaves EX, which costs two cycles. You tell it which branches in the trace are taken.

flowchart LR
  subgraph P["Pipeline registers"]
    EXM["EX/MEM<br/>ALU result"]
    MEMW["MEM/WB<br/>load or ALU result"]
  end
  ALU["ALU inputs in EX"]
  EXM -->|"forward, 0 cycles lost"| ALU
  MEMW -->|"forward after a load, 1 cycle lost"| ALU

Forwarding paths: the producer's result is copied from a later pipeline register to the ALU input of the consumer.

Step 1: parse the program and find hazards

First the program must be read. The parser handles add, sub, and, or, addi, lw, sw and beq, and for each instruction records the register it writes (dest) and the registers it reads (srcs). A store writes memory but no register, a branch writes nothing, and r0 is always zero, so it never creates a dependence.

A read-after-write (RAW) hazard exists when an instruction reads a register that an earlier instruction writes. The function find_hazards remembers the last instruction that wrote each register and reports every consumer that follows. The distance between producer and consumer matters: a distance of 1 is the dangerous case, and by a distance of 4 the producer has already written its result back.

Python Parse and detect dependences

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 output lists five dependences. Four are at distance 1: the add needs the load's r1, the sub needs the add's r3, the store needs the sub's r5, and the or needs addi's r7. The fifth, r3 from instruction 1 to instruction 5, is four instructions apart: no stall is needed for it even without forwarding. Only the load result is marked specially, because it is the one forwarding cannot fully hide.

This tool only handles RAW hazards, the only kind an in-order five-stage pipeline suffers from. Write-after-read and write-after-write hazards appear in out-of-order machines, where register renaming removes them.

Step 2: schedule the pipeline

The scheduler walks through the instructions in order and decides the cycle each one is in each stage. For instruction i:

  1. It can enter IF when the instruction before it leaves IF.
  2. It can enter ID once the previous instruction has left ID, and not before its own fetch is done.
  3. It reads its registers in ID, but only once the values are ready. Without forwarding, a source is ready in the cycle its producer is in WB. With forwarding, it is ready right away, except that a load result costs one extra cycle.
  4. Once it passes ID, the later stages follow in consecutive cycles: EX, MEM, WB.

Waiting in ID is a stall: the instruction stays put, and since the stage ahead is empty (a bubble), the instructions behind queue up. The drawing function shows an instruction waiting in IF or ID with lowercase if and id, so a stall is easy to spot.

Run the scheduler on four instructions that each depend on the previous results.

Python Pipeline chart with and without 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 chart is a staircase of waiting. The sub stalls for 2 cycles, because it must wait until the add is in WB. The and needs sub's result, so it waits too, and the or waits for and. The four instructions take 14 cycles, a CPI of 3.50. With forwarding the chart is a perfect diagonal: each instruction starts one cycle after the previous one and the four finish in 8 cycles. That is the ideal 4 + 4 cycles (4 instructions plus 4 cycles to fill the pipeline) and a CPI of 2.00; for long programs the fill cost vanishes and the CPI approaches 1. The 6 saved cycles are the entire value of forwarding on this example.

Step 3: the hazards forwarding cannot fix

Forwarding is a big win but it cannot do everything. Two cases remain.

Load-use hazard. A load only has its data after the MEM stage, one stage too late for the very next instruction's EX. That instruction must wait one cycle even with forwarding. Instruction scheduling can hide the delay: move an independent instruction into the gap. The compiler (or you) can often do it, as the second chart shows.

Branch penalty. Until the branch finishes EX the pipeline does not know which instruction comes next, so the fetch of the next instruction has to wait. Here the visualizer shows that as two empty fetch slots after a taken branch. Real processors reduce this loss with branch prediction.

The next program draws three charts: the original load-use sequence, the same work with one load moved earlier, and a short trace with a taken branch. It ends with a summary table.

Python Load-use stalls, reordering and a branch

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 the original order both loads are followed immediately by an instruction that needs their data. Each costs one stall cycle, giving 11 cycles for 5 instructions. Moving the second lw up between the first load and its consumer keeps all five instructions and all five dependences but fills the load delay slot with useful work: 9 cycles, with no stalls at all. That is a 2-cycle saving from a change that does not alter the program's result.

The branch trace shows a different loss. The beq finishes EX in cycle 7, so the next lw cannot be fetched before cycle 8, leaving cycles 6 and 7 empty in the fetch row. Look at the gap in the chart: two cycles are lost, even with forwarding.

The summary shows how the three costs combine. Even in a pipeline with forwarding, every hazard that remains shows up as extra cycles per instruction (CPI above 1).

To check your reading of the chart, count the cycles by hand with the formula cycles = instructions + 4 + stalls. The original sequence has 5 instructions and 2 stalls: 5 + 4 + 2 = 11. If your formula and the tool disagree, one of them has a bug.

Ideas to extend it

  • Add a stall report that lists, for each stall, the cause (RAW on which register, load-use, or branch).
  • Reorder automatically: write a function that searches for an independent instruction to slide into each load-use gap, without breaking any dependence.
  • Model a branch predictor: add a predicted set and charge the penalty only for mispredictions.
  • Add structural hazards: give the machine one shared memory port, so a load's MEM cycle blocks the fetch of a later instruction.
  • Handle sw precisely: a store needs its data register only in MEM, so a load followed by a store of the same register needs no stall with forwarding. The visualizer simplifies this by treating every register read as needed in EX.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Without forwarding, when can a dependent instruction leave ID (in this model)?

    The register file is written in the first half of the cycle and read in the second, so the consumer can read the value in the same cycle as the producer's WB.
  2. 2. Why does a load followed immediately by an instruction using its result still stall with forwarding?

    A load's value is read in MEM, so it can only be forwarded to the cycle after. The consumer must wait one cycle.
  3. 3. How can instruction scheduling remove a load-use stall?

    An independent instruction fills the delay, so the pipeline does useful work in the cycle that would have been a bubble.
  4. 4. 4 instructions run with no stalls in a 5-stage pipeline. How many cycles do they take?

    cycles = instructions + (stages - 1) = 4 + 4 = 8: the first instruction needs 5 cycles and every later one finishes one cycle after the previous.
  5. 5. The visualizer charges two cycles after a taken branch. Why?

    Until the branch is resolved in EX, the pipeline cannot know the right next address, so that fetch happens two cycles later than it otherwise would.

Summary

  • A pipeline chart shows each instruction's stage in each cycle; stalls appear as repeated stage names.
  • A RAW hazard is a read of a register that an earlier, nearby instruction writes. Parsing the program and remembering the last writer of each register finds them all.
  • Without forwarding, the consumer waits until the producer's WB; with forwarding, only the load-use case costs one cycle.
  • Reordering independent instructions into a load's delay slot removes the stall without changing results.
  • A taken branch costs fetch bubbles until it is resolved in EX; prediction exists to reduce them.
  • A quick check: cycles = instructions + 4 + stall cycles, for a five-stage pipeline.

Next: the memory side of a real machine in Project: A Virtual Memory Manager.