Data dependence: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Data dependence''' --- зависимость по данным. In general terms, a statement <math>T</math> '''depends''' on a statement <math>S</math>, denot…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Data dependence''' | '''Data dependence''' —''[[зависимость по данным]].'' | ||
In general terms, a statement <math>T</math> '''depends''' on a statement <math>S</math>, denoted | 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: | ||
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 | (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''; | ||
references is a ''write''; | |||
(2) in a serial execution of the program, <math>S'</math> is executed before <math>T'</math>; | (2) in a serial execution of the program, <math>\,S'</math> is executed before <math>\,T'</math>; and | ||
and | |||
(3) in the same execution, <math>M</math> is not written between the time <math>S'</math> | (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. | ||
finishes and the time <math>T'</math> starts. | |||
The following three types of dependence between the statements <math>S</math> and <math>T</math> | 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: | ||
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 | (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. | ||
<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> | (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. | ||
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> | (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. | ||
and then <math>T'</math> writes to it again. | |||
==Литература== | |||
*Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
[[Категория:Основные термины]] | |||
Текущая версия от 13:13, 27 ноября 2024
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.