Data dependence

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

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

(1) both [math]\displaystyle{ \,S' }[/math] and [math]\displaystyle{ \,T' }[/math] are references to [math]\displaystyle{ \,M }[/math], and at least one of those references is a write;

(2) in a serial execution of the program, [math]\displaystyle{ \,S' }[/math] is executed before [math]\displaystyle{ \,T' }[/math]; and

(3) in the same execution, [math]\displaystyle{ \,M }[/math] is not written between the time [math]\displaystyle{ \,S' }[/math] finishes and the time [math]\displaystyle{ \,T' }[/math] starts.

The following three types of dependence between the statements [math]\displaystyle{ \,S }[/math] and [math]\displaystyle{ \,T }[/math] based upon the types of the two references to [math]\displaystyle{ \,M }[/math] are considered:

(1) [math]\displaystyle{ \,T }[/math] is flow (true) dependent on [math]\displaystyle{ \,S }[/math], ([math]\displaystyle{ \,S \delta T }[/math]), if [math]\displaystyle{ \,S' }[/math] writes to [math]\displaystyle{ \,M }[/math] and then [math]\displaystyle{ \,T' }[/math] reads it.

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

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

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.