Data dependence: различия между версиями

'''Data dependence''' —''[[зависимость по данным]].''

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

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

(2) in a serial execution of the program, <math>\,S'</math> is executed before <math>\,T'</math>; and

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

The following three types of dependence between the statements <math>\,S</math> and <math>\,T</math> based upon the types of the two references to <math>\,M</math> are considered:

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

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

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