Editing Pipeline (computing) (section)

=== Dependencies between items ===
In some applications, the processing of an item Y by a stage A may depend on the results or effect of processing a previous item X by some later stage B of the pipeline. In that case, stage A cannot correctly process item Y until item X has cleared stage B.

This situation occurs very often in instruction pipelines. For example, suppose that Y is an arithmetic instruction that reads the contents of a register that was supposed to have been modified by an earlier instruction X. Let A be the stage that fetches the instruction [[operand]]s, and B be the stage that writes the result to the specified register.  If stage A tries to process instruction Y before instruction X reaches stage B, the register may still contain the old value, and the effect of Y would be incorrect.

In order to handle such conflicts correctly, the pipeline must be provided with extra circuitry or logic that detects them and takes the appropriate action. Strategies for doing so include:
* '''Stalling:''' Every affected stage, such as A, is halted until the dependency is resolved—that is, until the required information is available and/or the required state has been achieved.
* '''Reordering items:''' Instead of stalling, stage A may put item Y aside and look for any subsequent item Z in its input stream that does not have any dependencies pending with any earlier item. In instruction pipelines, this technique is called [[out-of-order execution]].
* '''Guess and backtrack:''' One important example of item-to-item dependency is the handling of a [[conditional branch]] instruction X by an instruction pipeline. The first stage A of the pipeline, that fetches the next instruction Y to be executed, cannot perform its task until X has fetched its operand and determined whether the branch is to be taken or not. That may take many clock cycles, since the operand of X may in turn depend on previous instructions that fetch data from main memory.
: Rather than halt while waiting for X to be finished, stage A may guess whether the branch will be taken or not, and fetch the next instruction Y based on that guess. If the guess later turns out to be incorrect (hopefully rarely), the system would have to backtrack and resume with the correct choice. Namely, all the changes that were made to the machine's state by stage A and subsequent stages based on that guess would have to be undone, the instructions following X already in the pipeline would have to be flushed, and stage A would have to restart with the correct [[instruction pointer]]. This [[branch prediction]] strategy is a special case of [[speculative execution]].