Pipelining: The Assembly-Line Idea

The idle machine

In the datapath rung you built a processor that runs one whole instruction, start to finish, before touching the next. We saw it work in five logical phases: fetch the instruction, decode it and read registers, do the arithmetic, reach memory, write the result back. The trouble — the single-cycle limitation we ended that rung on — is that only one phase is busy at any instant. While the arithmetic unit is computing, the instruction memory, the register read ports, and the data memory all sit idle, drumming their fingers. You paid for all five pieces of hardware and you are using one-fifth of them.

Pipelining is the fix, and the picture to hold in your head is a laundromat. You have four loads to do, and each load must wash, then dry, then fold. The naive way is to take one load all the way through — wash, dry, fold — and only then start the next. But the moment your first load leaves the washer and moves to the dryer, the washer is free. So you start washing load two right then, while load one dries. Soon all three machines run at once on three different loads, and four loads finish in roughly the time the naive way needs for two. That is the whole idea: don't make any one load finish faster; just stop the machines from sitting idle.

Throughput, not latency

Look closely at the laundry and you'll see the crucial, easily-missed truth. Any single load still takes wash-plus-dry-plus-fold; pipelining did not shorten that one bit. What changed is how often a finished load drops out the end. Once the line is full, one load completes every wash-time, not every wash-plus-dry-plus-fold. That rate of completion is throughput, and it is what pipelining multiplies. The time for one item to travel the whole line — its latency — is untouched, and may even creep up slightly.

There is a second hidden cost the laundry analogy quietly assumes away: all three machines must run for the same length of time, or the slowest one sets the pace. If drying takes twice as long as washing, the washer finishes early and waits anyway. In a processor the stages are rarely perfectly balanced, so the clock period is set by the slowest stage, not the average. Pipelining wins most when you can chop the work into stages of roughly equal length — and chasing that balance is a big part of why architects pick five stages, or fourteen, or thirty.

Five stages and the latches between them

The classic textbook pipeline cuts an instruction's life into the same five phases your single-cycle datapath already had — this is the five-stage pipeline, and the next guide builds it in detail. The phases get the abbreviations IF (instruction fetch), ID (instruction decode and register read), EX (execute in the ALU), MEM (access data memory), and WB (write back to the register file). In a full pipeline, five different instructions occupy these five stages at once — one being fetched while another executes while a third writes back.

cycle:    1    2    3    4    5    6    7    8
add  ->  IF   ID   EX   MEM  WB
sub  ->       IF   ID   EX   MEM  WB
and  ->            IF   ID   EX   MEM  WB
or   ->                 IF   ID   EX   MEM  WB
                        ^
         pipeline full here: 5 instructions in flight,
         one finishes (WB) every cycle from now on

But how does the machine keep five instructions from trampling each other's signals? Between every pair of stages sits a pipeline register — a wall of flip-flops that, on each clock tick, snapshots everything the next stage will need and carries that instruction's private data forward. Each load's clothes ride in their own basket between machines; the baskets are the pipeline registers. They are pure overhead — they compute nothing — but without them the stages would smear into one another, and the chapter on the critical path from the logic rung tells you why each tick must be long enough for the slowest stage plus its register to settle.

When the line jams: the three hazards

Real instructions are not laundry loads minding their own business — they depend on one another, and that breaks the tidy overlap. Anything that stops the next instruction from launching in its proper cycle is a pipeline hazard, and they come in exactly three flavors. The rest of this rung is essentially the story of these three and how engineers tamed each.

1. Structural hazard — two instructions want the same piece of hardware in the same cycle. Like one load needing the washer while another also needs it. The classic cure is to not share: give the pipeline separate instruction and data memories so a fetch and a memory access never collide (a quietly Harvard-flavored split).
2. Data hazard — an instruction needs a value that an earlier, still-in-flight instruction hasn't written back yet. This is the read-after-write dependence, and it's the most common jam in real code.
3. Control hazard — a branch decides whether to keep going straight or jump elsewhere, but that decision isn't known until the branch is partway down the pipe, while the machine has already fetched the instructions that follow. Bet wrong and they must be thrown away.

Take the data hazard concretely. Suppose an add writes its result into register x1, and the very next instruction subtracts using x1. In our diagram the add only reaches WB in cycle 5, but the sub wants to read x1 in its ID stage back in cycle 3 — two cycles too early. This is a read-after-write dependence: the reader is breathing down the writer's neck. Left alone the sub would grab a stale value and compute garbage.

The cures, and the cost in cycles

There are two tools for hazards, and you reach for the cheaper one first. The clever one is forwarding (also called bypassing): notice that the add actually computed x1's value back in its EX stage, long before it bothers to write it to the register file. So add a shortcut wire that snatches the freshly-computed result straight from one stage and feeds it into the ALU input of the waiting instruction — no waiting for the slow write-back trip. Most read-after-write hazards vanish for free this way, and guide 4 wires it up.

But forwarding can't conjure a value that doesn't exist yet. A load reads memory in MEM, one stage later than EX, so an instruction using a just-loaded value really has nowhere to grab it from in time. This is the load-use hazard, and here you must fall back on the blunt tool: a stall. The hardware freezes the dependent instruction for one cycle and slips a do-nothing bubble into the pipeline behind it — an empty basket on the conveyor — giving the load just enough time. The bubble costs you exactly one wasted cycle. For a branch, the matching cure is to flush the wrongly-fetched instructions once a misprediction is discovered, turning them into bubbles too.

Every bubble shows up in one number: the effective CPI, the average cycles per instruction the machine actually achieves. A perfect, hazard-free five-stage pipeline approaches an ideal of 1 instruction per cycle. Each stall and each flush nudges that average above 1 — and the iron law from the foundations rung reminds you run time is instruction count times CPI times cycle time, so a worse CPI directly slows the whole program. The art of the rest of this rung is keeping effective CPI as close to 1 as the hazards allow.

How deep should the line be?

If five stages are good, why not fifty? Chopping the work into more, shorter stages makes each stage's job smaller, which lets you shorten the clock period and raise the clock rate — the headline number marketing loves. Some early-2000s designs pushed past twenty and even thirty stages chasing gigahertz. This is the pipeline depth tradeoff, and the catch is brutal: a deeper pipe has more instructions in flight when something goes wrong, so every misprediction and every stall throws away more of them. A 30-stage machine that mispredicts a branch can flush dozens of instructions; a 5-stage machine loses a handful.