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

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

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

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

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

${displaystyle [I(S_{1})cap O(S_{2})]cup [O(S_{1})cap I(S_{2})]cup [O(S_{1})cap O(S_{2})]eq varnothing }$

куда:

• ${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 на узлы, которые зависят от них.

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

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

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

Рекомендации

1. Джон Л. Хеннесси; Дэвид А. Паттерсон (2003). Компьютерная архитектура: количественный подход (3-е изд.). Морган Кауфманн. ISBN  1-55860-724-2.
2. Cytron, R .; Ferrante, J .; Rosen, B.K .; Wegman, M. N .; Задек, Ф. К. (1989-01-01). «Эффективный метод вычисления статической единой формы назначения». Материалы 16-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования. ПОПЛ '89. Нью-Йорк, Нью-Йорк, США: ACM: 25–35. Дои:10.1145/75277.75280. ISBN  0897912942.