next up previous

3.2 Pipelines     continued...

It should be apparent that in the general case a pipeline of depth d can process n items in n + d steps when there are no bubbles. Without a pipeline, each application of the basic function would require d cycles, and they would have to be executed sequentially, for a total time of cycles. The speedup obtained by a full pipeline is thus

When we can safely ignore the d in the denominator, so the asymptotic speedup, observed for large n, is a factor of d. For example, suppose we want to add 1000 pairs of numbers, e.g. when adding two 1000-element vectors. If it takes 5 cycles for each addition, a machine without a pipelined adder would require 5000 cycles. With our 5-stage pipelined adder, the last sum will appear after cycles, so the pipeline is times faster. Providing a steady stream of independent operands that will keep a pipeline full is the distinguishing feature of a vector processor, which can initiate such a series of operations with a single instruction.