The Pipeline
Stretch reached Los Alamos in April 1961 fetching and decoding instructions ahead of the one being executed. The diagram of four stages marching along is everywhere; what it usually leaves out is 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.
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 the value early recovers some of it but not all | 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, and the easy one
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.
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.