Зависимость от данных - Data dependency

А зависимость данных в Информатика это ситуация, в которой оператор программы (инструкция) относится к данным предыдущего оператора. В теория компилятора метод, используемый для обнаружения зависимостей данных между операторами (или инструкциями), называется анализ зависимости.

Есть три типа зависимостей: данные, имя и контроль.

Зависимости данных

Предполагая заявление ${displaystyle S_ {1}}$ и ${displaystyle S_ {2}}$ , ${displaystyle S_ {2}}$ зависит от ${displaystyle S_ {1}}$ если:

${displaystyle [I (S_ {1}) крышка O (S_ {2})] чашка [O (S_ {1}) крышка I (S_ {2})] чашка [O (S_ {1}) крышка O (S_ {2})] эквар. Ничего}$

куда:

${displaystyle I (S_ {i})}$ набор ячеек памяти, читаемых ${displaystyle S_ {i}}$ и
${displaystyle O (S_ {j})}$ это набор ячеек памяти, записанных ${displaystyle S_ {j}}$
и существует возможный путь выполнения во время выполнения от ${displaystyle S_ {1}}$ к ${displaystyle S_ {2}}$

Это Условие называется Условием Бернштейна, названным А. Дж. Бернштейном.

Существуют три случая:

Анти-зависимость: ${displaystyle I (S_ {1}) cap O (S_ {2}) eq varnothing}$ , ${displaystyle S_ {1} ightarrow S_ {2}}$ и ${displaystyle S_ {1}}$ читает что-то перед ${displaystyle S_ {2}}$ перезаписывает это
Зависимость от потока (данных): ${displaystyle O (S_ {1}) cap I (S_ {2}) eq varnothing}$ , ${displaystyle S_ {1} ightarrow S_ {2}}$ и ${displaystyle S_ {1}}$ пишет перед тем, как что-то прочитает ${displaystyle S_ {2}}$
Выходная зависимость: ${displaystyle O (S_ {1}) cap O (S_ {2}) eq varnothing}$ , ${displaystyle S_ {1} ightarrow S_ {2}}$ и оба записывают одну и ту же ячейку памяти.

Зависимость потока (Истинная зависимость)

Зависимость потока, также известная как зависимость данных или истинная зависимость, или чтение после записи (RAW), возникает, когда инструкция зависит от результата предыдущей инструкции:

1. А = 32. В = А3. C = B

Инструкция 3 действительно зависит от инструкции 2, так как окончательное значение C зависит от обновления инструкции B. Инструкция 2 действительно зависит от инструкции 1, так как окончательное значение B зависит от инструкции обновления A. Поскольку инструкция 3 действительно зависит если инструкция 2 и инструкция 2 действительно зависят от инструкции 1, инструкция 3 также действительно зависит от инструкции 1. Параллелизм на уровне инструкций поэтому не вариант в этом примере.^[1]

Анти-зависимость

Анти-зависимость, также известная как запись после чтения (WAR), возникает, когда инструкция требует значения, которое позже обновляется. В следующем примере инструкция 2 не зависит от инструкции 3 - порядок этих инструкций не может быть изменен, и они не могут выполняться параллельно (возможно, изменение порядка инструкций), так как это повлияет на окончательное значение A.

1. B = 32. A = B + 13. B = 7

Анти-зависимость - это пример зависимость от имени. То есть переименование переменных могло бы удалить зависимость, как в следующем примере:

1. В = 3Н. В2 = В2. А = В2 + 13. В = 7

Новая переменная B2 была объявлена как копия B в новой инструкции N. Анти-зависимость между 2 и 3 удалена, что означает, что теперь эти инструкции могут выполняться параллельно. Однако модификация привела к новой зависимости: теперь инструкция 2 действительно зависит от инструкции N, которая действительно зависит от инструкции 1. Как зависимости потока, эти новые зависимости невозможно безопасно удалить.^[1]

Выходная зависимость

Выходная зависимость, также известная как запись после записи (WAW), возникает, когда порядок инструкций влияет на окончательное выходное значение переменной. В приведенном ниже примере существует выходная зависимость между инструкциями 3 и 1 - изменение порядка инструкций в этом примере приведет к изменению конечного значения A, поэтому эти инструкции не могут выполняться параллельно.

1. B = 32. A = B + 13. B = 7

Как и в случае с анти-зависимостями, выходные зависимости зависимости имен. То есть их можно удалить путем переименования переменных, как в приведенной ниже модификации приведенного выше примера:

1. B2 = 32. A = B2 + 13. B = 7

Обычно используется следующее соглашение об именах для зависимостей данных: чтение после записи или RAW (зависимость потока), запись после чтения или WAR (анти-зависимость) или запись после записи или WAW (зависимость вывода).^[1]

Зависимость управления

Инструкция B имеет управляющую зависимость от предыдущей инструкции A, если результат A определяет, следует ли выполнять B или нет. В следующем примере инструкция ${displaystyle S_ {2}}$ имеет управляющую зависимость от инструкции ${displaystyle S_ {1}}$ . Тем не мение, ${displaystyle S_ {3}}$ не зависит от ${displaystyle S_ {1}}$ потому что ${displaystyle S_ {3}}$ всегда выполняется независимо от результата ${displaystyle S_ {1}}$ .

S1. если (a == b) S2. а = а + bS3. б = а + б

Интуитивно понятно, что между двумя операторами A и B существует управляющая зависимость, если

B может быть выполнен после A
Результат выполнения A будет определять, будет ли выполнено B или нет.

Типичным примером является наличие управляющих зависимостей между условной частью оператора if и операторами в его истинных / ложных телах.

Формальное определение зависимости управления можно представить следующим образом:

Заявление ${displaystyle S_ {2}}$ называется контролем, зависящим от другого утверждения ${displaystyle S_ {1}}$ если только

существует путь ${displaystyle P}$ из ${displaystyle S_ {1}}$ к ${displaystyle S_ {2}}$ так что каждое заявление ${displaystyle S_ {i}}$ ≠ ${displaystyle S_ {1}}$ в ${displaystyle P}$ за ним последует ${displaystyle S_ {2}}$ в каждом возможном пути до конца программы и
${displaystyle S_ {1}}$ не обязательно будет сопровождаться ${displaystyle S_ {2}}$ , т.е. есть путь выполнения из ${displaystyle S_ {1}}$ до конца программы, которая не проходит ${displaystyle S_ {2}}$ .

Выраженные с помощью (пост) доминирования, эти два условия эквивалентны

${displaystyle S_ {2}}$ пост-доминирует над всеми ${displaystyle S_ {i}}$
${displaystyle S_ {2}}$ не доминирует ${displaystyle S_ {1}}$

Построение управляющих зависимостей

Управляющие зависимости по сути граница господства в обратном графике график потока управления (CFG).^[2] Таким образом, одним из способов их построения было бы построить границу пост-доминирования CFG, а затем обратить ее, чтобы получить график зависимостей управления.

Ниже приводится псевдокод для построения границы пост-доминирования:

для каждого X в восходящем обходе дерева доминаторов выполните: PostDominanceFrontier (X) ← ∅ для каждого Y ∈ Predecessors (X) do: if momentPostDominator (Y) ≠ X: то PostDominanceFrontier (X) ← PostDominanceFrontier (X) ∪ {Y} сделано для каждого Z ∈ Children (X) do: для каждого Y ∈ PostDominanceFrontier (Z) do: if momentPostDominator (Y) ≠ X: то PostDominanceFrontier (X) ← PostDominanceFrontier (X) ∪ {Y} сделано сделано

Здесь Children (X) - это набор узлов в CFG, над которыми пост-доминирует X, а Predecessors (X) - это набор узлов в CFG, которые непосредственно предшествуют X в CFG.

После того, как карта границ пост-доминирования вычислена, ее реверсирование приведет к отображению узлов в CFG на узлы, которые зависят от них.

Подразумеваемое

Обычные программы пишутся с учетом модель последовательного выполнения. Согласно этой модели, инструкции выполняются одна за другой, атомарно (то есть в любой данный момент времени выполняется только одна инструкция) и в порядке, заданном программой.

Однако зависимости между операторами или инструкциями могут препятствовать параллелизму - параллельному выполнению нескольких инструкций либо распараллеливающим компилятором, либо процессором, использующим параллелизм на уровне инструкций. Неосторожное выполнение нескольких инструкций без учета связанных зависимостей может вызвать опасность получения неверных результатов, а именно: опасности.