Data dependency

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}}$.

This Condition is called Bernstein Condition, named by A. J. Bernstein.

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.

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

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

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

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

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

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

An instruction B has a control dependency on a preceding instruction A if the outcome of A determines whether B should be executed or not. In the following example, the instruction ${\displaystyle S_{2}}$ has a control dependency on instruction ${\displaystyle S_{1}}$. However, ${\displaystyle S_{3}}$ does not depend on ${\displaystyle S_{1}}$ because ${\displaystyle S_{3}}$ is always executed irrespective of the outcome of ${\displaystyle S_{1}}$.

S1.         if (a == b)
S2.             a = a + b
S3.         b = a + b

Intuitively, there is control dependence between two statements A and B if

• B could be possibly executed after A
• The outcome of the execution of A will determine whether B will be executed or not.

A typical example is that there are control dependences between the condition part of an if statement and the statements in its true/false bodies.

A formal definition of control dependence can be presented as follows:

A statement ${\displaystyle S_{2}}$ is said to be control dependent on another statement ${\displaystyle S_{1}}$ iff

• there exists a path ${\displaystyle P}$ from ${\displaystyle S_{1}}$ to ${\displaystyle S_{2}}$ such that every statement ${\displaystyle S_{i}}$ ≠ ${\displaystyle S_{1}}$ within ${\displaystyle P}$ will be followed by ${\displaystyle S_{2}}$ in each possible path to the end of the program and
• ${\displaystyle S_{1}}$ will not necessarily be followed by ${\displaystyle S_{2}}$, i.e. there is an execution path from ${\displaystyle S_{1}}$ to the end of the program that does not go through ${\displaystyle S_{2}}$.

Expressed with the help of (post-)dominance the two conditions are equivalent to

• ${\displaystyle S_{2}}$ post-dominates all ${\displaystyle S_{i}}$
• ${\displaystyle S_{2}}$ does not post-dominate ${\displaystyle S_{1}}$

for each X in a bottom-up traversal of the post-dominator tree do:
    PostDominanceFrontier(X) ← ∅
    for each Y ∈ Predecessors(X) do:
        if immediatePostDominator(Y) ≠ X:
            then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
    done
    for each Z ∈ Children(X) do:
        for each Y ∈ PostDominanceFrontier(Z) do:
            if immediatePostDominator(Y) ≠ X:
                then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
        done
    done
done

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.

In 2016, Edgard Marx, a computer scientist from Leipzig University, coined the term Data Dependency Management[3] to refer to the systems that deal with the management of data. Data Dependency Management systems are designed to facilitate the deployment and management of data on the cloud, personal computers, or smart devices (edge). Data Dependency Management frameworks can be used to describe how the data was conceived, licensing as well as its dependencies. The concept of data dependency management comes from software package dependency management tools such as npm for JavaScript, gem for Ruby, and NuGet for .NET. Their rationale is to allow users to manage the software dependency on data, such as machine learning models for data-driven applications. They are useful to publish, locate, and install data packages. A typical example of a data dependency management frameworks are Hugging Face, KBox,[4] among others.