Data dependency in computer science is a situation in which the next program command depends on any previous command. In compilation theory, a dependency detection technique is called .
There are three types of dependencies: data dependencies, name dependencies, and management dependencies. [one]
Content
Data Dependencies
We say that command 2 depends on the data from command 1 if at least one of the following conditions is true:
- command 1 creates the output that command 2 uses
- team 2 depends on the data from any team 3, which in turn is dependent on the data from team 1
If the commands are data dependent, then they cannot be executed at the same time. The simultaneous execution of these commands requires the creation of some machine with internal circuits of conveyor locks, which ensure elimination of overlap. In a machine without internal locks , the compiler cannot plan dependent commands so that they are fully compatible. Otherwise, the program will not run correctly.
Name Dependencies
The next type of dependency is dependency by name . These dependencies arise when teams use the same name ( register , memory location), but in the absence of data transfer between commands. There are two types of dependencies by names between teams 1 and 2:
- Anti - dependency - occurs if command 2 writes to the memory cell that command 1 reads, and command 1 is executed first.
- Dependence on output - occurs when command 1 and command 2 write the result to the same memory location. The execution order of these commands must be maintained.
These two types of dependencies are dependencies by name, because unlike data dependencies, they do not transfer data from one command to another. This means that the commands associated with the dependency by name can be executed together if the name of the memory cell used in the commands is changed so that the commands do not conflict. Renaming registers can be performed statically by the compiler , as well as dynamically by hardware.
Management Dependencies
The final type of dependency is management dependency. They determine the order of the teams relative to the conditional branch command. As a result, commands that are not transition commands are executed only when they should be executed. Each command in the program is dependent on control on a certain set of conditional transitions. In general, these management dependencies should be preserved.
There are two limitations associated with management dependencies:
- A control-dependent command cannot be placed in front of a conditional branch command as a result of a move, become independent of it.
- A command that is independent of control of a conditional branch instruction cannot be delivered after a conditional branch instruction so that its execution will be controlled by this conditional branch.
See also
- Command Level Concurrency
Notes
- β John L. Hennessy ; David A. Patterson . Computer Architecture: a quantitative approach (3rd ed.). - Morgan Kaufmann , 2003. - ISBN 1-55860-724-2 .