Data dependency

From Wikipedia, the free encyclopedia

It has been suggested that the section Dependencies from the article Instruction level parallelism be merged into this article or section. (Discuss)

A data dependency in computer science is a situation whereby computer instructions refer to the results of preceding instructions that have not yet been completed. This can also be known as a data hazard. Ignoring data dependencies can result in race conditions. The area dealing with data dependencies is called Dependence analysis.

1 Examples of Data Dependencies
2 Solutions

[edit] Examples of Data Dependencies

There are three types of data hazards or data dependencies:

RAW - Read After Write
WAR - Write After Read
WAW - Write After Write

[edit] RAW - Read After Write

A RAW Data Hazard refers to a situation where we refer to a result that has not yet been calculated, for example:

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

The 1st instruction is calculating a value to be saved in register 2, and the second is going to use this value to compute a result for register 4. However, in a pipeline, when we fetch the operands for the 2nd operation, the results from the 1st will not yet have been saved, and hence we have a data dependency.

We say that there is a data dependency with instruction 2, as it is dependent on the completion of instruction 1

[edit] WAR - Write After Read

A WAR Data Hazard represents a problem with concurrent execution, for example:

i1. r1 <- r2 + r3 i2. r3 <- r4 x r5

If we are in a situation that there is a chance that i2 may be completed before i1 (i.e. with concurrent execution) we must ensure that we do not store the result of register 3 before i1 has had a chance to fetch the operands.

[edit] WAW - Write After Write

A WAW Data Hazard is another situation which may occur in a Concurrent execution environment, for example:

i1. r2 <- r1 + r3 i2. r2 <- r4 x r7

We must delay the WB (Write Back) of i2 until the execution of i1

[edit] Solutions

We can delegate the task of removing data dependencies to the compiler, which can fill in an appropriate number of NOP instructions between dependent instructions to ensure correct operation, or re-order instructions where possible.

Other methods include on-chip solutions such as: