When the line jams: hazards and forwarding

Three ways a pipeline can jam

Lesson 1 ran the five-stage pipeline under two silent assumptions, spelled out by the notes on page 20: every instruction is independent of the others, and there are no branches or jumps. Drop either and the overlap stops being free. The word for what goes wrong is hazard.

Each stall is a cycle in which no instruction completes — the reason the real CPI of a pipeline sits above 1 (lesson 3). Think of the assembly line as a laundry: washer, dryer, folding table, ironing board, closet, one load in each. Three things can jam it (notes, pages 20–21):

• Structural hazard — two instructions want the same hardware in the same cycle: one dryer, two loads. The notes' example: one memory for instructions and data, so the IF of one instruction collides with the MEM of another.
• Data hazard — an instruction needs a result an earlier one has not produced yet: the folding table waits for a shirt still in the dryer.
• Control hazard — the next instruction to fetch is unknown because a branch is undecided: which basket comes next depends on a decision nobody has made. This class waits for lesson 4.

Data hazards are this lesson. Here is the notes' example (page 21), written as the 2026 exam paper writes code — capital mnemonics, registers R1, R2 … and offset(Rbase) addressing (the 2024 and 2025 papers put a dollar sign in front of every register, $R1, $F2: same thing); the notes spell it lw x2, 0(x1) / add x3, x2, x4, and x2 is R2, register number 2.

I0   LD   R2, 0(R1)      # R2 = memory[R1 + 0]
I1   ADD  R3, R2, R4     # needs R2

Three orders of access, one of them real

Two instructions that touch the same register can collide in three orders, named after the order the accesses must keep; the "dependency analysis" table of Exercise 1 has a second name for each:

• RAW, read after write: the later instruction reads what the earlier one writes — a true data dependence, "RAW with I0 for R2" in the papers. This is Fig. 1.
• WAR, write after read: the later instruction writes a register the earlier one still has to read — an anti-dependence.
• WAW, write after write: both write the same register and the later value must win — an output dependence.

A fact the notes leave out and examiners like to ask: in the five-stage in-order pipeline only RAW can happen. Every instruction reads in ID and writes in WB, three stages later, and none overtakes another (Fig. 2).

Structural hazards are absent for a different reason: they were designed away. The datapath of lesson 1 has separate instruction and data memories, a register file with two read ports and one write port, and its own adder for PC + 4, so no two stages compete for a resource. The notes turn this into a slogan that is too strong (red pen below). The papers never make the slogan; what they state, as a machine assumption of every VLIW exercise of 2024–2026, is one of those design decisions: "in the Register File, it is possible to read and write at the same address at the same clock cycle" — the split-cycle register file of the next section.

One more thing an examiner likes to ask: which classes can hardware remove for good? Structural hazards, yes — duplicate the resource and they are gone. Data hazards it can only reduce: forwarding takes most of the stalls, and this lesson ends with the one it cannot take. Control hazards it can only guess around: prediction, lessons 4–6.

In the five-stage in-order pipeline only two things can go wrong: a RAW dependence and a branch. Everything else was designed away.

The distance rule: what a RAW costs without forwarding

Start with the plain machine: no forwarding, but one cheap trick in the register file that every exam paper assumes. The notes describe it on page 22: the register file is written in the first half of the clock cycle and read in the second half, so an instruction in WB and one in ID exchange a value within the same cycle. This is the split-cycle register file — the "read and write at the same address at the same clock cycle" of the exam texts.

Example 2 of the notes, cycle by cycle

Now put the consumer right behind the producer — Example 2 of the notes (page 23), the pair of every exercise of this kind:

I0   SUB  R2, R1, R3     # R2 = R1 - R3
I1   AND  R12, R2, R5    # needs R2 at once

Walk it. Cycle 3: SUB is in EX computing R2; AND is in ID and wants R2, but the register file still holds the old value. Cycle 4: SUB is in MEM, R2 sits in the EX/MEM pipeline register; AND is held in ID. Cycle 5: SUB writes R2 in the first half of the cycle, AND reads it in the second half and moves to EX in cycle 6. Two cycles lost. The table is the form of every such exercise: a row per instruction, a column per clock cycle.

The example generalises into a rule the notes never state but all their tables obey. Call \(d\) the distance from producer to consumer: \(d = 1\) for the very next instruction, \(d = 2\) with one instruction between them, and so on.

1. Clock the producer. Fetched in cycle \(t\), it goes through IF, ID, EX, MEM, WB in cycles \(t, t+1, t+2, t+3, t+4\); its result enters the register file in WB:

   \[ \text{write} = t + 4 . \]

2. The consumer is \(d\) instructions later: fetched in cycle \(t + d\), it reads its registers in ID in cycle \(t + d + 1\) if nothing holds it.

3. Hold it \(s\) cycles in ID; the read happens in cycle \(t + d + 1 + s\). With the split-cycle register file a read in the same cycle as the write sees the new value, so

   \[ t + d + 1 + s \ge t + 4 . \]

4. Solve for \(s\); a stall count cannot be negative:

   \[ s = \max(0,\ 3 - d) . \]

   \(d = 1\): two stalls (Example 2). \(d = 2\): one. \(d = 3\): none — the I1 to I4 pair of Fig. 3.

5. Without the split-cycle file the read must come strictly after the write, \(t + d + 1 + s \ge t + 5\), so \(s = \max(0,\ 4 - d)\): one more stall at distances 1 to 3. That is what the papers' assumption line saves you.

A load obeys the same rule without forwarding: its value also reaches the register file in WB. Loads and ALU instructions part ways only once forwarding exists.

A stall freezes everything behind it

The two-row table hides one thing: when an instruction is held in ID, the instruction behind it cannot enter ID and is held in IF, and everything further back waits too. The notes' Figure 9 (page 26) has five instructions that all read R2 after SUB writes it. Recomputed:

I0   SUB  R2, R1, R3
I1   AND  R12, R2, R5    # d = 1: 2 stalls
I2   OR   R13, R6, R2    # d = 2, held in IF behind I1: 0
I3   ADD  R14, R2, R2    # d = 3: 0
I4   SD   R15, 100(R2)   # d = 4: 0

Only I1 pays: by the time I2 reaches ID in cycle 6 the write is done, and I3 and I4 are later still. By hand, work row by row with one rule — an instruction enters a stage only in the cycle after the one ahead of it has left that stage — and I1's stalls push I2 along by themselves. The total is the cycle of the last WB: 11 = 5 instructions + 4 cycles of fill + 2 stalls, the formula sheet's \(\text{cycles} = IC + 4 + \text{stalls}\); lesson 3 turns it into CPI and seconds.

Forwarding: one wire and one comparison

Look at Example 2 again. R2 is computed at the end of cycle 3 and sits, finished, in the EX/MEM pipeline register during cycle 4 — exactly the cycle in which AND would like to execute. The two stalls carry an existing value through MEM, WB and back out of the register file. Forwarding (the notes also say bypassing) adds a wire from the pipeline register straight to the ALU input, and a multiplexer that chooses between the register-file value and the wire.

The three paths, in the names the course uses

The notes name each path by the stage the value comes from and the stage it goes to (pages 23–24). All three take the value from a pipeline register, never from the register file:

• EX/EX path — from the EX/MEM register (the previous ALU result) to the ALU input. Serves an ALU producer at distance 1: Example 2, 0 stalls.
• MEM/EX path — from the MEM/WB register to the ALU input. Serves an ALU producer at distance 2, when the value has moved one register further, and — the case the notes' Figure 6 draws while their text names only the first — a load, whose value is born in MEM and only ever exists in MEM/WB. Name the wire by its ends, not by one use.
• MEM/MEM path — from the MEM/WB register to the write-data input of the data memory. Serves a load followed by a store of the loaded value: the store needs the data only in its MEM stage, exactly when the load's data sits in MEM/WB (the notes' Figure 7).

Store data from an ALU producer, and the base register of a load or store, go through the same ALU-input multiplexers, so EX/EX and MEM/EX cover them too. With forwarding, Example 2 shrinks to the notes' second table:

What the forwarding unit actually does

Figure 8 of the notes (page 24) is Patterson and Hennessy's forwarding datapath, and it gives away the secret: forwarding is a comparison of register numbers. When an instruction was decoded in ID, its source numbers rs1 and rs2 were copied into ID/EX; the two instructions ahead of it carry their destination number rd in EX/MEM and MEM/WB. The forwarding unit compares them while the instruction is in EX and sets the multiplexers. In the textbook's words (background from the book, not in the notes), for the first ALU input:

EX hazard:
  if EX/MEM.RegWrite and EX/MEM.rd != R0
     and EX/MEM.rd == ID/EX.rs1
  then ForwardA = EX/MEM        # EX/EX path

MEM hazard:
  if MEM/WB.RegWrite and MEM/WB.rd != R0
     and MEM/WB.rd == ID/EX.rs1
     and not (EX hazard on rs1)
  then ForwardA = MEM/WB        # MEM/EX path

Two details matter. The clause "not EX hazard" gives priority to the newest result: in ADD R1, R1, R2 / ADD R1, R1, R3 / ADD R1, R1, R4 both older instructions match R1, and the third add must take the second one's value, in EX/MEM. And R0 is excluded because it is hard-wired to zero: an instruction that "writes" R0 forwards nothing.

The table collects what forwarding buys, read as the exam reads it: producer, consumer, distance.

The one stall no wire can remove: load-use

Fig. 5 puts the two producers side by side. An ALU result is born at the end of EX, one cycle before the next instruction's EX: the EX/EX wire delivers it just in time. A load's value is born at the end of MEM — the memory has to answer first — while the next instruction's EX runs in that same cycle: there is nothing to forward yet. The consumer waits one cycle, then MEM/EX hands it the value. This is the load-use hazard: one stall even with full forwarding, the fact of the chapter most worth remembering.

Who inserts the bubble

The forwarding unit works in EX; it can route a value but cannot hold an instruction back. The load-use case needs a second circuit one stage earlier, the hazard detection unit of Patterson and Hennessy (background from the book: the notes draw the bubble but never say who makes it). It sits in ID and asks: is the instruction in EX a load whose destination is one of my sources?

if ID/EX.MemRead
   and (ID/EX.rd == IF/ID.rs1 or ID/EX.rd == IF/ID.rs2)
then stall one cycle

One refinement the course's third wire forces on the book's rule: when the instruction in ID is a store and the match is on its data register, there is no stall — the data is needed only in MEM, where the MEM/MEM path delivers it (the Figure 7 table above). Only the base register of a store goes through the test.

Stalling is three actions in one cycle (Fig. 6): freeze the PC, so the same instruction is fetched again; freeze the IF/ID register, so the instruction in ID stays and reads its registers again next cycle; and zero the control signals entering ID/EX, so the stage downstream executes a nop. That zeroed set of control signals is the bubble; it travels through EX, MEM and WB doing nothing.

Who fixes it: the compiler or the hardware

Everything so far was hardware. The notes (page 25) sort the answers to a RAW hazard by who acts: static solutions are applied by the compiler before the program runs, dynamic solutions by the hardware while it runs. Keep the two words; they return for scheduling (VLIW against Tomasulo) and branch prediction.

The notes' Examples 3 and 4, corrected

Now the warm-up puzzle. The notes insert one nop (Example 3, page 25) or one independent instruction (Example 4, page 26) between SUB R2 and AND R12, R2, R5 and declare R2 ready. Run the distance rule: without forwarding the pair needs two stalls, so one filler turns \(d = 1\) into \(d = 2\) and removes one stall. The hardware still inserts the other — or, without interlocks, AND reads the old R2.

# no forwarding: the consumer must be the third instruction after
I0   SUB  R2, R1, R3
I1   NOP                 # or an independent instruction
I2   NOP                 # or a second one
I3   AND  R12, R2, R5    # reads R2 in cycle 5 = SUB's WB: ready

# with forwarding: nothing between an ALU producer and its consumer
I0   SUB  R2, R1, R3
I1   AND  R12, R2, R5    # EX/EX path

# with forwarding, a load producer: exactly one slot
I0   LD   R2, 0(R1)
I1   NOP                 # fill it with useful work
I2   ADD  R3, R2, R4     # MEM/EX path, 0 stalls

Why does a hardware stall beat the compiler's nop if both lose a cycle? Because the nop is a real instruction — fetched, counted in IC, and the program grows — and the compiler had to know the pipeline depth of the machine the code would run on; an interlock costs a comparator and nothing else. And why does the compiler still matter when forwarding exists? Because of the one slot forwarding cannot fill: after every load something useful should go into the load-use slot. That is the beginning of compiler scheduling, the main tool of lesson 15 and the VLIW lessons.

So the warm-up has its answer: two empty slots without forwarding, none with it — and the one-slot case the notes were reaching for exists: the slot after a load.

Forwarding is a comparison of register numbers in the pipeline registers, and it removes every data-hazard stall but one: the slot after a load.