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

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

Описание

Предполагая утверждение и , зависит от того, если: ${\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}}$

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

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

• Антизависимость: считывает что-то , прежде чем перезаписать его. ${\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. Поэтому параллелизм на уровне инструкций в этом примере невозможен. ^[1]

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

Антизависимость возникает, когда инструкция требует значения, которое позже обновляется. Нарушение антизависимости приводит к опасности записи после чтения (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. Поскольку эти новые зависимости являются зависимостями потока, эти новые зависимости невозможно безопасно удалить. ^[1]

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

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

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

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

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

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

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

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

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

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

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

Дизайн процессора

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

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

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

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

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

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

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

1. Джон Л. Хеннесси ; Дэвид А. Паттерсон (2003). Компьютерная архитектура: количественный подход (3-е изд.) . Морган Кауфманн . ISBN 1-55860-724-2.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )