Data dependence

Материал из WikiGrapp
Перейти к:навигация, поиск

Data dependence --- зависимость по данным.

In general terms, a statement T depends on a statement S, denoted by S \delta T, if there exist an instance S' of S, an instance T' of T, and a memory location M, such that the following properties hold:

(1) both S' and T' are references to M, and at least one of those references is a write;

(2) in a serial execution of the program, S' is executed before T'; and

(3) in the same execution, M is not written between the time S' finishes and the time T' starts.

The following three types of dependence between the statements S and T based upon the types of the two references to M are considered:


(1) T is flow (true) dependent on S, (S \delta T), if S' writes to M and then T' reads it.

(2) T is anti-dependent on S, (S \bar{\delta} T), if S' reads M and then T' writes to it.

(3) T is output dependent on S, (S \delta^{o} T), if S' writes to M and then T' writes to it again.