Data dependency: Difference between revisions

Revision as of 11:05, 22 January 2024

Revision as of 11:27, 22 January 2024

Line 1:

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]].

== Description ==

There are three types of dependencies: data, name, and control.

== Data dependencies ==

Assuming statement <math>S_1</math> and <math>S_2</math>, <math>S_2</math> depends on <math>S_1</math> if:

Line 15 ⟶ 13:

* there is a feasible run-time execution path from <math>S_1</math> to {{nobr|1=<math>S_2</math>.}}

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

Three cases exist:

Line 23 ⟶ 21:

* Output dependence: <math>O(S_1) \cap O(S_2) \neq \varnothing</math>, <math>S_1 \rightarrow S_2</math> and both write the same memory ___location.

== Types ==

=== Flow dependency (True dependency) ===

=== FlowTrue dependency (True dependencyread-after-write) ===

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

A Flowtrue dependency, also known as a data'''flow''' '''dependency''' or true'''data dependency or read-after-write (RAW)''', 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

Line 31:

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.<ref name="architecture">{{cite book | author=[[John L. Hennessy]]; [[David A. Patterson (scientist)|David A. Patterson]] | title=Computer Architecture: a quantitative approach (3rd ed.) | publisher=[[Morgan Kaufmann]] | year=2003 | isbn=1-55860-724-2}}</ref>

<ref name="architecture">{{cite book | author=[[John L. Hennessy]]; [[David A. Patterson (scientist)|David A. Patterson]] | title=Computer Architecture: a quantitative approach (3rd ed.) | publisher=[[Morgan Kaufmann]] | year=2003 | isbn=1-55860-724-2}}</ref>

=== Anti-dependency (write-after-read) ===

An anti-dependency, also known as write-after-read (WAR), occurs when an instruction requires a value that is later updated. A violation of an anti-dependency leads to an '''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

Line 42 ⟶ 43:

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.

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:

Line 56:

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.<ref name="architecture"/>

<ref name="architecture"/>

=== Output dependency (write-after-write) ===

An output dependency, also known as write-after-write (WAW), 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

Line 67 ⟶ 68:

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

A commonly used naming convention for data dependencies is the following: Read-after-Write or RAW (flow dependency), Write-After-Read or WAR (anti-dependency), or Write-after-Write or WAW (output dependency).

<ref name="architecture"/>

==Implications==