--- title: "Data Hazards: Stalling and Forwarding" module: Pipelining moduleNumber: 5 lessonNumber: 3 order: 503 summary: > Overlapping instructions collide when a later one needs a value an earlier one has not finished computing: a read-after-write data hazard. We map exactly which instruction distances are dangerous, fix hazards the slow way by stalling (three bubbles), then the fast way by forwarding from five distinct sources into Decode, in a priority order that sequential semantics forces. Forwarding handles almost everything; the load-use hazard still needs exactly one stall. topics: [Pipelining] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §4.5 Pipelined Y86-64 Implementations" --- PIPE keeps five instructions in flight, and that overlap creates its first hard problem. In SEQ each instruction finished (wrote its result into the register file) before the next one read its operands. In PIPE the next instruction reads its operands in Decode while the earlier one is still grinding through Execute or Memory, _before_ it has written anything back. If the later instruction needs the value the earlier one is producing, it reads a **stale** register. This is a **data hazard**, and handling it is what separates a pipeline that is fast from one that is merely wrong. ## The read-after-write hazard Consider two Y86-64 instructions where the second uses what the first produces. ```asm [raw.ys] irmovq $10, %rax # rax <- 10 addq %rax, %rbx # rbx <- rbx + rax (reads rax) ``` The `addq` reads `%rax` in its Decode stage. But `irmovq` does not write `%rax` into the register file until its own write-back stage, several cycles later. Lay the two on the pipeline diagram and the conflict is geometric: the Decode that _reads_ happens earlier in time than the write-back that _writes_. > **Definition (Data hazard).** A situation where an instruction depends on the > result of an earlier instruction still in the pipeline, so that reading the > source naively would return the value from _before_ the earlier instruction's > update. The Y86-64 form is **read-after-write** (RAW): a register is read before > the prior write to it has completed. $$ % caption: The RAW hazard. addq reads rax in its Decode (cycle 3), but irmovq does % caption: not write rax back until cycle 5. The arrow points from the producing % caption: write-back back to the consuming Decode — the value is needed two cycles % caption: before it exists in the register file. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % cycle headers 1..6 \foreach \c in {1,...,6} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; % irmovq: F D E M W in cycles 1..5 \node[anchor=east] at (-0.15,0) {\texttt{irmovq}}; \foreach \c/\s in {1/F, 2/D, 3/E, 4/M, 5/W} \node[cell, fill=acc!8] (a\c) at (\c*1.0-0.5,0) {\s}; % addq: F D E M W in cycles 2..6 \node[anchor=east] at (-0.15,-0.85) {\texttt{addq}}; \foreach \c/\s in {2/F, 3/D, 4/E, 5/M, 6/W} \node[cell, fill=acc!8] (b\c) at (\c*1.0-0.5,-0.85) {\s}; % hazard arrow: irmovq W (cycle5, top row) back to addq D (cycle3, bottom row) \draw[acc, thick, ->] (a5.south) .. controls (3.0,-1.6) and (3.0,-1.6) .. (b3.south); \node[anchor=north, text=acc] at (3.0,-1.7) {\scriptsize needs \texttt{rax} here, written there}; \end{tikzpicture} $$ The `addq` reads `%rax` in cycle 3 but `irmovq` writes it in cycle 5: the value is needed two cycles before the register file holds it. Something must give. ## Which pairs are dangerous: the hazard taxonomy Before fixing anything, map the problem's exact extent. Two questions decide whether a pair of instructions collides: _who_ writes and reads registers, and _how far apart_ they sit. The writers are every instruction with a destination: `OPq`, `rrmovq`, `irmovq`, and `cmovXX` write a computed value through register port E; `mrmovq` and `popq` write a loaded value through port M; and `pushq`, `popq`, `call`, `ret` update `%rsp` through port E. The readers are every instruction that consumes register values in Decode: `OPq`, `rrmovq`, `rmmovq`, `mrmovq`, `pushq` read `rA` and/or `rB`, and the stack instructions read `%rsp`. Condition codes create no hazard at all: they are written in Execute and read in Execute, so a jump following an `OPq` always sees fresh codes one cycle later. The register file is the only point of conflict. Distance is the sharper axis. The register file is written on the rising clock edge that _ends_ the producer's write-back cycle, so a consumer's Decode read is safe only if it happens in a strictly later cycle. Count it out: a producer fetched in cycle 1 writes back in cycle 5; a consumer at distance $d$ decodes in cycle $d + 2$. The read is safe when $d + 2 > 5$, that is $d \geq 4$. Distances 1 through 3 are all hazardous, and each one leaves the needed value in a different place: | Distance | Producer's position at consumer's Decode | Where the value is | | --- | --- | --- | | 1 | Execute | coming out of the ALU this cycle | | 2 | Memory | in the M register (or coming out of data memory) | | 3 | Write-back | in the W register, one edge from the register file | | $\geq 4$ | completed | in the register file — no hazard | The table is the lesson's skeleton: every fix must cover exactly rows 1-3, and row 3 is a genuine hazard even though producer and consumer overlap in only one cycle — a Decode read _concurrent_ with the write-back still sees the old value, because the write lands on the edge that ends the cycle. ## Fix 1: stall (inject bubbles) The blunt fix is to make the pipeline **wait**. Detection is cheap: the decode logic compares its source IDs `d_srcA`, `d_srcB` against the destination IDs of the instructions in Execute, Memory, and Write-back. On a match, the control logic holds the F and D registers in place (the consumer re-reads the register file each cycle) and injects a **bubble** into E so the stages ahead have harmless work. > **Definition (Stall and bubble).** To **stall** is to hold an instruction (and > everything behind it) in place for one or more cycles instead of advancing it. A > **bubble** is the no-op the stall injects into the stage ahead, so that stage has > something benign to execute while the held instruction waits. $$ % caption: Stalling to fix the hazard. addq is held in Decode through cycles 3-6, % caption: injecting bubbles into Execute in cycles 4, 5, 6. irmovq writes rax at % caption: the clock edge ending cycle 5, so cycle 6 is the first Decode that reads % caption: the new value. Three bubbles, three cycles lost. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,9} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; % irmovq normal \node[anchor=east] at (-0.15,0) {\texttt{irmovq}}; \foreach \c/\s in {1/F, 2/D, 3/E, 4/M, 5/W} \node[cell, fill=acc!8] at (\c*1.0-0.5,0) {\s}; % addq: F(2), held in D for 3,4,5,6, then E(7) M(8) W(9) \node[anchor=east] at (-0.15,-0.85) {\texttt{addq}}; \foreach \c/\s in {2/F, 3/D, 4/D, 5/D, 6/D, 7/E, 8/M, 9/W} \node[cell, fill=acc!8] at (\c*1.0-0.5,-0.85) {\s}; % bubbles entering Execute while addq is stalled (cycles 4,5,6) \node[anchor=east] at (-0.15,-1.7) {bubbles}; \foreach \c in {4,5,6} \node[cell, fill=black!8] at (\c*1.0-0.5,-1.7) {bb}; \end{tikzpicture} $$ Count the cost carefully, because the naive count is off by one. `irmovq` writes back in cycle 5, but a cycle-5 Decode still reads stale data; the first good read is cycle 6. So `addq` sits in Decode for cycles 3 through 6 and **three** bubbles flow through the pipeline, the same effect as the compiler inserting three `nop`s between the two instructions. A third-of-the-pipeline penalty for one dependency, and adjacent dependent instructions are the most common pattern in compiled code. Stalling is always correct, but as the only tool it would erase most of pipelining's gain. We can do far better by noticing the value is not actually missing; it is just in the wrong place. ## Fix 2: forward (bypass) The value `addq` needs already _exists_ inside the processor by cycle 3: the ALU computes it during that very cycle. It just has not made the round trip through the register file. **Forwarding** (bypassing) adds wires that route such values straight back to Decode, skipping the register file entirely. > **Definition (Forwarding / bypassing).** Routing a result from a later pipeline > stage — a stage output or a pipeline-register field — directly back to the > Decode stage of a dependent instruction, so the dependent instruction uses the > freshly computed value the same cycle it needs it, without waiting for the > producer's write-back. $$ % caption: Forwarding the value. Instead of stalling, the result irmovq computes in % caption: Execute is routed straight into addq's Decode the same cycle (the acc % caption: arrow). No bubbles; full throughput. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,6} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; \node[anchor=east] at (-0.15,0) {\texttt{irmovq}}; \foreach \c/\s in {1/F, 2/D, 3/E, 4/M, 5/W} \node[cell, fill=acc!8] (a\c) at (\c*1.0-0.5,0) {\s}; \node[anchor=east] at (-0.15,-0.85) {\texttt{addq}}; \foreach \c/\s in {2/F, 3/D, 4/E, 5/M, 6/W} \node[cell, fill=acc!8] (b\c) at (\c*1.0-0.5,-0.85) {\s}; % forward arrow: from irmovq E (cycle3 top) down to addq D (cycle3 bottom) \draw[acc, thick, ->] (a3.south) -- (b3.north); \node[anchor=north, text=acc] at (2.5,-1.3) {\scriptsize \texttt{forward}}; \end{tikzpicture} $$ Timing makes this legal: Decode only has to deliver `valA`/`valB` by the _end_ of its cycle, when the E register latches, and the ALU output settles well before that. Nothing about the clock changes; the value simply takes a wire instead of a detour. One path is not enough, though. The taxonomy said the needed value can be in three different places, and values come in two kinds (computed `valE`, loaded `valM`), so PIPE wires **five forwarding sources** into Decode: | Source | What it is | Covers distance | | --- | --- | --- | | `e_valE` | ALU output, computed in Execute this cycle | 1 | | `m_valM` | data-memory output, read in Memory this cycle | 2 (loads) | | `M_valE` | pending port-E write in the M register | 2 | | `W_valM` | pending port-M write in the W register | 3 (loads) | | `W_valE` | pending port-E write in the W register | 3 | $$ % caption: The five forwarding sources feeding Decode's operand selection. The % caption: muxes compare the decode-stage source IDs against each pending % caption: destination ID, top first; if nothing matches, the register-file read % caption: is used. Top-to-bottom order is the priority order. \begin{tikzpicture}[font=\footnotesize,>=stealth, src/.style={draw, fill=acc!8, minimum width=17mm, minimum height=6.5mm, inner sep=1pt}, mux/.style={draw, fill=acc!8, minimum width=15mm, minimum height=14mm, inner sep=2pt, align=center}] \definecolor{acc}{HTML}{2348F2} \node[mux] (m) at (0,-1.25) {Sel+Fwd A\\Fwd B}; \draw[acc, thick, ->] (m.west) -- ++(-1.3,0) node[anchor=east, text=acc] {valA, valB}; % sources, top to bottom = priority order \node[src] (s1) at (4.6,0.8) {e\_valE}; \node[anchor=west, black] at (5.7,0.8) {ALU output (Execute)}; \node[src] (s2) at (4.6,0.0) {m\_valM}; \node[anchor=west, black] at (5.7,0.0) {memory output (Memory)}; \node[src] (s3) at (4.6,-0.8) {M\_valE}; \node[anchor=west, black] at (5.7,-0.8) {M register}; \node[src] (s4) at (4.6,-1.6) {W\_valM}; \node[anchor=west, black] at (5.7,-1.6) {W register}; \node[src] (s5) at (4.6,-2.4) {W\_valE}; \node[anchor=west, black] at (5.7,-2.4) {W register}; \node[src] (s6) at (4.6,-3.2) {d\_rvalA, d\_rvalB}; \node[anchor=west, black] at (5.7,-3.2) {\texttt{register-file} read}; % fan-in arrows, order preserved so no crossings \draw[->] (s1.west) -- (m.20); \draw[->] (s2.west) -- (m.10); \draw[->] (s3.west) -- (m.0); \draw[->] (s4.west) -- (m.350); \draw[->] (s5.west) -- (m.340); \draw[->] (s6.west) -- (m.330); \node[anchor=south, text=acc] at (4.6,1.25) {highest priorit\/y}; \end{tikzpicture} $$ Decode's two selection blocks ("Sel+Fwd A" for `valA`, "Fwd B" for `valB`) compare `d_srcA` and `d_srcB` against each source's destination ID and pick the first match; only if nothing matches do they fall through to the register-file read. In HCL, for `valA`: ```c [d_valA.hcl] word d_valA = [ D_icode in { ICALL, IJXX } : D_valP; # incremented PC, merged into valA d_srcA == e_dstE : e_valE; # forward valE from execute d_srcA == M_dstM : m_valM; # forward valM from memory d_srcA == M_dstE : M_valE; # forward valE from memory d_srcA == W_dstM : W_valM; # forward valM from write back d_srcA == W_dstE : W_valE; # forward valE from write back 1 : d_rvalA; # use value read from register file ]; ``` With these five paths, every RAW hazard in the taxonomy is covered with **zero** stall cycles — except one case, coming below. ### A worked trace: three distances at once One program can carry all three hazard distances against a single producer, and tracing it shows each forwarding source firing in turn. Here `irmovq` writes `%rax` in cycle 5, and three later instructions each read it at a different distance: ```asm [distances.ys] irmovq $7, %rax # I1: writes rax (write-back in cycle 5) addq %rax, %rbx # I2: distance 1 subq %rax, %rcx # I3: distance 2 andq %rax, %rdx # I4: distance 3 ``` $$ % caption: One producer, three consumers at distances 1, 2, 3. When each consumer % caption: decodes, irmovq's result rax=7 sits in a different place: Execute output % caption: for I2, the M register for I3, the W register for I4. Each reads its % caption: value by forwarding, no stalls. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,8} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; \foreach \i/\y/\lab in {0/0/{I1 irmo\/vq}, 1/-0.9/{I2 addq}, 2/-1.8/{I3 subq}, 3/-2.7/{I4 andq}}{ \node[anchor=east] at (-0.15,\y) {\scriptsize \lab}; \foreach \s/\o in {F/0, D/1, E/2, M/3, W/4} \node[cell, fill=acc!8] at (\i*1.0+\o*1.0+0.5,\y) {\s}; } % forwarding arrows routed in the gaps between columns/rows (never through a cell) % row centers: I1=0, I2=-0.9, I3=-1.8, I4=-2.7; cells span +-0.35 vertically, +-0.45 horiz % I2 decodes cycle 3 <- I1 in E (e_valE): short vertical, same column, clear gap \draw[acc, thick, ->] (2.5,-0.36) -- (2.5,-0.54); \node[anchor=west, text=acc] at (0.2,-3.35) {\scriptsize I2 gets e\_valE (I1 in E)}; % I3 decodes cycle 4 <- I1 in M (x=3.5): out M-bottom, left to column-gap x=3.0, down, into D-top \draw[acc, thick, ->] (3.5,-0.36) -- (3.5,-0.45) -- (3.0,-0.45) -- (3.0,-1.45) -- (3.5,-1.45) -- (3.5,-1.54); \node[anchor=west, text=acc] at (3.5,-3.35) {\scriptsize I3 gets M\_valE (I1 in M)}; % I4 decodes cycle 5 <- I1 in W (x=4.5): out W-bottom, left to column-gap x=4.0, down, into D-top \draw[acc, thick, ->] (4.5,-0.36) -- (4.5,-0.45) -- (4.0,-0.45) -- (4.0,-2.35) -- (4.5,-2.35) -- (4.5,-2.44); \node[anchor=west, text=acc] at (6.85,-3.35) {\scriptsize I4 gets W\_valE (I1 in W)}; \end{tikzpicture} $$ Walk the cycles. I2 decodes in cycle 3, when I1 is in Execute; the ALU output `e_valE` forwards straight down. I3 decodes in cycle 4, when I1 has moved to Memory; its result now sits in the M register as `M_valE`. I4 decodes in cycle 5, the same cycle I1 writes back; the value is in the W register as `W_valE`, and forwarding beats the register-file read (which would still be stale until the edge ends the cycle). Three consumers, three different sources, and the pipeline never stalls — every value was already inside the machine, just never in the register file yet. ## Why the priority order matters The HCL cases are tested top to bottom, and that order matters. Several instructions ahead of the consumer may all be writing the _same_ register, one pending in each stage: ```asm [priority.ys] irmovq $10, %rdx # older write to rdx irmovq $3, %rdx # newer write to rdx rrmovq %rdx, %rax # must read 3, not 10 ``` When `rrmovq` decodes in cycle 4, _two_ pending writes to `%rdx` are in flight: the first `irmovq` is in Memory holding 10, the second in Execute computing 3. Sequential semantics is unambiguous (executed one at a time, `rrmovq` reads the _most recent_ write, 3), so the forwarding logic must prefer the source from the **earliest pipeline stage**, which holds the latest instruction in program order. Execute beats Memory beats Write-back. $$ % caption: Forwarding priority. In cycle 4 both pending writes to rdx are in % caption: flight: 10 in Memory (dashed, older, must lose) and 3 in Execute % caption: (solid, newest, must win). Preferring the earliest stage preserves % caption: sequential semantics. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,7} \node at (\c*1.0-0.5,0.75) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.75) {\scriptsize cycle}; \node[anchor=east] at (-0.15,0) {\texttt{irmovq \char36 10,\%rdx}}; \foreach \c/\s in {1/F, 2/D, 3/E, 4/M, 5/W} \node[cell, fill=acc!8] (a\c) at (\c*1.0-0.5,0) {\s}; \node[anchor=east] at (-0.15,-1.1) {\texttt{irmovq \char36 3,\%rdx}}; \foreach \c/\s in {2/F, 3/D, 4/E, 5/M, 6/W} \node[cell, fill=acc!8] (b\c) at (\c*1.0-0.5,-1.1) {\s}; \node[anchor=east] at (-0.15,-2.2) {\texttt{rrmovq \%rdx,\%rax}}; \foreach \c/\s in {3/F, 4/D, 5/E, 6/M, 7/W} \node[cell, fill=acc!8] (c\c) at (\c*1.0-0.5,-2.2) {\s}; % winning forward: E (cycle 4, middle row) straight down to D below \draw[acc, thick, ->] (b4.south) -- (c4.north); % losing forward: M (cycle 4, top row), threaded through the column gap, dashed \draw[black, dashed, ->] (a4.south) .. controls (4.0,-0.9) and (4.1,-1.7) .. (3.8,-1.83); \node[anchor=north, text=acc] at (3.0,-2.75) {\scriptsize solid: 3 from Execute wins \enspace / \enspace dashed: 10 from Memory loses}; \end{tikzpicture} $$ Swap any two cases in the HCL and some program breaks. If Memory were checked before Execute, `rrmovq` here would read 10, a value the ISA says was already overwritten. The within-stage order matters too: `m_valM` before `M_valE` because `popq %rsp` writes both ports at once and the ISA defines its result as the _loaded_ value. Forwarding priority is one of those details that simulation rarely catches (the buggy order runs most programs correctly) and systematic analysis catches immediately — reason it out per stage, oldest to newest. ## The load-use hazard: forwarding's one gap Forwarding works whenever the needed value has _been computed_ by the time the consumer's Decode ends. There is exactly one case where it has not: a **load** followed immediately by an instruction that uses the loaded value. ```asm [loaduse.ys] mrmovq 0(%rcx), %rax # rax <- M[rcx] (value read in Memory stage) addq %rax, %rbx # uses rax one instruction later ``` The loaded value does not exist until `mrmovq` finishes its **Memory** stage. But `addq` reaches Decode one cycle earlier, when `mrmovq` is only in Execute and the value is not yet read. Forwarding cannot send a value backward in time. The diagram shows the path that _would_ be needed pointing the wrong way: $$ % caption: The load-use hazard. mrmovq's value is read in its Memory stage (cycle 4), % caption: but addq needs it in Decode (cycle 3) — one cycle too early. Forwarding % caption: from M to D would have to run backward in time, which is impossible. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,6} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; \node[anchor=east] at (-0.15,0) {\texttt{mrmovq}}; \foreach \c/\s in {1/F, 2/D, 3/E, 4/M, 5/W} \node[cell, fill=acc!8] (a\c) at (\c*1.0-0.5,0) {\s}; \node[anchor=east] at (-0.15,-0.85) {\texttt{addq}}; \foreach \c/\s in {2/F, 3/D, 4/E, 5/M, 6/W} \node[cell, fill=acc!8] (b\c) at (\c*1.0-0.5,-0.85) {\s}; % impossible backward arrow from mrmovq M (cycle4 top) to addq D (cycle3 bottom) \draw[acc, thick, dashed, ->] (a4.south) -- (b3.north); \node[anchor=north, text=acc] at (3.0,-1.3) {\scriptsize \texttt{backward in time}}; \end{tikzpicture} $$ The fix is a hybrid called a **load interlock**: stall the consumer for exactly one cycle, then forward. The control logic detects the pattern (a load in Execute whose `E_dstM` matches `d_srcA` or `d_srcB`), holds F and D, and injects a single bubble into E. Now `addq` decodes in cycle 4, when `mrmovq` is in its Memory stage and `m_valM` is available to forward. One stall, not three: the minimum the dependency forces. $$ % caption: Load-use fix: stall addq one cycle (a single bubble into Execute), so % caption: its Decode slides to cycle 4, exactly when mrmovq's Memory stage has the % caption: loaded value, which then forwards as m valM. One bubble is the whole cost. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,7} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; \node[anchor=east] at (-0.15,0) {\texttt{mrmovq}}; \foreach \c/\s in {1/F, 2/D, 3/E, 4/M, 5/W} \node[cell, fill=acc!8] (a\c) at (\c*1.0-0.5,0) {\s}; % addq: F(2), D held 3 and 4, then E(5) M(6) W(7) \node[anchor=east] at (-0.15,-0.85) {\texttt{addq}}; \foreach \c/\s in {2/F, 3/D, 4/D, 5/E, 6/M, 7/W} \node[cell, fill=acc!8] (b\c) at (\c*1.0-0.5,-0.85) {\s}; % one bubble into Execute at cycle 4 \node[anchor=east] at (-0.15,-1.7) {bubble}; \node[cell, fill=black!8] at (4*1.0-0.5,-1.7) {bb}; % forward from mrmovq M (cycle4 top) to addq D (cycle4 bottom) \draw[acc, thick, ->] (a4.south) -- (b4.north); \end{tikzpicture} $$ Load interlocks plus forwarding handle _every_ data hazard PIPE can encounter, and only the interlock costs anything. This single unavoidable stall is why compilers schedule a useful, independent instruction into the slot right after a load when they can, turning the mandatory bubble into real work. ## Executing around the hazard PIPE's answer to a load-use hazard is to stall: the consumer waits one cycle in Decode while the whole pipeline behind it freezes. That is correct but blunt — the frozen cycle is wasted even if there is other, independent work the processor could have done meanwhile. Out-of-order (dynamically scheduled) processors do not waste it. Instead of stalling the consumer _and everything behind it_, they let the stalled instruction step aside and run any later instruction whose operands are ready. The mechanism is **Tomasulo's algorithm** (Tomasulo, 1967, _IBM Journal of Research and Development_), first shipped in the IBM System/360 Model 91's floating-point unit and standard in performance cores today. Decoded instructions wait in **reservation stations** rather than a rigid pipeline slot; each station holds an instruction and tags for the operands it still needs. When a functional unit produces a result, it broadcasts the value with its tag on a **common data bus**, and every waiting station listening for that tag grabs it at once — a forwarding network generalized from PIPE's five fixed wires to a fully associative match. An instruction fires the cycle its last operand arrives, regardless of program order, so a load miss no longer freezes the machine: independent instructions sail past the waiting consumer and keep the execution units busy. The load-use hazard shows the contrast. In PIPE, `addq %rax, %rbx` after a load of `%rax` costs one guaranteed bubble. In an out-of-order core, if the instruction stream contains any independent work — and compiled code usually does — that work executes during the load's latency, and the `addq` fires the moment the loaded value broadcasts, with no idle cycle at all. The catch is enormous hardware cost: reservation stations, the reorder buffer that puts results back in program order, the register renaming from the previous lesson, and the associative wakeup logic. This is why the trade sits where it does — PIPE's in-order stall is a few gates, and dynamic scheduling is a large fraction of a modern core's area and power (Hennessy and Patterson, _Computer Architecture: A Quantitative Approach_, ch. 3). The principle, though, is a direct descendant of forwarding: route each value to whatever needs it the instant it exists. > **Takeaway.** Overlap creates **read-after-write data hazards** at distances 1, > 2, and 3; from distance 4 the register file itself is safe. **Stalling** fixes > any hazard by holding the consumer in Decode and bubbling Execute, but an > adjacent dependency costs **three** bubbles. **Forwarding** routes the value > from wherever it lives — five sources: `e_valE`, `m_valM`, `M_valE`, `W_valM`, > `W_valE` — straight into Decode for zero penalty, checked in that order so the > **newest** pending write wins, as sequential semantics demands. The one gap is > the **load-use hazard**: the loaded value does not exist until Memory, so a > load interlock stalls **exactly one cycle**, then forwards. Data hazards are about values flowing _forward_. The [next lesson](/computer-architecture/pipelining/control-hazards-and-branch-prediction) turns to a different break in the flow: not knowing which instruction comes next.