Content deleted Content added
Cybercobra (talk | contribs) |
|||
Line 17:
Technically, there is a fourth type, Read after Read (RAR or "Input"): Both instructions read the same ___location. Input dependence does not constrain the execution order of two statements, but it is useful in scalar replacement of array elements.
To make sure we respect the three types of dependencies, we construct a dependency graph, which is a [[directed graph]] where each vertex is an instruction and there is an edge from I<sub>1</sub> to I<sub>2</sub> if I<sub>1</sub> must come before I<sub>2</sub> due to a dependency. If loop-carried dependencies are left out, the dependency graph is a [[directed acyclic graph]]. Then, any [[topological sort]] of this graph is a valid instruction schedule. The edges of the graph are usually labelled with the '''latency''' of the dependence. This is the number of clock cycles that needs to elapse before the pipeline can proceed with the target instruction without stalling.
However, we want more than a valid instruction scheduling: we also want one which minimizes delays. ''Write about how it does this...'' -->
| |||