Data dependency

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Data dependency" – news · newspapers · books · scholar · JSTOR (September 2024) (Learn how and when to remove this message)

A data dependency in computer science is a situation in which a program statement (instruction) refers to the data of a preceding statement. In compiler theory, the technique used to discover data dependencies among statements (or instructions) is called dependence analysis.

Assuming statement ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$, ${\displaystyle S_{2}}$ depends on ${\displaystyle S_{1}}$ if:

${\displaystyle \left[I(S_{1})\cap O(S_{2})\right]\cup \left[O(S_{1})\cap I(S_{2})\right]\cup \left[O(S_{1})\cap O(S_{2})\right]\neq \varnothing }$

where:

• ${\displaystyle I(S_{i})}$ is the set of memory locations read by ${\displaystyle S_{i}}$,
• ${\displaystyle O(S_{j})}$ is the set of memory locations written by ${\displaystyle S_{j}}$, and
• there is a feasible run-time execution path from ${\displaystyle S_{1}}$ to ${\displaystyle S_{2}}$.

These conditions are called Bernstein's Conditions, named after Arthur J. Bernstein.^[1]

Three cases exist:

• Anti-dependence: ${\displaystyle I(S_{1})\cap O(S_{2})\neq \varnothing }$, ${\displaystyle S_{1}\rightarrow S_{2}}$ and ${\displaystyle S_{1}}$ reads something before ${\displaystyle S_{2}}$ overwrites it
• Flow (data) dependence: ${\displaystyle O(S_{1})\cap I(S_{2})\neq \varnothing }$, ${\displaystyle S_{1}\rightarrow S_{2}}$ and ${\displaystyle S_{1}}$ writes before something read by ${\displaystyle S_{2}}$
• Output dependence: ${\displaystyle O(S_{1})\cap O(S_{2})\neq \varnothing }$, ${\displaystyle S_{1}\rightarrow S_{2}}$ and both write the same memory location.

It has been suggested that Hazard (computer architecture)#Data hazards be merged into this section. (Discuss) Proposed since August 2024.

A true dependency, also known as a flow dependency or data dependency, occurs when an instruction depends on the result of a previous instruction. A violation of a true dependency leads to a read-after-write (RAW) hazard.

1. A = 3
2. B = A
3. C = B

Instruction 3 is truly dependent on instruction 2, as the final value of C depends on the instruction updating B. Instruction 2 is truly dependent on instruction 1, as the final value of B depends on the instruction updating A. Since instruction 3 is truly dependent upon instruction 2 and instruction 2 is truly dependent on instruction 1, instruction 3 is also truly dependent on instruction 1. Instruction level parallelism is therefore not an option in this example.^[2]

An anti-dependency occurs when an instruction requires a value that is later updated. A violation of an anti-dependency leads to a write-after-read (WAR) hazard.

In the following example, instruction 2 anti-depends on instruction 3 — the ordering of these instructions cannot be changed, nor can they be executed in parallel (possibly changing the instruction ordering), as this would affect the final value of A.

1. B = 3
2. A = B + 1
3. B = 7

Example:

 MUL R3,R1,R2
 ADD R2,R5,R6

It is clear that there is anti-dependence between these 2 instructions. At first we read R2 then in second instruction we are Writing a new value for it.

An anti-dependency is an example of a name dependency. That is, renaming of variables could remove the dependency, as in the next example:

1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7

A new variable, B2, has been declared as a copy of B in a new instruction, instruction N. The anti-dependency between 2 and 3 has been removed, meaning that these instructions may now be executed in parallel. However, the modification has introduced a new dependency: instruction 2 is now truly dependent on instruction N, which is truly dependent upon instruction 1. As flow dependencies, these new dependencies are impossible to safely remove.^[2]

An output dependency occurs when the ordering of instructions will affect the final output value of a variable. A violation of an output dependency leads to an write-after-write (WAW) hazard.

In the example below, there is an output dependency between instructions 3 and 1 — changing the ordering of instructions in this example will change the final value of A, thus these instructions cannot be executed in parallel.

1. B = 3
2. A = B + 1
3. B = 7

As with anti-dependencies, output dependencies are name dependencies. That is, they may be removed through renaming of variables, as in the below modification of the above example:

1. B2 = 3
2. A = B2 + 1
3. B = 7

Conventional programs are written assuming the sequential execution model. Under this model, instructions execute one after the other, atomically (i.e., at any given point in time, only one instruction is executed) and in the order specified by the program.

However, dependencies among statements or instructions may hinder parallelism — parallel execution of multiple instructions, either by a parallelizing compiler or by a processor exploiting instruction-level parallelism. Recklessly executing multiple instructions without considering related dependences may cause danger of getting wrong results, namely hazards.

Data dependencies are relevant in various areas of computing, particularly in processor design, compiler construction, parallel computing, and concurrent programming.

• Instruction pipelining: In pipelined processors, multiple instruction are executed in parallel in multiple pipeline stages. Thereby, data dependencies between registers must be respected and handled in the processor pipeline. Most relevant are true dependencies that are resolved e.g. by stalling the pipeline or operand forwarding.
• Out-of-order execution: Modern processors often execute instructions out of their original order to improve performance. Thereby, name dependencies between registers must be respected (in addition to data dependencies) and are resolved e.g. by register renaming or scoreboarding. Data dependencies are also relevant for memory accesses and must be respected by memory disambiguation techniques that execute memory access instructions (loads and stores) out of program order.

Data dependencies are relevant for various compiler optimizations, e.g.

• Instruction scheduling: Compilers must schedule instructions in a way that respects data dependencies. This is crucial in optimizing compilers that rearrange code for better performance.
• Loop transformations: In optimizing loops, compilers need to consider data dependencies to apply transformations like loop unrolling, fusion, or tiling without changing the semantics of the program.
• Code motion: When a compiler considers moving a piece of code, it must ensure that data dependencies are not violated.

• Dependency analysis
• Control dependency
• Loop dependence analysis § Data dependence
• Hazard (computer architecture) § Data hazards