--- title: "CPU Pipeline" description: "Five stages overlap so an instruction finishes almost every cycle — until a data hazard stalls the pipeline." source: https://vizlearn.app/cs/architecture/cpu-pipeline access: premium (interactive player requires Lifetime; this doc is free) --- # CPU Pipeline A CPU pipeline splits instruction execution into five stages — fetch, decode, execute, memory, write back — and keeps a different instruction in each one, so a new instruction finishes almost every cycle. It does not make any single instruction faster: each one still takes five stages from end to end. It raises throughput, not speed. The usual analogy is a laundromat, and it survives contact with the details, so here it is. One load takes wash, dry, fold: three machines, three time slots. If you insist on carrying each load through all three before starting the next, four loads take twelve slots. If you start the second load washing the moment the first moves to the dryer, four loads take six. No machine got faster. You just stopped leaving two of them idle. A CPU does the same thing with five machines instead of three — and, like the laundromat, it stalls the instant one load needs something the previous load has not finished producing. ## How a CPU Pipeline Works Every instruction walks the same five stages in the same order. **IF** fetches the instruction word. **ID** decodes it and reads its source registers. **EX** runs the ALU. **MEM** reads or writes data memory. **WB** writes the destination register. One instruction is issued per cycle, nobody overtakes anybody, and each stage hands its work to the next on the clock edge. Two of those five stages do all the interesting damage: ID *reads* registers and WB *writes* them. Everything a pipeline gets wrong about data comes from the gap between those two. An instruction reads its operands in its second cycle, but the instruction just ahead of it writes its result in its own fifth cycle — the reader's fourth. If those two happen to be the same register, the reader is early, and being early is the same thing as being wrong. The hardware notices, and holds the reader in ID until the value is available. That hold is a **stall**, and while it lasts, EX has nothing to do — the hole travelling down the pipeline behind the held instruction is a **bubble**. A bubble is a cycle the machine paid for and got nothing back from. Count them and you have measured exactly what dependencies cost. The counting rule for a hazard-free run is worth memorizing: `n` instructions take `n + 4` cycles. Four cycles to fill the pipeline, then one instruction retires per clock. Five instructions take nine cycles instead of the twenty-five they would take one at a time, and the same pipeline running five hundred instructions takes 504 instead of 2500. The fill cost is fixed; the throughput is what scales. ## CPU Pipeline Step by Step The default run puts five instructions through a machine that can only stall — no forwarding hardware, so a value is not available until it has been written back to the register file: - `I1` — `add $t1, $s1, $s2` - `I2` — `sub $t2, $s3, $s4` - `I3` — `lw $t3, 0($s0)` - `I4` — `or $t4, $t3, $t1` - `I5` — `and $t5, $t4, $t2` The first three instructions are independent. The last two are not: `I4` reads `$t3`, which `I3` loads, and `I5` reads `$t4`, which `I4` computes. 1. **Cycle 1.** `I1` is fetched. Four stages sit empty; this is the fill. 2. **Cycle 2.** `I1` decodes and reads `$s1, $s2`. `I2` is fetched. 3. **Cycle 3.** `I1` is in EX, `I2` in ID, `I3` in IF. Three instructions, three stages, one clock. 4. **Cycle 4.** Four in flight: `I1` MEM, `I2` EX, `I3` ID, `I4` IF. 5. **Cycle 5.** The pipeline is full. `I1` in WB, `I2` in MEM, `I3` in EX, `I4` in ID, `I5` in IF — five instructions, five stages, one clock edge. This is the frame the whole idea lives in. It is also where it stops: `I4` is in ID and wants `$t3`, and `I3` is only in EX. The load has not even reached memory yet, let alone written the register. `$t3` will not be written until `I3` reaches WB in cycle 7. 6. **Cycles 6 and 7.** `I4` is held in ID, and `I5` is stuck behind it in IF. Nothing enters EX in either cycle: two bubbles. In cycle 7, `I3` writes `$t3` while `I4` reads it — the register file writes in the first half of a cycle and reads in the second, so those two overlap legally, and that overlap is worth two whole cycles. 7. **Cycle 8.** `I4` finally moves to EX with a correct `$t3`. `I5` reaches ID and immediately hits the same wall: it needs `$t4`, and `I4` will not write it until cycle 10. 8. **Cycles 9 and 10.** Two more held cycles, two more bubbles. 9. **Cycles 11 to 13.** The drain. `I5` walks EX, MEM, WB alone; the last three cycles of the run move exactly one instruction. Thirteen cycles for five instructions. Nine would have been the hazard-free ideal and twenty-five the cost with no pipelining at all, so the pipeline still won — it just handed four of its cycles back. Every one of those four is visible in the animation as an empty stage box, and every held cycle is a dashed repeat of `ID` in the instruction's row. ## Data Hazards, Stalls, and Forwarding A read-after-write hazard is not a bug in the program. `I4` is allowed to use what `I3` loaded; that is what programs do. The hazard is the pipeline's problem, and there are two ways to solve it. The dumb one is the run above: notice the conflict in ID and stop until the register file has the value. It always works, and for a back-to-back dependency it costs two cycles — the consumer is sitting in ID while the producer is still two stages short of WB. Distance is what sets the price: a producer one instruction further ahead costs one cycle, and three ahead costs nothing at all. The good one is **forwarding** (also called bypassing). The value `I3` loads exists at the end of MEM, sitting in the pipeline register between MEM and WB. Waiting for it to be copied into the register file and read back out is bureaucracy. Run a wire from that latch straight back to the EX stage's input and the consumer gets the value the cycle after it is produced. Flip the hardware selector and the same five instructions take **ten** cycles instead of thirteen. `I5`'s dependency on `I4` costs nothing at all: `I4` computes `$t4` in EX at cycle 7, and the bypass hands it to `I5`'s EX in cycle 8, one clock later, which is exactly when `I5` wanted it. ## Why Forwarding Has a Floor One stall survives. Forwarding gets the dependent program to ten cycles, not to the ideal nine, and no amount of extra wiring closes that last gap. The reason is `lw`. An ALU instruction has its result at the end of EX, and the consumer needs it at the start of the *next* EX — so the bypass runs forward in time, which wires can do. A load does not have its result until the end of MEM, one stage later, and the consumer behind it wants it in EX during that same cycle. That wire would have to run backwards in time. So on this machine — every bypass path present, memory answering in a single cycle — a load followed immediately by a use of the loaded register costs exactly one cycle. Every time. This is the **load-use hazard**, and the `lw / use pairs` scenario preset shows the floor directly: four instructions, two load-use pairs, two bubbles, ten cycles where eight would be ideal. But the stall is a scheduling problem, not a fact about loads, and the next preset proves it. `lw / use, rescheduled` runs the same four instructions — the same two loads, the same two adds, the same results — with both loads hoisted so that an unrelated instruction sits in each load's shadow. Ten cycles becomes eight. Two bubbles become none. The hardware did not change; the order did. That reordering is what a compiler's instruction scheduler does with a load-use stall: the hardware cannot look ahead to find something useful to put in the gap, so the compiler puts it there before the program ever runs. The scenario presets are the argument in compressed form. A chain where every instruction uses the previous result runs in nine cycles with forwarding and seventeen without: eight bubbles, 3.4 cycles per instruction, a pipeline behaving like the one-at-a-time machine it replaced. Same program, same instruction count, one wire's worth of difference. ## Edge Cases - **Reading in the same cycle as the write.** A consumer whose ID lands on the producer's WB does not stall. This works only because the register file is written in the first half of a cycle and read in the second — a real design choice in the MIPS pipeline, not a rounding convention. Drop it and the default run takes 15 cycles instead of 13 — each of its two stalls grows by one cycle. - **The fill and the drain.** A stage left empty because nothing has been fetched yet, or because nothing is left to fetch, is not a bubble — a bubble is an empty stage with work both ahead of it and behind it. Fill and drain are the price of having a pipeline at all, and they are the reason `n + 4`, not `n`, is the floor. For a five-instruction program that overhead is most of the run; for a loop with a million iterations it rounds to nothing. - **A dependency that is far enough away.** `I4` also reads `$t1`, written by `I1` — three instructions earlier. It never causes a stall, because by the time `I4` reaches ID, `I1` has already reached WB. Distance is the cheapest hazard fix there is. - **An independent program.** Give the same five opcodes operands that never collide and the run takes nine cycles with or without forwarding hardware, and the bypass paths sit unused. Forwarding does not speed up code; it stops the machine from punishing code that has dependencies. - **Two producers, one consumer.** `I5` reads `$t4` and `$t2`. The hardware waits for the later of the two, so a stall is only as long as the worst dependency; the others are free. ## Common Mistakes - **Believing pipelining makes instructions faster.** Every instruction still passes through all five stages, and a stall makes it take longer: in the default run `I5` is fetched in cycle 5 and writes back in cycle 13, nine cycles later. Timing a single instruction on a pipelined machine measures nothing useful. Throughput is the metric, and it only shows up over many instructions. - **Counting a stall as one lost cycle.** Without forwarding, a back-to-back dependency costs two, because the consumer has to wait for WB and it is two stages away from it. Reason from where the value actually appears, not from "it stalled once". - **Forwarding a load out of the EX/MEM latch.** That latch holds what the ALU computed for a `lw` — the memory *address*, not the loaded word. A forwarding unit that treats loads like ALU ops delivers a plausible-looking wrong number with no stall and no warning. - **Assuming a stall only delays the stalled instruction.** Everything behind it stops too, because an in-order pipeline cannot let a later instruction overtake an earlier one. One stalled instruction holds the whole front of the machine. - **Reading a repeated stage in the diagram as progress.** Three `ID` boxes in a row is one decode that took three cycles, not three decodes. The dashed border is the tell. ## A Note on Simplification This lesson animates the textbook 5-stage in-order pipeline — the MIPS model used to teach the idea — and it leaves out most of what a shipping CPU does. There are no branches or jumps here, so control hazards (fetching instructions after a branch before knowing whether it is taken) never appear; that is the Branch Prediction lesson's subject. Memory always answers in one cycle, so cache misses never stall anything. One instruction issues per cycle, in program order, which rules out the superscalar issue and out-of-order execution that most high-performance cores rely on. Real pipelines are also deeper — often fourteen to twenty stages — which can make a hazard more expensive where the extra stages widen the gap between the stage that needs a value or branch outcome and the stage that produces it — and is precisely why branch prediction and aggressive forwarding networks are worth their silicon. Treat this as the model that makes those techniques make sense, not as a description of the chip you are reading this on.