Зависимость данных в информатике — это ситуация, в которой очередная команда программы зависит от какой-либо предыдущей команды. В теории компиляции техника обнаружения зависимости называется анализом зависимостей.
Существует три типа зависимостей: зависимости по данным, зависимости по именам и зависимости по управлению.[1]
Зависимости по данным
Будем говорить, что команда 2 зависит по данным от команды 1, если выполняется хотя бы одно из следующих условий:
- команда 1 создает выходные данные, которые использует команда 2
- команда 2 зависит по данным от какой-либо команды 3, которая в свою очередь является зависимой по данным от команды 1
Если команды зависимы по данным, то они не могут выполняться одновременно. Одновременное выполнение этих команд требует создания некоторой машины с внутренними схемами блокировок конвейера, обеспечивающих устранение перекрытия. В машине без внутренних блокировок, компилятор не может спланировать зависимые команды так, чтобы они полностью совмещались. В противном случае программа не будет выполняться правильно.
Зависимости по именам
Следующий тип зависимостей — зависимости по именам. Эти зависимости возникают при использовании командами одного и того же имени (регистра, ячейки памяти), но при отсутствии передачи данных между командами. Можно выделить два типа зависимости по именам между командами 1 и 2:
- Антизависимость — возникает, если команда 2 записывает в ячейку памяти, которую команда 1 считывает, и команда 1 выполняется первой.
- Зависимость по выходу — возникает, когда команда 1 и команда 2 пишут результат в одну и ту же ячейку памяти. Порядок выполнения этих команд должен сохраняться.
Эти два типа зависимостей являются зависимостями по именам, так как в отличие от зависимости по данным, в них отсутствует передача данных от одной команды к другой. Значит команды, связанные зависимостью по именам, могут выполняться вместе, если имя ячейки памяти, используемое в командах, изменяется так, что команды не конфликтуют. Переименование регистров может выполняться статически компилятором, а также динамически аппаратными средствами.
Зависимости по управлению
Последний тип зависимостей — зависимости по управлению. Они определяют порядок команд по отношению к команде условного перехода. В результате чего команды, не являющиеся командами перехода, выполняются только когда они должны выполняться. Каждая команда в программе является зависимой по управлению от некоторого набора условных переходов. В общем случае, эти зависимости по управлению должны сохраняться.
Имеются два ограничения, связанные с зависимостями по управлению:
- Зависящая по управлению команда, не может быть в результате перемещения поставлена перед командой условного перехода, стать независимой от него.
- Команда, не зависимая по управлению от команды условного перехода, не может быть поставлена после команды условного перехода так, что её выполнение станет управляться этим условным переходом.
См. также
Примечания
- ↑ John L. Hennessy; David A. Patterson. Computer Architecture: a quantitative approach (3rd ed.) (англ.). — Morgan Kaufmann, 2003. — ISBN 1-55860-724-2.
Эта страница в последний раз была отредактирована 29 мая 2022 в 14:19.
Обычно почти сразу, изредка в течении часа.