Pipelining

Q: What is the difference between latency and throughput in a pipeline?

Latency is how long one instruction takes start to finish (still five cycles, and slightly more with register overhead). Throughput is how often instructions complete (one per cycle once the pipeline is full). Pipelining improves throughput, not latency.

Overlapping instructions for throughput

12 min read

Pipelining overlaps the execution of several instructions by splitting the datapath into stages (classically fetch, decode, execute, memory, write-back) separated by pipeline registers, so that while one instruction decodes the next is fetched, raising throughput toward one instruction per cycle even though each instruction still takes several cycles from start to finish.

Builds onFetch, decode, execute Timing: delay and the clock speed limit

The fetch-decode-execute loop you built runs one instruction to completion before starting the next. But notice that the stages use *different* hardware: fetch uses the memory port, execute uses the ALU, write-back uses the register write port. While one instruction is in the ALU, the fetch hardware is idle. Pipelining puts that idle hardware to work: start the next instruction's fetch the moment this one moves on to decode, so several instructions are in flight at once, each in a different stage.

The laundry analogy

Doing laundry has three stages: wash (30 min), dry (30 min), fold (30 min), so one load takes 90 minutes. Four loads done one-at-a-time take 4 x 90 = 360 minutes. But the washer, dryer, and folding table are different machines. Start washing load 2 the instant load 1 moves to the dryer, and the machines all run at once. Now the four loads finish in 180 minutes, and after the pipeline fills, a fresh load comes out every 30 minutes. You did not make any single load faster; you stopped letting machines sit idle.

The same trick works on any circuit

The five instruction stages are just one example. You can pipeline any combinational circuit. Recall from timing that a circuit's slowest input-to-output route, its critical path, sets the minimum clock period: the clock cannot tick again until the last bit has settled. Pipelining attacks that number directly. Insert a bank of registers partway through the logic and the one long path becomes two shorter ones, each of which only has to settle before the next clock edge. A circuit that had to be clocked slowly because of a single long path can now be clocked much faster, and once the pipeline is full it hands back one result on every clock.

Worked example: pipelining an adder chain

Say you compute s = a + b + c with two 8-bit adders in series: the first forms a + b, the second adds c. Back to back, a value has to ripple through both adders before s is stable, so the critical path is two adder delays and the clock must be slow enough to cover both. Cut it. Put a register bank right after the first adder to latch a + b, and (so the operands line up) latch c in a register alongside it. Now stage 1 is only a + b and stage 2 is only (a + b) + c, each just one adder deep. The clock only has to cover a single adder delay per stage, so it can run close to twice as fast, and if you stream a series of (a, b, c) triples in, a finished sum leaves on every clock.

Notice what pipelining did and did not do. One a + b + c sum is no faster than before: it still passes through both adder stages, and the register overhead makes its total time (its latency) a touch longer. What improved is throughput, the rate finished sums leave the circuit. The pipeline fills exactly once, because the first triple still has to cross every stage, and after that a completed sum comes out on every clock. Since the clock itself now runs faster, far more sums finish per second. Pipelining buys throughput, not latency: you stop letting stages sit idle, you do not make any single job quicker. (The same staircase fill shows up for CPU instructions in the table further down.)

Balance the stages: the clock follows the slowest one

How fast can the clock actually go? From timing, the period must cover a stage's logic delay plus the register overhead (its clock-to-output time and the setup time the next stage needs). Suppose the whole circuit has a critical-path delay of 8 ns and each register bank costs 1 ns of overhead. Unpipelined, with a register at each end, the period is 8 + 1 = 9 ns, a ceiling near 111 MHz. Cut the logic into two balanced 4 ns halves and each stage's period is 4 + 1 = 5 ns, about 200 MHz: nearly double, though not exactly, since the 1 ns overhead is now paid twice. Cut it unevenly into 6 ns and 2 ns instead and the clock is stuck at the slow stage, 6 + 1 = 7 ns (about 143 MHz), even though the total logic is the same 8 ns. A pipeline runs only as fast as its slowest stage, its bottleneck, so the real skill is splitting the logic into stages of equal delay.

Keep cutting and every new register bank pays that 1 ns overhead again, so the returns shrink. Splitting 8 ns of logic into k equal stages gives each stage a period of 8 / k + 1 ns:

Stages	Stage logic	Period	Max clock
1	8 ns	9 ns	111 MHz
2	4 ns	5 ns	200 MHz
4	2 ns	3 ns	333 MHz
8	1 ns	2 ns	500 MHz

Cutting the same 8 ns of logic into more stages raises the clock, but every stage still pays the 1 ns register overhead, so the period can never drop below 1 ns: the ceiling here is 1 GHz no matter how many stages you add. Past a point you spend power and area for almost no extra speed.

Try it

A combinational multiplier has a critical-path delay of 12 ns, and each pipeline register adds 1 ns of overhead. (a) What is its maximum clock unpipelined? (b) You split it into 3 balanced stages: what is the new maximum clock and throughput? (c) What is the latency of one multiply now?

The classic five stages

A textbook RISC pipeline splits each instruction into five stages, with a pipeline register between each pair that latches one instruction's partial results so the next stage can pick them up on the next clock (exactly the role of the registers and clocking you already built).

IF (instruction fetch): read the instruction from memory at the program counter, increment the counter.
ID (instruction decode): decode the opcode and read the source registers.
EX (execute): run the ALU (arithmetic, or compute a memory address).
MEM (memory access): read or write data memory, for loads and stores.
WB (write-back): write the result back into a register.

With the stages overlapped, the pipeline looks like a diagonal: each instruction starts one cycle after the one before, and once full, one instruction completes every cycle.

Instr	c1	c2	c3	c4	c5	c6	c7
I1	IF	ID	EX	MEM	WB
I2		IF	ID	EX	MEM	WB
I3			IF	ID	EX	MEM	WB

Three instructions flowing through the five stages. From cycle 5 on, a full pipeline retires one instruction per cycle even though each instruction still takes five cycles to pass through.

Throughput is not latency

Pipelining does not shorten one instruction. I1 still takes 5 cycles from IF to WB; that is its latency, and the pipeline registers even add a touch of overhead. What changes is throughput: the rate instructions complete. For n instructions in a k-stage pipeline, the time is k + (n - 1) cycles instead of n x k, because after the first instruction fills the pipe, each later one needs just one more cycle. As n grows the speedup approaches k.

pipelined cycles = k + (n - 1) vs sequential = n x k

Hazards: when overlap breaks

Overlap assumes the instructions are independent. When they are not, a hazard can make a naive pipeline compute the wrong answer or need to wait. There are three kinds:

Structural hazard: two instructions need the same hardware in the same cycle (for example, one fetching while another reads data memory, if there is only one memory port). The fix is more resources, such as separate instruction and data memories.
Data hazard: an instruction needs a result that an earlier, still-in-flight instruction has not written back yet (a read-after-write, or RAW, dependency). If ADD produces a value in WB but the next SUB reads it in ID two cycles earlier, the SUB would read a stale register.
Control hazard: a branch is not resolved until it reaches EX, but by then the pipeline has already fetched the instructions after it, which may be the wrong ones if the branch is taken.

Fixing hazards

Most data hazards are solved by forwarding (also called bypassing): the result exists in the EX or MEM stage well before WB writes it to the register file, so a wire routes it straight from where it is produced to where it is needed, with no waiting. Forwarding handles back-to-back arithmetic dependencies for free.

One data hazard forwarding cannot fully hide is the load-use hazard: a load's value is not available until after its MEM stage, so an instruction that uses it in the very next cycle must stall for one cycle (insert a bubble, a do-nothing slot) before forwarding can deliver it. Control hazards are handled by stalling until the branch resolves, by branch prediction (guess the outcome, fetch ahead, and undo if wrong), or by a delayed branch (define the slot after a branch to always execute). A regular, fixed-length RISC instruction set pipelines cleanly precisely because every instruction fits the same five stages, which is a large part of why such instruction sets exist.

Common mistakes. Pipelining improves throughput, not single-instruction latency; one instruction is no faster (and slightly slower) than before. Deeper pipelines are not automatically better: more stages mean more hazards and more stalls, and each pipeline register adds clock-to-output and setup overhead to the clock period, so there is a sweet spot. And do not assume branches are free: a mispredicted branch throws away the instructions fetched behind it, a real cost the analogy hides.

Try it

A non-pipelined CPU takes 5 cycles per instruction. You rebuild it as a 5-stage pipeline. Ignoring hazards, how many cycles does each design take to run 100 independent instructions, and what is the speedup?

Pipelining is the first big idea in instruction-level parallelism: keep the hardware busy by working on several instructions at once. Nearly every processor since the 1980s pipelines, and the deeper ideas (superscalar, out-of-order) all build on it. Our teaching CPU stays single-cycle for clarity, so pipelining here is conceptual, but every hazard above is a real thing real silicon spends transistors to handle.

Pipelining changes the performance equation by driving the average cycles per instruction toward 1 while sometimes raising it again with stalls. To weigh that tradeoff against clock speed and instruction count, the next lesson, measuring performance, puts all three on one scale.

Frequently asked

What is pipelining in a CPU?

Pipelining splits the datapath into stages separated by registers and overlaps several instructions, each in a different stage, so that while one instruction decodes the next is being fetched. It raises throughput toward one instruction per cycle without making any single instruction faster.

What are the five stages of a classic pipeline?

IF (instruction fetch), ID (instruction decode and register read), EX (execute or address calculation in the ALU), MEM (data memory access for loads and stores), and WB (write the result back to a register). A pipeline register between each pair carries one instruction's partial state to the next stage.

What is the difference between latency and throughput in a pipeline?

Latency is how long one instruction takes start to finish (still five cycles, and slightly more with register overhead). Throughput is how often instructions complete (one per cycle once the pipeline is full). Pipelining improves throughput, not latency.

What is a pipeline hazard?

A hazard is a situation where overlapping instructions would otherwise produce a wrong result or force a wait. Structural hazards are resource conflicts, data hazards are an instruction needing a result not yet written, and control hazards come from branches resolved after later instructions are already fetched.

How does forwarding fix a data hazard?

The needed result usually already exists in a later stage (EX or MEM) before it is written back, so forwarding routes it directly from where it is produced to the stage that needs it, avoiding a stall. The exception is the load-use hazard, where the value arrives too late and a one-cycle stall (a bubble) is still required.

Can you pipeline any circuit, or only a CPU?

Any combinational circuit can be pipelined. Insert a bank of registers partway through the logic to split its long critical-path delay into shorter stages, and the clock can run faster while the circuit delivers one result per clock once the pipeline is full. Arithmetic units, multipliers, and graphics shading units are all pipelined; the CPU instruction pipeline is just the most famous case.

What sets the clock speed of a pipeline?

The slowest stage. The clock period must cover the longest stage's logic delay plus each register's overhead (its clock-to-output time and the next stage's setup time), so an unbalanced pipeline is only as fast as its bottleneck. That is why stages are cut to have roughly equal delay, and why adding stages stops helping once each stage's logic shrinks to about the register overhead.

Every lesson here builds toward one thing: a working CPU, from the transistor up.

Open the free lab →