Instruction Pipelining, Hazards and the I/O Interface
A pipeline does not make any single instruction faster. It overlaps instructions so that one finishes every cycle instead of every k cycles, and every question in this chapter is about the gap between that ideal and what actually happens. Three facts set the ideal. The clock is set by the slowest stage, not the average, so a pipeline of stages taking 2, 3, 4, 3 and 2 ns runs at 4 ns and its ideal speedup over the 14 ns serial path is 14/4 = 3.5 — not 5, even though there are five stages. Latch overhead then eats into that: add 0.2 ns of register delay per stage and the clock is 4.2 ns and the speedup 3.33. And for a finite number of instructions the pipeline has to fill and drain, so speedup is nk/(k + n − 1), which for five stages and a hundred instructions is 4.81 rather than 5 — approaching k only as n grows large. What separates the ideal from reality is hazards, and they come in three kinds worth keeping distinct because their fixes differ: structural hazards are two instructions wanting one resource, fixed by duplicating it; data hazards are an instruction needing a result not yet written, fixed largely by forwarding; and control hazards are a branch whose outcome is unknown, fixed only partially, by prediction. Their cost is counted as added CPI: 20% of instructions stalling one cycle and 15% of them costing two brings CPI from 1 to 1.5, and a third of the pipeline's benefit is gone. The chapter closes on I/O, where the same overlap argument reappears in cruder form — an interrupt per byte costs the CPU thousands of cycles for a kilobyte, and DMA replaces that with one setup and a stolen cycle per transfer.
Three Hazards, Three Different Fixes
| Hazard | Cause | Fix |
|---|---|---|
| Structural | Two instructions need the same hardware in one cycle | Duplicate the resource — separate instruction and data memory |
| Data (RAW) | An instruction reads a register the previous one has not written | Forwarding removes most; a load-use pair still stalls one cycle |
| Control | The next address is unknown until a branch resolves | Only partly fixable — prediction, delay slots, early resolution |
🧠 Count hazards as added CPI, not as cycles
An ideal pipeline has CPI = 1. Every hazard adds its frequency times its penalty. If 20% of instructions are loads whose result is used immediately, each stalling one cycle, that adds 0.20. If 15% are branches costing two cycles each when mispredicted, that adds 0.30. CPI = 1 + 0.20 + 0.30 = 1.5, so the machine delivers two-thirds of its ideal throughput and the pipeline's benefit is a third smaller than the stage count suggests. Working in CPI rather than in absolute cycles is what makes these questions quick, and it also makes the answer comparable across programs — which is exactly why real design arguments are made in CPI.Interrupts, DMA, and Why the Difference Is Large
Programmed I/O has the CPU poll a status register, which wastes every cycle spent waiting. Interrupt-driven I/O lets the device speak up, but the CPU still executes a handler per unit transferred: at one byte per interrupt and ten cycles of overhead each, moving a 1 KB block costs 1024 × 10 = 10,240 cycles. DMA hands the transfer to a controller that moves the block itself and interrupts once at the end, so the CPU pays one setup — say 500 cycles — plus one stolen bus cycle per word: about 1,524 cycles for the same kilobyte, nearly seven times cheaper.
🎯 Cycle stealing is not the same as blocking the CPU
A DMA controller needs the bus, not the CPU. In cycle-stealing mode it takes one bus cycle at a time, and the CPU continues executing except in the cycles it happens to want the bus — so the cost is a small slowdown rather than a halt. In burst mode the controller holds the bus for the whole block, which is faster for the transfer and stalls the CPU for its duration. The examinable consequence of DMA is not the speed but the coherence problem: the controller writes main memory directly, so a write-back cache holding a stale copy of those addresses must be invalidated, which is the connection back to the previous chapter and a favourite place for a question to join the two topics.Key takeaways
- The pipeline clock is the slowest stage plus latch delay, never the average of the stages.
- Speedup for n instructions through k stages is nk/(k + n − 1), tending to k only for large n.
- Unequal stages, latch overhead and a finite instruction count each pull the speedup below k.
- Structural hazards are fixed by duplicating hardware, data hazards largely by forwarding, control hazards only partly by prediction.
- Forwarding cannot remove a load-use stall — the value is not read from memory until the stage after the ALU.
- Count hazards as CPI: 1 + frequency × penalty, summed over the hazards.
- DMA replaces one interrupt per unit with one setup plus a stolen cycle per word — about 1,524 cycles against 10,240 for a kilobyte.
- DMA writes memory directly, so a write-back cache holding those lines must be invalidated.
Practice questions (8)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
A five-stage pipeline has stage delays of 2, 3, 4, 3 and 2 ns and no latch overhead. What is the ideal speedup over a non-pipelined implementation? (One decimal place.)
Numerical answer — type the value.
Show answer
Answer: 3.5
The non-pipelined path runs the stages in sequence: 2+3+4+3+2 = 14 ns per instruction. The pipelined clock is set by the slowest stage, 4 ns, so the speedup is 14/4 = 3.5. The tempting answer is 5, from the number of stages, and it is right only for a perfectly balanced pipeline — here the 4 ns stage forces every other stage to idle for part of each cycle, and that idling is the whole of the loss. Balancing this pipeline into five 2.8 ns stages would recover the full factor of 5, which is why stage balancing is a real design activity rather than an exam artefact.A 5-stage pipeline with equal stages executes 100 instructions. Its speedup over a non-pipelined machine is closest to:
Show answer
Answer: B — 4.81
Speedup = nk/(k + n − 1) = (100 × 5)/(5 + 100 − 1) = 500/104 = 4.81. The shortfall from 5 is the cost of filling and draining the pipeline: the first instruction still takes all five cycles, and the last four cycles produce no new completions. As n grows the denominator approaches n and the ratio approaches k — at n = 1000 it is 4.98 — which is why the k-times claim is stated for long instruction streams. Option A is the asymptote quoted as the answer, and it is the single commonest error in this calculation.An ideal pipeline has CPI 1. In a program, 20% of instructions are loads that stall one cycle each, and 15% are branches that cost two cycles each. What is the effective CPI?
Numerical answer — type the value.
Show answer
Answer: 1.5
Each hazard contributes its frequency times its penalty: loads add 0.20 × 1 = 0.20, branches add 0.15 × 2 = 0.30. CPI = 1 + 0.20 + 0.30 = 1.5. So the machine achieves 1/1.5 = two-thirds of its ideal throughput, and a third of the pipeline's advantage has been spent on hazards — which is the number a design argument actually turns on. The two errors worth naming: adding the frequencies without weighting by penalty gives 1.35, and forgetting the base 1 gives 0.5, which should be caught by noticing that CPI below 1 is impossible for a single-issue pipeline.Operand forwarding eliminates most data hazards but cannot remove the stall in which case?
Show answer
Answer: B — A load whose value is used by the immediately following instruction
Forwarding works when the value already exists somewhere in the pipeline by the time it is needed. An ALU result exists at the end of the execute stage, so it can be routed straight to the next instruction's execute stage — no stall (A is fixed). But a load does not have its value until the end of the memory stage, one stage later than the ALU, so an instruction immediately after it needs the value before it exists anywhere: forwarding has nothing to forward, and one cycle of stall is unavoidable. This is the load-use hazard, and it is why compilers reorder instructions to put something useful between a load and its use. Option D is a control hazard, a different category with a different fix.A structural hazard is best resolved by:
Show answer
Answer: C — Duplicating or pipelining the contended resource
A structural hazard is a hardware shortage — two instructions needing the same unit in the same cycle — so the fix is more hardware: separate instruction and data memories (which is exactly why a pipelined machine has split L1 caches), or a pipelined multiplier instead of a single-cycle one. Forwarding addresses data hazards and prediction addresses control hazards; each is the right answer to a different question, and the three fixes are not interchangeable. Compiler reordering can hide a structural hazard's cost but cannot remove the contention, because the resource is still single.Transferring a 1 KB block one byte at a time by interrupt-driven I/O costs 10 CPU cycles of handler overhead per byte. How many CPU cycles does the whole transfer cost?
Numerical answer — type the value.
Show answer
Answer: 10240
1 KB is 1024 bytes, one interrupt each, ten cycles each: 1024 × 10 = 10,240 cycles. The figure is worth carrying because of what it is compared against — DMA on the same block costs one setup of a few hundred cycles plus one stolen bus cycle per word, roughly 1,524 cycles in total, and the near-sevenfold gap is the entire justification for putting a DMA controller on a machine. The comparison is also the reason interrupt-driven I/O survives at all: for a device delivering one byte occasionally, such as a keyboard, 10 cycles is nothing and a DMA setup would be pure overhead.Which of the following are true of DMA? (More than one may be correct.)
Show answer
Answer: A — In cycle-stealing mode the CPU continues executing between stolen cycles; B — It can leave a write-back cache holding stale data for the transferred addresses
A and B. Cycle stealing takes the bus one cycle at a time, so the CPU runs on except when it wants the bus in a stolen cycle (A) — that is the difference between DMA and simply blocking the processor. And because the controller writes main memory directly, a cache holding those lines is now out of date, which under a write-back policy means the stale copy must be invalidated or the CPU will read the old value (B) — the coherence problem, and the usual way a question links this chapter to the cache chapter. C and D are both descriptions of interrupt-driven and programmed I/O respectively, which are precisely what DMA exists to replace: it interrupts once at the end of the block, and the controller, not the CPU, runs the loop.Adding a 0.2 ns latch delay per stage to the pipeline with stages 2, 3, 4, 3, 2 ns changes the speedup from 3.5 to about:
Show answer
Answer: A — 3.33
The latch delay is paid once per cycle, not once per instruction, so it lands on the clock period: the clock becomes 4 + 0.2 = 4.2 ns and the speedup 14/4.2 = 3.33. The point of the question is what this implies about deep pipelines: each extra stage shortens the longest stage but adds another latch delay to every cycle, so speedup rises, peaks and then falls. That trade is why processors stopped getting deeper pipelines and started getting more cores. Option D is the new clock period mistaken for the speedup, which is worth catching by units alone.