RAW hazards, forwarding and stalls

A RAW hazard (read after write) appears when an instruction reads a register that an earlier instruction has not written yet. In a 5-stage pipeline it is the most common hazard, because registers are read in ID but written in WB, three stages later.

The problem: sub needs x1 too early

add  x1, x2, x3
sub  x4, x1, x5

add computes x1 in EX (cycle 3) and writes it in WB (cycle 5). sub reads its registers in ID in cycle 3. If nothing is done, it would read the old value of x1. The simplest fix is to hold sub in ID until the value is in the register file:

In the simulator, without forwarding, sub waits until add leaves WB: 3 bubbles. Many textbooks, Patterson and Hennessy among them, assume the register file is written in the first half of the cycle and read in the second; under that assumption sub can read in the same cycle as the WB and the wait is 2 bubbles. The simulator does not model that split cycle, so its numbers without forwarding are one higher.

Forwarding: use the result before it is written

add’s result already exists at the end of its EX, held in the EX/MEM pipeline register. Forwarding adds multiplexers at the ALU input to take the operand from there instead of from the register file:

No bubbles. If there is another instruction between the two, the value is taken one cycle later, from the MEM/WB register. These are the two forwarding paths of the classic pipeline:

• EX/MEM → EX: the producer is right in front (distance 1).
• MEM/WB → EX: there is one instruction in between (distance 2).

add  x1, x2, x3
addi x9, x9, 1
sub  x4, x1, x5

With forwarding this sequence has no bubbles; without forwarding the simulator inserts 2 (check it).

The exception: load followed by use

lw   x1, 0(x2)
add  x3, x1, x4

A load does not have its data at the end of EX but at the end of MEM, because EX only computes the address. add needs it at the start of its EX, which without a wait would coincide with lw’s MEM. No forwarding path can send data back in time, so a bubble is needed; afterwards the value arrives from MEM/WB:

The hazard detection unit catches it in ID: if the instruction in EX is a load and its rd matches rs1 or rs2 of the instruction in ID, it stalls the pipeline for one cycle. That is what the simulator implements.

Avoiding the bubble by reordering

If there is an independent instruction nearby, it can be placed between the load and its use. This sequence has a load-use bubble between lw and add:

addi does not depend on lw, so we move it up:

9 cycles become 8, the minimum for 4 instructions. The program’s result does not change because addi neither reads nor writes t0 or t1. Compilers do this instruction scheduling automatically.

What about WAR and WAW hazards?

Write after read (WAR) and write after write (WAW) do not occur in this pipeline: instructions move in order, all of them read their registers in ID and all of them write in WB. They only matter in out-of-order processors.

Practice

The load-use exercise asks you to count cycles with and without forwarding, and the reordering exercise checks the last section.