next up previous

3.2 Pipelines     continued...

There are many possible sources of bubbles in pipelines. Dependencies between instructions are the main cause. For arithmetic pipelines, data dependencies arise when pairs of operations share inputs and outputs. Consider the following two add instructions:

z1 = x1 + y1 
...
z2  =  x2  +  y2

The dependence illustrated previously is x2 = z1, e.g. both operands are the register R2. Other dependencies are z1 = z2 (both instructions write to the same register) and x1 = z2 (the output from the second instruction may overwrite the register before the first has had a chance to read the old value; an unlikely occurrence in a vector machine, but a situation that must be taken into account). Note that the instructions do not have to be consecutive, i.e. there could be intervening instructions. A compiler that checks for dependencies and possibly reorders instructions has to ``look ahead'' in the code by an amount equal to the depth of the pipeline used in the first instruction.

Instruction pipelines, used to speed up the fetch-decode-execute cycle, are also susceptible to bubbles. The most common case here is caused by branch or loop instructions, which are control dependencies. If the pipeline is ``looking ahead'' and fetching instructions it thinks the machine will want to execute, but in fact the machine branches to another location, a bubble is introduced while the fetch stage goes to get the instructions at the new location.