# Pipelining

*Overlapping instructions for throughput*

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.

Group: Processor
URL: https://digiwleea.wleeaf.dev/learn/pipelining/

The [fetch-decode-execute](https://digiwleea.wleeaf.dev/learn/cpu/) 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](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/regbit/) partway through the logic and the one long path becomes two shorter ones, each of which only has to settle before the next [clock](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/adder8/) 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](https://digiwleea.wleeaf.dev/learn/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._

**Q (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?

**A:** (a) The period must cover `12 + 1 = 13 ns`, so at most `1 / 13 ns`, about `77 MHz`. (b) Three balanced stages are `12 / 3 = 4 ns` of logic each, so the period is `4 + 1 = 5 ns`, a clock of `200 MHz`, and once the pipe is full it finishes one multiply every clock: `200 million` per second. (c) Latency is `3 stages x 5 ns = 15 ns`, slightly worse than the `13 ns` unpipelined, because pipelining trades a little latency for much higher throughput (about `2.6x` here, short of the ideal `3x` because of the register overhead).

## 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](https://digiwleea.wleeaf.dev/learn/regbit/) and [clocking](https://digiwleea.wleeaf.dev/learn/timing/) you already built).

1. **IF (instruction fetch)**: read the instruction from memory at the program counter, increment the counter.
2. **ID (instruction decode)**: decode the opcode and read the source registers.
3. **EX (execute)**: run the [ALU](https://digiwleea.wleeaf.dev/learn/alu/) (arithmetic, or compute a memory address).
4. **MEM (memory access)**: read or write data memory, for loads and stores.
5. **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:

1. **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.
2. **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.
3. **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.

> **WARN:** 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.

**Q (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?

**A:** Non-pipelined: `100 x 5 = 500` cycles. Pipelined: `k + (n - 1) = 5 + 99 = 104` cycles. Speedup = `500 / 104` which is about `4.8x`. It falls just short of the ideal `5x` because of the 4 cycles spent filling the pipeline at the start; the longer the program, the closer to `5x` it gets.

> **KEY:** 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](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/performance/), puts all three on one scale.

### FAQ

**Q:** What is pipelining in a CPU?

**A:** 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.

**Q:** What are the five stages of a classic pipeline?

**A:** IF (instruction fetch), ID (instruction decode and register read), EX (execute or address calculation in the [ALU](https://digiwleea.wleeaf.dev/learn/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.

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

**A:** **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.

**Q:** What is a pipeline hazard?

**A:** 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.

**Q:** How does forwarding fix a data hazard?

**A:** 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.

**Q:** Can you pipeline any circuit, or only a CPU?

**A:** Any combinational circuit can be pipelined. Insert a bank of registers partway through the logic to split its long [critical-path](https://digiwleea.wleeaf.dev/learn/timing/) 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.

**Q:** What sets the clock speed of a pipeline?

**A:** 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.