Pipeline Hazards

A hazard is a situation in which the next instruction in a pipeline cannot execute in its planned clock cycle without giving a wrong result. The pipeline must then either wait (a stall, also called a bubble) or use extra hardware that removes the conflict. Hazards are the reason a real pipeline has a CPI above 1.

There are three kinds. A structural hazard is a conflict over hardware: two instructions need the same unit in the same cycle. A data hazard is a conflict over a value: an instruction needs a result that an earlier instruction has not yet produced. A control hazard is a conflict over the instruction stream: the pipeline does not yet know which instruction follows a branch. Beyond the ideal formula of Instruction Pipelining, the task is to count the stall cycles these hazards cause, with or without forwarding, and to turn the count into CPI, time or speedup.

Pipeline convention used in all Gate CS Mastery notes. Unless a question says otherwise: five stages IF, ID, EX, MEM, WB, one cycle each; source registers are read in ID; an ALU result is computed in EX and a loaded value is available at the end of MEM; results are written in WB. The register file is written in the first half of a cycle and read in the second half (a split-cycle register file), so an instruction in ID can read a value written by WB in the same cycle. Separate instruction and data memories (or caches), so IF and MEM never conflict. A stalled instruction waits in ID and the instructions behind it wait too.

Counting convention. "Stall cycles" are the cycles added to the ideal count $k + n - 1$. Total cycles $= k + n - 1 +$ stall cycles. CPI over a long program $= 1 +$ stall cycles per instruction.

Let instruction $i$ come before instruction $j$ in program order.

WAR and WAW are name dependences: no value flows between the instructions, and renaming the register removes them. They become hazards in pipelines where instructions can complete out of order (for example a long floating-point unit beside a short integer path), or where some instruction writes early and another reads late. RAR (read after read) is not a dependence at all.

A result exists inside the pipeline long before WB writes it. Forwarding adds paths and multiplexers that take the value from the pipeline registers and feed it straight to the ALU inputs.

Load-use hazard. A load produces its value only at the end of MEM. The next instruction wants it at the start of its EX, which is the same cycle. Forwarding cannot send a value backward in time, so a load followed immediately by an instruction needing its value at the start of EX costs one stall cycle even with full forwarding. Store-data use is exempt when MEM/WB-to-MEM forwarding is present; a store-address dependency still needs the EX-stage value. The hardware that detects this and inserts the bubble is the hazard detection unit; the forwarding multiplexers are controlled by the forwarding unit.

Let the distance be $j - i$: 1 for adjacent instructions, 2 if one instruction sits between them, and so on. The table gives the stall cycles for one RAW dependence on an ALU result or a load result in the pipeline above.

The table counts stalls for one isolated dependence. In a sequence, an earlier stall pushes later instructions back and can absorb a later dependence. Always trace the sequence instead of adding table entries blindly (Example 1 shows both effects).

A structural hazard appears when the hardware cannot support every combination of instructions in flight.

A branch decides the next PC only when its condition and target are known. Instructions fetched after the branch in the meantime may be on the wrong path.

Filling a delay slot. The compiler can take the slot instruction from three places; each is legal only under its own condition.

The first source is the best because the slot does useful work whatever the outcome; the other two help only on one outcome and need the "harmless on the other path" check.

Figure 1 compares one RAW dependence on an ALU result without and with forwarding, and the load-use case.

Figure 2 shows a taken branch resolved in EX under predict not taken.

The procedure below counts the cycles of a straight-line sequence in the pipeline above, one instruction at a time. Instructions are numbered from 1; EXstart[j] is the cycle in which instruction $j$ starts EX.

Without split-cycle registers, replace EXstart[p]+3 by EXstart[p]+4. With a word-RAM register map supporting constant-time lookup/update, at most $s\ge1$ source operands and a bounded number of destinations per instruction, work is $O(ns)$; storage is $O(n+R)$ for EXstart and writers of the $R$ registers encountered. An absent map entry means no previous writer, avoiding a full register-universe initialization cost. Literal backward searches instead take $O(n^2s)$ worst case. Branches add their penalty to the next correct-path fetch; structural conflicts add a cycle per conflicting use.

CPI with stalls. If a fraction $f_h$ of instructions suffers hazard $h$ with penalty $p_h$ cycles,

Branches. With branch frequency $b$, taken fraction $t$ and penalty $p$:

Speedup with stalls. For balanced stages ($t_{np} = k\,t_p$) and many instructions,

With unequal stages, use $S = t_{np} / (\text{CPI} \cdot t_p)$.

Why the table is right. With forwarding, an ALU producer that starts EX in cycle $c$ has its result in the EX/MEM register at the end of $c$, so the consumer can start EX in $c + 1$: no stall at distance 1. A load's value is in MEM/WB at the end of $c+1$, so an EX-stage consumer starts EX at $c+2$: one stall at distance 1. For store data used only in MEM, the listed MEM/WB-to-MEM bypass permits EX at $c+1$ and MEM at $c+2$, with no stall. Thus LW R1,0(R2); SW R1,4(R2) has EX cycles 3 and 4 and completes the five-stage timing envelope in 6 cycles (the store's WB slot does no register write). Without forwarding, the producer writes in WB in cycle $c + 2$; with a split cycle the consumer reads in ID in that cycle and starts EX in $c + 3$, which is 2 cycles late at distance 1. Without a split cycle it reads one cycle later still.

The I3 and I4 dependences on R1 cost nothing in every case: the stall in front of them already delayed them.

MUL R1, R2, R3 spends 3 cycles in EX; ADD R4, R1, R5 and SUB R6, R7, R8 spend 1. With forwarding, MUL occupies EX in cycles 3, 4 and 5, so ADD starts EX in cycle 6 (2 stalls) and SUB in cycle 7. The three instructions finish in cycle 9 instead of 7. Even an independent instruction behind ADD is delayed, because EX is busy and the pipeline is in order.

20% of instructions are branches and 65% of them are taken.

With balanced stages and $k = 5$, the speedups over the non-pipelined processor are $5/1.40 \approx 3.57$, $5/1.26 \approx 3.97$, $5/1.13 \approx 4.42$ and $5/1.06 \approx 4.72$.

With one memory shared by IF and MEM, each load/store blocks a simultaneous fetch, if one is actually requested. For LW followed by four independent ALU instructions, LW is in MEM in cycle 4, so the fourth instruction's fetch moves from cycle 4 to cycle 5 and the five instructions take 10 cycles instead of 9. For a long otherwise-unstalled stream, CPI is approximately 1 plus the load/store fraction: 35% gives 1.35. Trace finite sequences and overlapping stalls explicitly.

Take every ordered pair $i < j$; for a read, the producer is the latest earlier instruction that writes that register.

Timing in the standard pipeline: with full forwarding all three distance-1 RAW pairs are ALU to ALU, so there is no stall and the sequence takes $5 + 4 - 1 = 8$ cycles. Without forwarding (split-cycle register file), I2, I3 and I4 each wait 2 cycles for the instruction just ahead: 6 stalls, 14 cycles. The I2 to I4 pair on R4 costs nothing, because I4 is already behind I3. The WAR and WAW pairs cost nothing in either case.

Suppose a divide unit spends 6 cycles in EX beside a 1-cycle integer ALU, and the pipeline lets a short instruction finish before a long one ahead of it (out-of-order completion).

I2 writes R1 in cycle 6 and I1 overwrites it in cycle 10, so after both have finished R1 holds the DIV result although ADD comes later in program order: a WAW hazard. The hardware must hold I2's write until after I1's (or rename R1). A WAR hazard needs the reverse situation, a later instruction writing a register before an earlier one has read it; that can happen only when operand reads are delayed (for example, an instruction waiting for a busy unit reads its registers when it finally starts). In the standard in-order pipeline neither situation arises, which is why only RAW stalls it.