The Pipeline
Stretch reached Los Alamos in April 1961 fetching and decoding instructions ahead of the one being executed. The usual diagram shows stages marching along. What follows counts the cost. Put in an instruction that needs a value the one in front of it has not written yet and the whole thing stops until it exists. What follows counts the cycles that costs and computes the speedup, which is never the number of stages.
New to overlapping instructions? Start here
An instruction is not one action. It is fetched from memory, decoded into what it wants, executed, and the result written back. Doing all four for one instruction before starting the next leaves three quarters of the machine idle at any moment.
So they overlap, like an assembly line: while one instruction is executing, the next is being decoded and another fetched. Nothing runs faster; more is in flight. The cost arrives when an instruction needs a result the one in front has not written back yet, and this page is about what happens then.
What a processor actually does
A processor fetches an instruction, works out what it says, carries out the operation, and chooses the next instruction. Add these numbers. Read this address. If this value is zero, branch there. Then the cycle repeats.
Caches, pipelines and schedulers arrange work around that cycle. They can change when an operation runs or how long it waits for data. The instruction cycle is the starting point; each machine explains which arrangement it models.
The machine for this idea on its own is Stored Program, if you would rather press it than read about it.
The next instruction starts before this one finishes
1 One instruction, four stages, one at a time
Four stages: fetch, decode, execute, write. One instruction at a time means every instruction pays for all four before the next one starts, so five instructions cost twenty cycles and three quarters of the machine is idle at any moment.
2 The next one starts before this one finishes
Overlapped, each stage takes a new instruction as soon as it hands the last one on. The first answer arrives no sooner; everything after it arrives one cycle apart, which is the whole gain.
3 An instruction that needs a value nobody has written yet
Now make one instruction read a register the one before it is still computing. It cannot decode until that value exists, so it waits, and everything behind it waits too. Switch the dependency on and watch the bubble appear.
4 The speedup, which is never the number of stages
Speedup is the serial time over the pipelined time. It approaches the number of stages only when the pipe is long, full, and never stalls, and one of those is never true. These ran in this browser when the page loaded.
| measure | value |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| overlapping the same work costs fewer cycles | yes | 20 cycles one at a time, 8 overlapped |
| and the speedup is less than the number of stages, with no stall at all | yes | 2.50 against 4 stages |
| one instruction on its own gains nothing | yes | 4 cycles either way |
| an instruction waiting on the one in front of it costs cycles | yes | 8 cycles clean, 10 with the dependency |
| forwarding out of execute recovers some of the stall but not all, because operands are read at decode in these four stages | yes | 10 waiting, 9 forwarded, 8 if it had never depended |
| a longer run gets closer to the stage count, and still never reaches it | yes | 2.29 over 4 instructions, 3.72 over 40 |
What is real here, and what is not
Four stages, because a picture needs a number
Stretch did not have four stages in the sense drawn here. Its lookahead fetched and decoded several instructions in flight with a structure considerably less tidy than a row of four boxes, and later machines went to five, then to a dozen and more. Four is the teaching shape, and this page uses it because the argument about stalls does not depend on the depth.
One hazard, the easy one, and forwarding that does not quite finish the job
The only dependency modelled is a value not yet written: one instruction reads what the instruction ahead is still computing. Not modelled: branches and what they cost when predicted wrong, memory that does not answer in one cycle, two instructions wanting the same unit, out-of-order issue, or anything that reorders work to hide a stall. Each of those is a bigger subject than this page. And the residual stall this page shows after forwarding is an assumption of these four stages, not a law. Operands are read at decode here, so a value forwarded out of execute arrives one cycle late. The canonical five-stage teaching pipeline reads its operands into execute and forwards execute to execute, which removes an arithmetic dependency's stall entirely. The dependency forwarding cannot remove in that pipeline is load-use, where the value is not known until after memory, and that is one this page does not model at all.
Cycles, not seconds
Every number here is a count of cycles, and a cycle is not a fixed amount of time. Pipelining a machine usually lets the clock run faster because each stage does less, which is a second gain this page does not model and cannot, because it has no clock.
The speedup is measured, not asserted
The table divides one measured cycle count by another. It is never the number of stages, and the gap between the two is the honest content of the page: the fill and the drain cost you the first and last few cycles even with no stalls at all.
No sound
Nothing here has a duration to hear.
Sources
- IBM's own history of the 7030, called Stretch. Read for this page: it dates the first delivery to Los Alamos to 1961 and describes the look-ahead that let the machine prepare a future instruction while still calculating the present one.
- Computer History Museum, on the surviving Stretch engineering console. Cited for the machine being a real object with a date rather than a diagram.
- Logical Art, the studio this belongs to.