Lesson 32 · Build a processor

Pipelining

A processor that finishes one instruction before starting the next leaves most of its hardware idle. Pipelining splits every instruction into five stages (fetch, decode, execute, memory, write-back) with a pipeline register between each pair, so a new instruction can start every clock tick. Watch five TINY-8 instructions move through the stages together, read the pipeline diagram, and see why throughput goes up while each instruction's latency stays the same.

12 min10 steps5 questionsIntermediate

Fig 32 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01Which list gives the five stages of the classic pipeline in order?

An instruction is first fetched from memory, then decoded, then executed; the memory stage serves loads and stores, and write-back puts the result into a register.

02What does a pipeline register between two stages do?

Each pipeline register (IF/ID, ID/EX, EX/MEM, MEM/WB) copies its stage's result at the rising edge and holds it steady, so the stage behind it can start on the next instruction.

03On a five-stage pipeline with no stalls, how many clock ticks do 5 instructions take from the first fetch to the last write-back?

The first instruction needs 5 ticks; after that one more finishes every tick: 5 + 5 − 1 = 9. One at a time it would take 5 × 5 = 25.

04What does pipelining improve?

Each instruction still takes five ticks from fetch to write-back (a little more, because of the pipeline registers). What improves is the stream: once the pipeline is full, one instruction finishes every tick.

051,000 instructions run on a five-stage pipeline with nothing stalling. About how much faster is that than one at a time?

One at a time: 5 × 1000 = 5000 ticks. Pipelined: 5 + 1000 − 1 = 1004 ticks. 5000 / 1004 ≈ 4.98, close to the ideal speed-up, the number of stages.

Key terms

Glossary

Pipelining: Splitting each instruction into stages so that several instructions can be in different stages at the same time, like an assembly line.
Stage: One step of an instruction's work, done by its own part of the hardware in one clock tick: fetch, decode, execute, memory or write-back.
Pipeline register: A register between two stages that catches one stage's result at the clock edge and holds it for the next stage.
Clock cycle (tick): One period of the clock. In a pipeline every instruction moves one stage on at each rising edge.
Throughput: How many instructions finish per unit of time. Pipelining raises it.
Latency: How long one instruction takes from start to finish. Pipelining does not shorten it.
Pipeline diagram: A chart with instructions down the side and clock cycles along the top, showing which stage each instruction is in at each tick.
Hazard: A situation where the next instruction cannot safely go on in the next tick, for example because it needs a result that is not ready yet.

Fine print

Notes and sources

The classic five-stage pipeline splits every instruction into instruction fetch (IF), decode and register read (ID), execute (EX), memory access (MEM) and write-back (WB), with a pipeline register between each pair of stages: IF/ID, ID/EX, EX/MEM and MEM/WB (Patterson and Hennessy, Computer Organization and Design, chapter 4; Harris and Harris, Digital Design and Computer Architecture, section 7.5).
Patterson and Hennessy introduce pipelining with laundry: four loads, four steps of 30 minutes each (wash, dry, fold, put away). One load after another takes 4 × 4 × 0.5 = 8 hours; overlapped, the last load is put away after (4 + 4 − 1) × 0.5 = 3.5 hours.
Pipelining improves performance by increasing throughput, not by making one instruction faster. Each pipeline register adds a small delay (the time to capture and pass on a value), so one instruction's latency is a little longer than without a pipeline (Harris and Harris, sections 3.5 and 7.5).
With k equal stages and nothing stalling, n instructions take k + n − 1 ticks instead of k × n. As n grows the speed-up k × n / (k + n − 1) approaches k: 25 / 9 ≈ 2.8 for 5 instructions, 5000 / 1004 ≈ 4.98 for 1,000. Real pipelines fall short: stages are never perfectly balanced, so the slowest one sets the clock, and hazards make some instructions wait.
The five instructions are lines of the course's TINY-8 example, reordered so the four LDI instructions come first. Bytes come from the TINY-8 assembler (LDI r0, 2 is 10 02; ADD r0, r1 is 51 00) and every register value from its reference simulator. ADD r0, r1 reads r1 in the same tick LDI r1, 3 writes it, which works because the register file is written in the first half of a tick and read in the second (Patterson and Hennessy, chapter 4).

Quiz Unlocks after the last step.