Five stages
Running one TINY-8 instruction takes five jobs: fetch its two bytes, decode them, execute, use memory, then write the result back. Give each job its own piece of hardware, a stage, and one clock tick.
If the next instruction waits until the last one is finished, four of the five stages sit idle every tick. LDI r1, 3 cannot start until LDI r0, 2 is written back. Five instructions take 5 × 5 = 25 ticks.
Overlapping work
Put a pipeline register between each pair of stages. At every rising clock edge it catches what its stage just finished and holds it for the next stage. The stage behind it is then free to start new work.
Now a new instruction enters fetch at every tick, like laundry: while load 1 dries, load 2 washes. In Patterson and Hennessy's example four loads take 8 hours one after another but 3.5 hours overlapped.
At cycle 5 the pipeline is full: five instructions are in flight, one in each stage. ADD r0, r1 is being fetched while LDI r0, 2 writes 2 into r0. No stage is idle any more.
Reading the diagram
A pipeline diagram puts instructions down the side and clock cycles along the top. Each row is one instruction; each column is one tick. Every row starts one column later, so the stages form a staircase.
Throughput is how many instructions finish per tick. Once the pipeline is full, one instruction is written back every tick. All five finish after 9 ticks instead of 25.
Latency is how long one instruction takes from start to finish. Follow ADD r0, r1: fetched in cycle 5, written back in cycle 9. That is still five ticks, just as before. Pipelining speeds up the stream, not each instruction.
How much faster
With k stages, n instructions take k + n - 1 ticks instead of k × n. For 1,000 instructions on five stages that is 1,004 ticks instead of 5,000: almost 5 times faster. The ideal speed-up equals the number of stages.
The results are the same as running one at a time: r0 = 5, r1 = 3, r2 = 3, r3 = 1. This order was chosen so no instruction needs a result before it is written. When one does, the pipeline has a hazard.
Tick by tick
;; step 1/10 · five-stages ;; about: Fetch, Decode, Execute, Memory, Write-back LDI r0, 2 (bytes 10 02) cycle 1 IF read bytes 10 02 at address 0 cycle 2 ID opcode 1 = LDI, target r0, value 2 cycle 3 EX nothing to compute, 2 passes on cycle 4 MEM no memory access (only LD and ST) cycle 5 WB r0 = 2 1 instruction, 5 stages, 5 ticks
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). 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).