Instruction Pipelining

A processor executes each instruction in stages. If it ran them strictly one at a time, the fetch hardware would sit idle while the execute hardware worked, and vice versa. Pipelining overlaps instructions like an assembly line: while one instruction is being executed, the next is being decoded and a third is being fetched. The classic design has five stages.

The five stages

1. 1IF — instruction fetch: read the instruction from memory.
2. 2ID — instruction decode: figure out the operation and read the registers.
3. 3EX — execute: the ALU does the arithmetic or computes an address.
4. 4MEM — memory access: load from or store to data memory (only loads/stores use this).
5. 5WB — write-back: write the result into a register.

Each instruction still takes five cycles from start to finish. But once the pipeline is full, all five stages are busy on five different instructions, and one instruction completes every cycle — that is the throughput win.

Worked example — the speedup

For n instructions in a k-stage pipeline, total cycles = k + (n - 1): k cycles to fill the pipe, then one completion per cycle thereafter.

100 instructions, 5-stage pipeline:

  pipelined   = k + (n - 1) = 5 + 99  = 104 cycles
  unpipelined = n * k       = 100 * 5 = 500 cycles

  speedup = 500 / 104 = ~4.8x  (approaching the 5-stage ideal)

Hazards — when overlap breaks

Overlap assumes instructions are independent. When they are not, a hazard stalls the pipeline. The most common is a data hazard: an instruction needs a value the one just ahead has not written back yet (a read-after-write conflict).

ADD R1, R2, R3   # R1 = R2 + R3  (result ready after EX)
SUB R4, R1, R5   # needs R1 in its own EX -- too soon!

The ADD does not write R1 back until its WB stage, but SUB wants R1 in its EX stage, which comes earlier. Without help, SUB must stall — wait with empty slots called bubbles — until the value is ready.