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

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

Описание

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

${\displaystyle \left[I(S_{1})\cap O(S_{2})\right]\cup \left[O(S_{1})\cap I(S_{2})\right]\cup \left[O(S_{1})\cap O(S_{2})\right]\neq \varnothing }$

где:

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

Эти условия называются условиями Бернштейна, названными в честь Артура Дж. Бернстайна. ^[1]

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

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

Типы

Истинная зависимость (чтение после записи)

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

1. А = 32. Б = А3. С = В

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

Антизависимость (написание после прочтения)

Антизависимость возникает, когда инструкция требует значение, которое позже обновляется. Нарушение антизависимости приводит к опасности записи после чтения (WAR) .

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

1. В = 32. А = В + 13. В = 7

Пример:

МУЛ R3,R1,R2 ДОБАВИТЬ R2,R5,R6

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

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

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

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

Зависимость вывода (запись после записи)

Выходная зависимость возникает, когда порядок инструкций влияет на конечное выходное значение переменной. Нарушение выходной зависимости приводит к опасности записи после записи (WAW) .

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

1. В = 32. А = В + 13. В = 7

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

1. В2 = 32. А = В2 + 13. В = 7

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

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

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

Актуальность в вычислительной технике

Зависимости данных актуальны в различных областях вычислительной техники, особенно при проектировании процессоров, создании компиляторов, параллельных вычислениях и параллельном программировании.

Конструкция процессора

• Конвейеризация инструкций : в конвейерных процессорах несколько инструкций выполняются параллельно на нескольких этапах конвейера. Таким образом, зависимости данных между регистрами должны соблюдаться и обрабатываться в конвейере процессора. Наиболее важными являются истинные зависимости, которые разрешаются, например, путем остановки конвейера или пересылки операндов .
• Выполнение не по порядку : современные процессоры часто выполняют инструкции не в их изначальном порядке для повышения производительности. Таким образом, зависимости имен между регистрами должны соблюдаться (в дополнение к зависимостям данных) и разрешаться, например, путем переименования регистров или ведения табло . Зависимости данных также важны для доступа к памяти и должны соблюдаться методами устранения неоднозначности памяти , которые выполняют инструкции доступа к памяти (загрузки и сохранения) не в порядке программы.

Конструкция компилятора

Зависимости данных важны для различных оптимизаций компилятора , например:

• Планирование инструкций : Компиляторы должны планировать инструкции таким образом, чтобы учитывать зависимости данных. Это имеет решающее значение для оптимизации компиляторов, которые перестраивают код для лучшей производительности.
• Преобразования циклов : при оптимизации циклов компиляторам необходимо учитывать зависимости данных, чтобы применять преобразования, такие как развертывание цикла, слияние или мозаичное размещение, не изменяя семантику программы.
• Перемещение кода : когда компилятор рассматривает возможность перемещения фрагмента кода, он должен убедиться, что зависимости данных не нарушаются.

Смотрите также

• Анализ зависимости
• Зависимость от контроля
• Анализ зависимости цикла § Зависимость данных
• Опасность (архитектура компьютера) § Опасности данных

Ссылки

1. Бернстайн, Артур Дж. (1 октября 1966 г.). «Анализ программ для параллельной обработки». Труды IEEE по электронным компьютерам . EC-15 (5): 757–763. doi :10.1109/PGEC.1966.264565.
2. Джон Л. Хеннесси ; Дэвид А. Паттерсон (2003). Архитектура компьютера: количественный подход (3-е изд.) . Морган Кауфманн . ISBN 1-55860-724-2.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )