Data dependency

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. There are three types of dependencies: data, name, and control. Assuming statement and , depends on if: where: is the set of memory locations read by is the set of memory locations written by and there is a feasible run-time execution path from to This Condition is called Bernstein Condition, named by A. J. Bernstein. Three cases exist: Anti-dependence: , and reads something before overwrites it Flow (data) dependence: , and writes before something read by Output dependence: , and both write the same memory location. 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.

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. An anti-dependency, also known as write-after-read (WAR), occurs when an instruction requires a value that is later updated. 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.
4. B = 3
5. A = B + 1
6. 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.