Instruction Pipelining

Washing, drying and folding clothes one load at a time wastes the washer while the dryer runs. Starting the next load as soon as the washer is free keeps every machine busy. A pipeline does the same with instructions: it splits instruction execution into stages and works on several instructions at once, each in a different stage.

The five classic stages

stages = ["IF", "ID", "EX", "MEM", "WB"]
program = ["I1", "I2", "I3", "I4"]
cycles = len(stages) + len(program) - 1
print("     " + " ".join(f"{c:>3}" for c in range(1, cycles + 1)))
for i, name in enumerate(program):
    row = ["   "] * cycles
    for s, stage in enumerate(stages):
        row[i + s] = f"{stage:>3}"
    print(f"{name:4} " + " ".join(row))
print(f"{len(program)} instructions finish in {cycles} cycles instead of {len(program) * len(stages)}")

       1   2   3   4   5   6   7   8
I1    IF  ID  EX MEM  WB
I2        IF  ID  EX MEM  WB
I3            IF  ID  EX MEM  WB
I4                IF  ID  EX MEM  WB
4 instructions finish in 8 cycles instead of 20

Once the pipeline is full, one instruction completes every cycle, even though each instruction still takes 5 cycles from start to finish (its latency does not improve; the throughput does).

Timing

With k stages, stage delays d₁, …, d_k, and a pipeline register (latch) delay d_latch between stages:

• Clock period T_p = max(dᵢ) + d_latch: the slowest stage sets the pace.
• Time for n instructions = (k + n − 1) × T_p: the first instruction needs k cycles, then one more finishes every cycle.
• Non-pipelined time = n × Σdᵢ (one instruction at a time, no latches).
• Speedup = non-pipelined time / pipelined time. As n grows, it approaches Σdᵢ / T_p, and in the ideal case (equal stages, no latch delay) it approaches k.
• Efficiency = speedup / k, and throughput = n / (pipelined time).

Example: stages of 150, 120, 160, 140 and 130 ps with 10 ps latches.

stages = [150, 120, 160, 140, 130]       # ps
latch, n, k = 10, 1000, len(stages)
clock = max(stages) + latch
pipelined = (k + n - 1) * clock
unpipelined = n * sum(stages)
print(f"clock period = {clock} ps")
print(f"{n} instructions: pipelined {pipelined} ps, non-pipelined {unpipelined} ps")
print(f"speedup = {unpipelined / pipelined:.3f}, limit for large n = {sum(stages) / clock:.3f}, ideal = {k}")
print(f"throughput = {n / pipelined * 1e12 / 1e9:.2f} billion instructions per second")

clock period = 170 ps
1000 instructions: pipelined 170680 ps, non-pipelined 700000 ps
speedup = 4.101, limit for large n = 4.118, ideal = 5
throughput = 5.86 billion instructions per second

The speedup is about 4.1, not 5, because the stages are unequal (the 160 ps stage forces every stage to take 170 ps) and because of the latch overhead.

Why real speedup is lower

• Unbalanced stages: the clock fits the slowest stage.
• Latch overhead: every stage pays the pipeline register delay.
• Fill and drain: the k − 1 cycles at the start and end do less useful work (significant for small n).
• Hazards: dependences between instructions force stalls (next lesson).

With stalls, the average CPI becomes 1 + (stall cycles per instruction), and speedup = pipeline depth / (1 + stalls per instruction) in the ideal-stage case.

Making the pipeline deeper (more, shorter stages) raises the clock rate, but the latch overhead becomes a larger fraction of each stage and hazards cost more cycles, so very deep pipelines stop paying off.

Practice questions