E ExamMaster

Computer Architecture · Computer Architecture

Instruction Pipelining

Overlap fetch, decode, execute, memory and write-back; hazards that stall that overlap; speedup versus a non-pipelined machine.

The ISA topic walked LOAD R1, (R2) through fetch, decode, execute, memory and write-back as if the machine did one job at a time. Pipelining overlaps those jobs so a new instruction can start every clock once the pipe is full. This topic is that overlap, what stalls it, and the speedup formula.

  • Computer Architecture
  • Hard level
  • 4 concepts

1Instruction pipelining

Pipelining overlaps the five jobs of `LOAD R1, (R2)` so more than one instruction occupies the machine at once. The classic stages are IF (fetch), ID (decode), EX (execute), MEM (memory), and WB (write-back). While our LOAD is in MEM reading 0x1000, the next instruction can be in EX, the one after that in ID, and a new one in IF.

Each individual instruction still walks all k stages — the LOAD still takes five clocks of latency. What rises is throughput: once the pipe is full, a new instruction can complete every clock. A non-pipelined CPU finishes write-back before the next fetch; a k-stage pipeline can have up to k instructions in flight.

Figure. Three instructions stagger through the same five stages. Each row starts one stage-width after the row above, so at any clock the busy stages hold different instructions. The top row is our LOAD.

How it works

  1. FillThe first instruction walks through all k stages before any result completes.
  2. Steady stateEvery clock, one instruction enters and one completes — throughput ≈ 1 per cycle.
  3. DrainAfter the last fetch, k − 1 cycles elapse before the final write-back.

Cycles for a handful of instructions

A 5-stage pipeline (k = 5) runs 3 instructions with no hazards, against a non-pipelined machine that spends 5 cycles per instruction. How many cycles does each take, and what is the speedup?

  • non-pipelined = k times n = 5 x 315 cycles
  • pipelined = k + (n - 1) = 5 + 27 cycles
  • speedup = 15 / 7about 2.14, far below k for small n

Pro tip. For small n the fill cost k dominates, so the speedup stays well under the stage count; only as n grows does the ratio kn / (k + n - 1) approach k.

In a 5-stage pipeline at steady state, a new instruction completes every
  1. 1 clock cycle
  2. 5 clock cycles
  3. 4 clock cycles

Once filled, one instruction finishes per cycle even though each still needs 5 stages. Five cycles is the latency of one instruction, not the completion rate.

2Pipeline hazards

A hazard is anything that stops the ideal overlap. A structural hazard is two stages wanting the same hardware in the same clock. A data hazard is an instruction that needs a register another instruction has not yet written — after `LOAD R1, (R2)`, an `ADD R3, R1, R4` needs R1. A control hazard follows a branch: fetch may have already pulled the wrong next instruction.

The usual fixes: duplicate a contended unit; forward (bypass) a result from a pipeline register so the consumer does not wait for write-back; predict the branch and flush if the guess was wrong. The ideal speedup of a k-stage pipeline approaches k only when hazards are rare.

Figure. Hazards stall or squash a stage: data (result not ready), control (branch), structural (resource conflict). EX is highlighted because that is where a data-hazard consumer first needs the missing value.

How it works

  1. StructuralTwo stages need the same hardware at once — duplicate the unit or stall one stage.
  2. DataA later instruction needs a result not yet written — forward the value, or insert stall bubbles.
  3. ControlA branch may have fetched the wrong next instruction — predict, and flush on a mispredict.
Hazard types and fixes
HazardCauseTypical fix
StructuralTwo stages need the same unitDuplicate hardware or stall
Data (RAW)Consumer reads before producer writesForwarding or stall bubble
ControlBranch changes PC after wrong path fetchedPredict, delayed branch, or flush
An ADD will write R1 in WB, and the next instruction needs R1 before that write is available. Without forwarding, the pipeline must
  1. Insert stall bubbles until WB completes
  2. Flush all five stages and restart
  3. Predict the branch and continue fetching

This is a read-after-write data hazard. Forwarding bypasses the stall; without it, bubbles wait for WB. Flushing is for control hazards; branch prediction does not resolve operand availability.

3Pipeline speedup

For k pipeline stages executing n instructions, speedup over a non-pipelined design is \text{Speedup} = \frac{k \times n}{k + (n - 1)}. The denominator is k cycles to fill plus (n − 1) cycles at steady throughput. As n grows large, speedup approaches k, the stage count. For a handful of instructions, fill and drain eat most of the time and speedup falls well short of k.

Never report k as the speedup without checking n. A 5-stage pipe running three instructions — our LOAD and two neighbours — spends most of its clocks filling and draining.

Figure. Ideal speedup approaches the stage count. The left bar is one instruction's serial cost; the right bar is the steady issue cost after fill. Hazards and fill/drain keep the realised factor lower than 5.

How it works

  1. Non-pipelined timek × n cycles — each of n instructions passes through all k stages serially.
  2. Pipelined timek + (n − 1) cycles — k to fill, then one completion per cycle.
  3. RatioDivide non-pipelined by pipelined; for large n the ratio → k.

Pipeline speedup

A 5-stage pipeline executes 1000 instructions. What is the speedup over a non-pipelined design that spends 5 cycles on each instruction?

  • Speedup = \frac{k \times n}{k + (n - 1)} = \frac{5 \times 1000}{5 + 999}5000 / 1004
  • 5000 / 1004≈ 4.98
  • Speedup≈ 5 (near stage count k)

Pro tip. For very large n, pipeline speedup tends to the stage count k. With only a few instructions, fill-and-drain overhead keeps speedup well below k.

A 4-stage pipeline runs 10^6 instructions. Speedup over non-pipelined is closest to
  1. 4
  2. 10^6
  3. 4 \times 10^6

With n = 10^6, overhead is negligible: speedup ≈ k = 4. 10^6 is the instruction count; 4 \times 10^6 is the non-pipelined cycle count, not the ratio.

4The LOAD in the pipe

Put the running instruction in that schedule. `LOAD R1, (R2)` fetches, decodes, forms 0x1000, reads memory, writes R1. The next line of the tiny program is `ADD R3, R1, R4` — add the loaded word into a running total. The ADD needs R1. That is a load-use data hazard: the consumer is the very next instruction after a load.

Forwarding can hand the MEM-stage result to the ADD without waiting for write-back. It cannot hand the result a cycle earlier than MEM, because the word is still in flight from 0x1000. So a load-use pair still pays one stall bubble even with forwarding. Without forwarding, the ADD waits until WB completes.

Figure. LOAD produces the word in MEM. ADD is issued the next clock and still needs one stall so its EX lines up after that MEM. Forwarding then carries 0x1000's word into the ADD; WB of the LOAD is too late to be the only path.

How it works

  1. LOAD in MEMThe word at 0x1000 becomes available at the end of MEM, not at WB.
  2. ADD wants R1ADD R3, R1, R4 needs R1 in EX. That is one stage before the LOAD's WB.
  3. Load-useEven with forwarding from MEM, the ADD still needs one stall — the value is not ready a cycle earlier.
LOAD R1, (R2) then ADD R3, R1, R4. With forwarding from MEM, the ADD still
  1. Needs one stall — the word is not ready before MEM
  2. Needs no stall — forwarding removes every data hazard
  3. Must flush the pipeline — this is a control hazard

Load-use is the case forwarding cannot fully hide: the data appear at MEM. ALU-to-ALU pairs can forward with zero stall. This is not a branch, so there is nothing to flush.

Notes

  • Pipelining overlaps instruction stages (IF, ID, EX, MEM, WB) to increase throughput; each instruction still has latency equal to the stage count.
  • Hazards (structural, data, control) stall or flush the pipeline; data hazards are resolved by forwarding or stalls, control hazards by prediction.
  • Ideal speedup for k stages and n instructions is kn / (k + n − 1) and approaches k only when n is large and hazards are rare.
  • A load-use pair — LOAD R1 then an instruction that reads R1 — still needs one stall even with forwarding, because the word arrives at MEM.
  • Throughput at steady state is one instruction per cycle; that is not the same as one-cycle latency.

Formulas

  • Pipeline speedup = \frac{k \times n}{k + (n-1)} for k stages and n instructions; ideal speedup \to k.
  • Pipelined cycles (no hazards) = k + (n - 1).
  • Non-pipelined cycles = k \times n if each instruction takes k cycles.
  • For an ideal pipeline, throughput = 1 instruction per clock cycle after the pipeline fills.

Exam traps & shortcuts

  • For pipeline speedup with large n, the answer approaches the number of stages k.
  • Latency of one instruction is still k cycles; throughput is 1 per cycle after fill.
  • Load-use is the data hazard forwarding cannot fully hide.

Reference tables

Use the speedup formula only after naming k and n. Hazards are not in the ideal formula.

Formula sheet
QuantityFormulaWatch for
Pipelined cyclesk + (n − 1)No hazards
Pipeline speedupkn / (k + n − 1)→ k only when n is large
Steady throughput1 instruction / cycleAfter fill; latency still k cycles

Recap

Overlap raises throughput. Hazards eat the ideal k. The running LOAD still has a load-use stall.

Overlap
k stages in flight; each instruction still takes k cycles of latency.
Hazards
Structural = shared hardware; data = forward or stall; control = predict or flush.
Speedup
kn / (k + n − 1) → k only when n is huge and stalls are rare.
LOAD then ADD
Load-use: one stall remains even with forwarding from MEM.

Practise Instruction Pipelining

Reading is free and needs no account. Practice, mocks and progress live in the app.

  • A 3-question practice set that ends the chapter
  • 4 quick checks with worked explanations
  • Timed mocks scored with the real marking scheme
  • Readiness tracked per topic, kept on your device
Continue with Google — freeNo card, no trial. Works offline once installed.