Data Hazards and Forwarding

A data hazard arises when two instructions that are close together in the pipeline access the same register, and the order in which the pipeline would naturally access it differs from program order. The classical taxonomy has three kinds, defined relative to a pair of instructions $i$ (earlier) and $j$ (later):

• RAW (read-after-write): $j$ reads a register that $i$ writes. This is a true dependency — $j$ genuinely needs $i$'s result. If $j$ reads before $i$ writes, it gets the wrong value.
• WAR (write-after-read): $j$ writes a register that $i$ reads. If $j$ writes before $i$ reads, $i$ picks up the wrong value. This is a false (name) dependency — no real data flows between them.
• WAW (write-after-write): $i$ and $j$ both write the same register. If they complete out of order, the register ends up with $i$'s value instead of $j$'s.

In the classic in-order, single-issue five-stage pipeline (IF, ID, EX, MEM, WB), only RAW hazards actually occur, because instructions read operands in ID and write results in WB, always in program order and always with each instruction's ID stage happening before later instructions' ID stages, and WB happening in the same relative order. WAR and WAW require instructions to be reordered or to read/write out of program sequence, which does not happen in this simple in-order design; they become real concerns only in more advanced techniques such as out-of-order execution, where Structural Hazards-style resource conflicts and reordering can let a later instruction's write or read race ahead. So the problem to solve here is exactly RAW: an ALU instruction produces a value at the end of its EX stage (or MEM/WB for loads), but that value logically belongs to the destination register the instant the instruction is "conceptually" done, long before it is physically written into the register file in WB. Forwarding (or bypassing) exploits the fact that the value already exists in a pipeline latch several cycles before WB; it just needs a wire and a multiplexer to deliver it early to any later instruction's ALU input, rather than forcing that instruction to fetch a stale copy from the register file.

Consider the standard five-stage MIPS/RISC-V-style pipeline. Each instruction passes through IF → ID → EX → MEM → WB, one stage per cycle, with the ID stage reading register operands from the register file and the WB stage writing a result back. Register-file reads and writes happen in the same cycle when they alias (write-then-read within a cycle, so a same-cycle WB/ID pair on the same register already works via internal register-file bypassing), but that alone does not fix the tighter cases. Take this instruction sequence: ``` add $t0,$t1, $t2 ; I1:$t0 = $t1 +$t2 sub $t3,$t0, $t4 ; I2: needs$t0, immediately after I1 defines it and $t5,$t0, $t6 ; I3: also needs$t0 or $t7,$t0, $t8 ; I4: also needs$t0, but by now WB has happened ``` Lay these out on a pipeline diagram (cycles across the top, stages across the rows): ``` Cycle: 1 2 3 4 5 6 I1 (add): IF ID EX MEM WB I2 (sub): IF ID EX MEM WB I3 (and): IF ID EX MEM WB I4 (or ): IF ID EX MEM WB ``` I1 computes `$t0` in its EX stage, which finishes at the end of cycle 3, and that value sits in the EX/MEM pipeline register at the start of cycle 4. I2's EX stage is also cycle 4 — I2 needs `$t0` exactly when I1's fresh result is sitting one stage ahead of it. Without forwarding, I2's ID stage (cycle 3) would have already read the register file and gotten the old, wrong value for `$t0`, and even if ID happened later I1's WB does not occur until cycle 5. So the value must be routed from the EX/MEM latch (produced at the end of cycle 3) directly into the ALU input for I2's EX stage (cycle 4). This is **EX-to-EX forwarding** (also called EX/MEM forwarding). I3's EX stage is cycle 5, which is exactly when I1's result is sitting in the MEM/WB pipeline register (I1 is in WB that same cycle). So I3 needs the value forwarded from MEM/WB into its ALU input — **MEM-to-EX forwarding**. I4's EX stage is cycle 6, one cycle after I1 has already written `$t0` back into the register file (WB happens in cycle 5, and by the conventional "write in first half, read in second half of the cycle" register-file discipline, or simply because ID for I4 is cycle 5 and WB for I1 is also cycle 5 with careful ordering, the value is available through the normal register read). I4 needs no forwarding at all — this is the case forwarding does not need to touch, because the pipeline's natural timing already delivers the correct value. This gives exactly two forwarding paths for a classic five-stage integer pipeline: 1. EX/MEM → EX — forward the ALU result computed one instruction ago. 2. MEM/WB → EX — forward the ALU result (or loaded value) computed two instructions ago, taken from the MEM/WB latch (this also covers forwarding a loaded value from a `lw` two instructions back, and it covers the case where EX/MEM forwarding was "skipped" because the intervening instruction did not need it). Two multiplexers are placed on the ALU's two input operands in the EX stage, and a small combinational block called the forwarding unit decides, every cycle, whether each ALU input should come from the register file (no hazard), from EX/MEM (forward from one instruction back), or from MEM/WB (forward from two instructions back).

Forwarding-unit logic

Let the pipeline registers carry, alongside data, the destination register number and a valid/regwrite flag for each in-flight instruction. Denote the instruction currently in EX as the consumer, and the instructions currently in MEM and WB as candidate producers. ``` // Registers available combinationally this cycle: // ID_EX.Rs, ID_EX.Rt -- source register numbers of instruction in EX // EX_MEM.RegWrite, EX_MEM.Rd -- info about instruction now in MEM // MEM_WB.RegWrite, MEM_WB.Rd -- info about instruction now in WB function FORWARDING_UNIT(ID_EX, EX_MEM, MEM_WB): ForwardA = "NONE" // selects source for ALU input A (Rs) ForwardB = "NONE" // selects source for ALU input B (Rt) // --- EX hazard: instruction in MEM (one ahead) defines a source of EX --- if EX_MEM.RegWrite and EX_MEM.Rd != 0 and EX_MEM.Rd == ID_EX.Rs: ForwardA = "FROM_EX_MEM" if EX_MEM.RegWrite and EX_MEM.Rd != 0 and EX_MEM.Rd == ID_EX.Rt: ForwardB = "FROM_EX_MEM" // --- MEM hazard: instruction in WB (two ahead) defines a source of EX, // but only if the EX/MEM case above did NOT already claim it // (EX/MEM hazard is closer in program order, so it takes priority) --- if MEM_WB.RegWrite and MEM_WB.Rd != 0 and MEM_WB.Rd == ID_EX.Rs and not (EX_MEM.RegWrite and EX_MEM.Rd != 0 and EX_MEM.Rd == ID_EX.Rs): ForwardA = "FROM_MEM_WB" if MEM_WB.RegWrite and MEM_WB.Rd != 0 and MEM_WB.Rd == ID_EX.Rt and not (EX_MEM.RegWrite and EX_MEM.Rd != 0 and EX_MEM.Rd == ID_EX.Rt): ForwardB = "FROM_MEM_WB" return ForwardA, ForwardB ``` ``` function ALU_INPUT(ForwardSelect, RegFileValue, EX_MEM_Value, MEM_WB_Value): if ForwardSelect == "FROM_EX_MEM": return EX_MEM_Value if ForwardSelect == "FROM_MEM_WB": return MEM_WB_Value return RegFileValue // "NONE": no hazard, use value read in ID ``` Two subtleties in this pseudocode are load-bearing, not stylistic:

• Checking `Rd != 0` guards against architectures (like MIPS) where register `$0` is hardwired to zero and instructions that "write" to it (or have no destination) must never trigger a forward — otherwise two unrelated instructions that both nominally target register 0 would be treated as dependent.
• Priority of EX/MEM over MEM/WB encodes program order: if both the instruction in MEM and the instruction in WB wrote the same register that EX now needs, the one in MEM is more recent (it is closer to EX in program order, having been issued later), so its value is the correct one and must win. Getting this priority backwards is a classic, silent correctness bug: the pipeline would forward a stale value from further up the pipeline even though a fresher one exists.

Space/hardware cost. Forwarding adds: two 3-to-1 multiplexers on the ALU inputs, a handful of extra wires carrying the EX/MEM and MEM/WB result values back to the EX stage, and a forwarding unit whose logic is a small, constant number of equality comparisons — $O(1)$ comparators independent of program size, since it only ever compares the (fixed, small) register-number fields of at most three pipeline registers each cycle. This is negligible next to the ALU, register file, and caches. Compare this to the without-forwarding alternative, which requires no extra hardware but forces the compiler or hardware to insert stall cycles (bubbles) whenever a RAW hazard exists — a real time cost on essentially every dependent instruction pair, since dependent arithmetic chains are extremely common in real code (loop-carried accumulations, address arithmetic, pointer chasing).

Time cost. With full EX/MEM and MEM/WB forwarding as described, a RAW hazard between an ALU instruction and a consumer that is one or two instructions later costs zero extra cycles — the pipeline still issues one instruction per cycle. The only place this specific mechanism fails is when the producer is a load instruction and the consumer immediately follows it, because a load's data does not exist until the end of its MEM stage, one cycle later than an ALU instruction's EX stage — at that point the consuming instruction's EX stage has already happened. No forwarding path can send a value backward in time; this residual case needs a single stall cycle and is handled by hazard detection plus a bubble, covered in Stalling and the Load-Use Hazard.

Correctness argument. The proof obligation is: the pipelined, forwarding-augmented machine computes the same register-file contents (and takes the same architected steps) as a hypothetical unpipelined machine that executes instructions strictly one at a time, in program order. Sketch of the argument: 1. Invariant: at the moment any instruction's EX stage consumes a source register value, that value is the most recently written value for that register among all instructions preceding it in program order (or the initial register-file value if none precede it and write it). 2. In program order, define for each register $r$ the sequence of instructions that write $r$. For any consumer instruction $j$ reading $r$, let $i$ be the closest preceding writer of $r$ (if any). 3. Because instructions enter the pipeline in program order, one per cycle (in this simple in-order issue model), the pipeline-stage distance between $i$ and $j$ is exactly $j - i$ instruction slots, which is also exactly the number of cycles separating their EX stages. 4. Case $j - i = 1$: $i$'s result is in the EX/MEM register exactly when $j$ is in EX — the forwarding unit's EX/MEM check (`EX_MEM.Rd == ID_EX.Rs/Rt`) fires and selects it. Case $j - i = 2$: $i$'s result is in the MEM/WB register exactly when $j$ is in EX — the MEM/WB check fires. Case $j - i \geq 3$: $i$ has already completed WB before $j$ reaches ID, so the ordinary register-file read in $j$'s ID stage already returns the correct, updated value; no forwarding is needed. 5. The priority rule (EX/MEM over MEM/WB) guarantees that if two preceding instructions both wrote $r$ (say at distances 1 and 2), the nearer one — which is the true most-recent writer in program order — wins, preserving the invariant even when the naive register-name match alone is ambiguous. 6. The `Rd != 0` guard prevents false hazards on architectures with a hardwired zero register, preserving the invariant that "no write" is never mistaken for "a real write." By induction over instructions in program order, the invariant holds for every instruction, so every read in the pipelined machine sees exactly the value a sequential machine would have produced — establishing that forwarding preserves the sequential-semantics contract that pipelining as a whole must not violate.

Tradeoffs, honestly. Forwarding is not free: it adds combinational-logic depth and mux delay directly into the EX stage's critical path, potentially lengthening the clock period rather than the instruction count — a classic time/complexity-of-hardware tradeoff rather than a time/instruction-count one. Real designs must balance how many forwarding paths to build (from EX/MEM, MEM/WB, and in more aggressive designs even further back, or from store-buffers, floating-point pipelines, etc.) against the wiring cost and the mux delay added to every instruction's ALU input, whether or not it needs forwarding that cycle.

Trace this instruction sequence through the pipeline, register file initially `$t1=10,$t2=20, $t4=1,$t6=2`: ``` I1: add $t0,$t1, $t2 ;$t0 = 10 + 20 = 30 I2: sub $t3,$t0, $t4 ;$t3 = 30 - 1 = 29 (needs I1's $t0, one instr. back) I3: and$t5, $t0,$t6 ; t5 = 30 & 2 = 2 (needs I1's t0, two instrs. back) I4: add $t7,$t3, $t5 ;$t7 = 29 + 2 = 31 (needs I2's $t3, two back; I3's$t5, one back) ```

Every dependent value (`$t0` used twice, `$t3` and `$t5` both used by I4 in the same cycle from different forwarding sources) reaches its consumer through a forwarding path, and the pipeline never stalls — four instructions complete in 8 cycles (versus 4 in a fully sequential 5-stage-latency machine that never overlaps, which would take 20 cycles), demonstrating forwarding's throughput benefit even under dense dependencies. Note cycle 6 in particular: I4 needs two different registers from two different distances simultaneously, and ForwardA and ForwardB are computed independently — this is exactly why the multiplexers and forwarding logic are duplicated per ALU input rather than shared.

Forwarding grew directly out of the pipelining work pioneered for early high-performance computers, where designers first confronted the fact that overlapping instruction execution creates genuine, hardware-visible ordering hazards that must be resolved without breaking the illusion of sequential execution.

Every classroom RISC-V or MIPS pipeline simulator implements exactly the EX/MEM and MEM/WB forwarding paths described here, and every real in-order embedded core — from ARM Cortex-M pipelines to simple RISC-V cores used in microcontrollers — needs equivalent bypass logic to keep single-issue throughput close to one instruction per cycle. In high-performance out-of-order superscalars (modern x86 and ARM server/desktop cores), the same idea scales up dramatically: instead of two forwarding paths, there is a bypass network connecting the outputs of many functional units (integer ALUs, multipliers, load/store units, floating-point units) to the reservation stations or issue queues of many other units, all governed by tag-matching logic that generalizes the simple register-number comparison used here. Compilers and instruction schedulers also reason about forwarding latency directly: they know which operand a just-issued instruction can supply "for free" next cycle versus which result needs extra cycles to become visible, and they reorder independent instructions to hide any residual latency — a compiler-side complement to the hardware technique, and a bridge to the broader story of hazards continued in Control Hazards.

Ask the tutor: How does the forwarding-unit design change once the pipeline supports a load-use stall alongside these two forwarding paths?