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

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

Описание

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

\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

где:

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

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

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

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

Типы

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

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

1. A = 3
2. B = A
3. C = B

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

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

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

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

1. B = 3
2. A = B + 1
3. B = 7

Пример:

 MUL R3,R1,R2
 ADD R2,R5,R6

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

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

1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7

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

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

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

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

1. B = 3
2. A = B + 1
3. B = 7

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

1. B2 = 3
2. A = B2 + 1
3. B = 7

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

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

[1]