Data Hazards

Consider the short sequence beside this paragraph. The first instruction, add x3, x7, x6, writes its sum into x3. Every one of the four instructions that follow it then reads x3, and the last of them reads it twice. This is not a contrived program. It is what ordinary code looks like when a value is computed once and then used, which is most of the time.

Now put that sequence on the pipeline and watch the clock. The add computes its sum in Execution during cycle 3, but it does not write that sum into the register file until Writeback, in cycle 5. The or behind it reads the register file during its own Decode stage, in cycle 3, and the sub behind that reads in cycle 4. Both go looking for x3 before the add has put anything there, so both walk away with whatever x3 held before this program started. The pipeline does not stumble or complain. It computes two confidently wrong answers and carries them forward.

The chart beside this paragraph draws the same five instructions against a single time axis, with an arrow from the point where x3 is written to each point where it is read. Two of those arrows point backwards. The or wants a value in cycle 3 that does not exist until cycle 5, and the sub wants it in cycle 4. An arrow that runs backwards in time is the visual signature of a hazard, and it is the fastest way to spot one. The last two arrows are fine. The sw reads in the very cycle the write happens and the and reads a cycle later, and we will see in a moment why the first of those two is safe.

That is a data hazard: an instruction needs a value that an instruction ahead of it has not finished writing. It is worth being precise about what has gone wrong, because it is a timing failure rather than a logic failure. Nothing in the datapath computes the wrong function. The right value is produced by the right hardware at the right stage. It simply arrives at the register file later than the instruction behind it thinks to look.

Redrawn with forwarding, the chart has no backwards arrows left in it. The sum leaves the add at the end of its Execution stage and travels forward into the Execution stage of the or and then of the sub. Every arrow now points the way time does, which is the whole test of whether a value can be delivered at all. Forwarding cannot rescue a value that has not been computed yet, and that limit will matter a great deal later, but for arithmetic feeding arithmetic it is enough.

Knowing that a wire is needed is a different problem from knowing when to use it, and the second is the one the hardware solves every cycle. To state that condition precisely we will name each signal after the pipeline register it is stored in. A signal written EX/MEM_rd is the rd field held in the EX/MEM pipeline register, the destination of the instruction leaving Execution for Memory, and ID/EX_rs1 is the rs1 field held in the ID/EX register, the first source of the instruction entering Execution. The prefix says where the value sits, and because a pipeline register holds one instruction's worth of state, it also names the instruction it belongs to.

With that notation the two failures in our program become two very short statements. In cycle 4 the add is in Memory and the or is in Execution, so the destination of the one and the first source of the other are sitting one register apart, and EX/MEM_rd equals ID/EX_rs1. In cycle 5 the add has moved on to Writeback and the sub has reached Execution, and since x3 is the second source of a sub, this time MEM/WB_rd equals ID/EX_rs2. Both are comparisons between two register numbers that the pipeline is already carrying, which is what makes them cheap to test in hardware.

Generalizing from those two gives four conditions, and they fall into two natural pairs. The pair that compares against the EX/MEM register we will call the EX hazards, since the value being forwarded comes from the instruction leaving Execution. The pair that compares against the MEM/WB register we will call the MEM hazards, since the value comes from the instruction leaving Memory. Both sets are beside this paragraph.

Those four are necessary but they are not yet sufficient, and a forwarding unit built on them alone would corrupt perfectly good programs. The first gap is that not every instruction writes a register. A store and a branch both carry bits in the position where rd lives, because the field is at bits 11 down to 7 in every format that has one and the hardware pulls it out without asking what the instruction is. Those bits are meaningless for an instruction that never writes back, and matching against them would forward a value that was never produced. The cure is to consult the control the instruction is already carrying and require that regWrite is asserted in the stage we are forwarding from.

The second gap is x0. In RISC-V register zero is hardwired to the value zero and reading it always yields zero, no matter what any instruction claims to have written there. That makes x0 a perfectly legal destination for an instruction whose result is being thrown away, and add x0, x3, x12 is a normal thing to find in a program. The ALU still computes a sum for it, and that sum still appears in the EX/MEM register alongside a rd of zero. If a later instruction reads x0, the four conditions above would match and we would forward a non-zero number to an instruction that is entitled to receive zero. So both comparisons also require EX/MEM_rd ≠ 0 and MEM/WB_rd ≠ 0.

The delivery mechanism is smaller than the decision. Each ALU input gains a 3x1 multiplexer in front of it, choosing between the operand the register file read during Decode, the value held in the EX/MEM register, and the value held in the MEM/WB register. Two select signals drive them, one per operand, and a small combinational block generates both. That block is the forwarding unit. It sits under the ID/EX register with the register numbers and the write enables running into it and the two selects running back out to the multiplexers.

module forwarding_unit (
    input  wire [4:0] IDEX_rs1,
    input  wire [4:0] IDEX_rs2,
    input  wire [4:0] EXMEM_rd,
    input  wire [4:0] MEMWB_rd,
    input  wire       EXMEM_regWrite,
    input  wire       MEMWB_regWrite,
    output reg  [1:0] IDEX_forwardA,
    output reg  [1:0] IDEX_forwardB
);

  always @(*) begin
    // defaults: no forwarding, read from register file
    IDEX_forwardA = 2'b00;
    IDEX_forwardB = 2'b00;

    // ---- IDEX_forwardA ----
    if (EXMEM_regWrite && (EXMEM_rd != 5'd0)
                       && (EXMEM_rd == IDEX_rs1))
      IDEX_forwardA = 2'b10;  // from EX/MEM
    else if (MEMWB_regWrite && (MEMWB_rd != 5'd0)
                            && (MEMWB_rd == IDEX_rs1))
      IDEX_forwardA = 2'b01;  // from MEM/WB

    // ---- IDEX_forwardB ----
    if (EXMEM_regWrite && (EXMEM_rd != 5'd0)
                       && (EXMEM_rd == IDEX_rs2))
      IDEX_forwardB = 2'b10;
    else if (MEMWB_regWrite && (MEMWB_rd != 5'd0)
                            && (MEMWB_rd == IDEX_rs2))
      IDEX_forwardB = 2'b01;
  end

endmodule

The chart beside this marks that arrow not possible for that reason, and no wiring will fix it. What fixes it is time. The pipeline stalls for one cycle, and one is enough: the dependent instruction then reaches Execution after the load has left Memory, where the forwarding unit can deliver the value as it would any other. Holding an instruction back is not the same as pausing, because the front of the pipeline is still fetching. We must hold both the program counter and the IF/ID pipeline register, so that we pick up exactly where we left off when the stall lifts. Along the laundry analogy, it is as if we restart the washer with the same clothes still inside while the dryer tumbles on an empty drum. The dryer is the back half of the pipeline, which cannot freeze, because Execution, Memory and Writeback each have to do something this cycle. What they do is nothing, in the precise sense of a NOP, an instruction with no effect. We insert one by setting every control line in the ID/EX pipeline register to zero, so the instruction traveling down the back half writes no register and touches no memory. That hole is called a bubble, and the chart below draws it moving through the stages like an air bubble in a water pipe.

None of that happens on its own, so the last piece is the hardware that notices. The forwarding unit works from the ID/EX register, which is one stage too late for this job, since by the time the dependent instruction has reached Execution the chance to stall it has already gone. So a second block sits a stage earlier and watches Decode. It is called the hazard detection unit, and its test is a single line. The instruction in ID/EX must be a load, which the control signal memRead already tells us, and its destination must match a source of the instruction still sitting in IF/ID, so ID/EX_rd equals either IF/ID_rs1 or IF/ID_rs2. When both hold, the unit does all three of the things above at once. It holds the PC, it holds IF/ID, and it forces the control lines entering ID/EX to zero. One cycle is the entire cost, and it is the reason a compiler will try to schedule an unrelated instruction into the slot behind a load rather than leave the machine to buy that cycle back at run time.

module hazard_detection_unit (
    input  wire [4:0] IFID_rs1,
    input  wire [4:0] IFID_rs2,
    input  wire [4:0] IDEX_rd,
    input  wire       IDEX_memRead,
    output reg        IFID_pcWrite,
    output reg        IFID_write,
    output reg        IFID_stall
);

  always @(*) begin
    // defaults: pipeline advances normally
    IFID_pcWrite = 1'b1;
    IFID_write   = 1'b1;
    IFID_stall   = 1'b0;

    // load-use hazard: load in EX, its result
    // needed by the instruction in ID
    if (IDEX_memRead && (IDEX_rd != 5'd0)
                     && ((IDEX_rd == IFID_rs1) ||
                         (IDEX_rd == IFID_rs2))) begin
      IFID_pcWrite = 1'b0;  // hold PC
      IFID_write   = 1'b0;  // hold IF/ID
      IFID_stall   = 1'b1;  // zero ID/EX control
    end
  end

endmodule