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.

Uses your system voice; voice and rate in settings.

≈ 8 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

  • 2.1.2 Write after read (WAR)
  • 2.1.3 Write after write (WAW)
  • 2.2 True dependency (read-after-write)
  • 2.3 Anti-dependency (write-after-read)
  • 2.4 Output dependency (write-after-write)
  • 3 Implications
  • 4 Relevance in computing
  • 5 See also
  • 6 References
  • Description

    edit edit source

    Assuming statement S1 and S2, S2 depends on S1 if:

    [I(S1)∩O(S2)]∪[O(S1)∩I(S2)]∪[O(S1)∩O(S2)]≠∅

    where:

    • I(Si) is the set of memory locations read by Si,
    • O(Sj) is the set of memory locations written by Sj, and
    • there is a feasible run-time execution path from S1 to S2.

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

    Three cases exist:

    • Anti-dependence: I(S1)∩O(S2)≠∅, S1→S2 and S1 reads something before S2 overwrites it
    • Flow (data) dependence: O(S1)∩I(S2)≠∅, S1→S2 and S1 writes before something read by S2
    • Output dependence: O(S1)∩O(S2)≠∅, S1→S2 and both write the same memory location.

    Types

    edit edit source

    Data hazards

    edit edit source

    Data hazards occur when instructions that exhibit data dependence modify data in different stages of a pipeline. Ignoring potential data hazards can result in race conditions (also termed race hazards). There are three situations in which a data hazard can occur:

    1. read after write (RAW), a true dependency
    2. write after read (WAR), an anti-dependency
    3. write after write (WAW), an output dependency
    4. read after read (RAR), a false dependency

    Read after read (RAR) is not a hazard case.

    Consider two instructions i1 and i2, with i1 occurring before i2 in program order.

    Read after write (RAW)

    edit edit source

    ( i2 tries to read a source before i1 writes to it) A read after write (RAW) data hazard refers to a situation where an instruction refers to a result that has not yet been calculated or retrieved. This can occur because even though an instruction is executed after a prior instruction, the prior instruction has been processed only partly through the pipeline.

    Example edit edit source

    For example:

    i1. R2 <- R5 + R8 i2. R4 <- R2 + R8

    The first instruction is calculating a value to be saved in register R2, and the second is going to use this value to compute a result for register R4. However, in a pipeline, when operands are fetched for the 2nd operation, the results from the first have not yet been saved, and hence a data dependency occurs.

    A data dependency occurs with instruction i2, as it is dependent on the completion of instruction i1.

    Write after read (WAR)

    edit edit source

    ( i2 tries to write a destination before it is read by i1) A write after read (WAR) data hazard represents a problem with concurrent execution.

    Example edit edit source

    For example:

    i1. R4 <- R1 + R5 i2. R5 <- R1 + R2

    In any situation with a chance that i2 may finish before i1 (i.e., with concurrent execution), it must be ensured that the result of register R5 is not stored before i1 has had a chance to fetch the operands.

    Write after write (WAW)

    edit edit source

    ( i2 tries to write an operand before it is written by i1) A write after write (WAW) data hazard may occur in a concurrent execution environment.

    Example edit edit source

    For example:

    i1. R5 <- R4 + R7 i2. R5 <- R1 + R3

    The write back (WB) of i2 must be delayed until i1 finishes executing.

    True dependency (read-after-write)

    edit edit source

    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]

    Anti-dependency (write-after-read)

    edit edit source

    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.

    Note that there is still a read-after-write dependency: instruction 2 is truly dependent on instruction N, which is truly dependent upon instruction 1. This dependency existed in the original version, where instruction 2 was truly dependent on instruction 1. This dependency cannot be safely removed.[2]

    Output dependency (write-after-write)

    edit edit source

    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

    Implications

    edit edit source

    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.

    Relevance in computing

    edit edit source

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

    Processor design

    edit edit source
    • 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.

    Compiler construction

    edit edit source

    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.

    See also

    edit edit source

    References

    edit edit source
    1. ^ Bernstein, Arthur J. (1 October 1966). "Analysis of Programs for Parallel Processing". IEEE Transactions on Electronic Computers. EC-15 (5): 757–763. doi:10.1109/PGEC.1966.264565. Wikipedia revision 1310777676, retrieved 2026-11-22
    2. ^ a b John L. Hennessy; David A. Patterson (2003). Computer Architecture: a quantitative approach (3rd ed.). Morgan Kaufmann. ISBN 1-55860-724-2.{{cite book}}: CS1 maint: multiple names: authors list (link) Wikipedia revision 1310777676, retrieved 2026-11-22

    Text derived from https://en.wikipedia.org/w/index.php?oldid=1310777676 under CC BY-SA 4.0; modifications have been made.

    Words in each sectionTypesTypesTypes: 902 words902Relevance in computingRelevance in computingRelevance in computing: 227 words227DescriptionDescriptionDescription: 124 words124ImplicationsImplicationsImplications: 86 words86See alsoSee alsoSee also: 17 words17
    Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

    Provenance

    snapshot enwiki-001310777676 · captured 2025-09-11 · ledger · version history

    Cite this page as: encyclopegia.org, “Data dependency”, snapshot enwiki-001310777676. https://encyclopegia.org/a/data-dependency