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

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

Существует три типа зависимостей: зависимости по данным, зависимости по именам и зависимости по управлению.^[1]

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

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

• команда 1 создает выходные данные, которые использует команда 2
• команда 2 зависит по данным от какой-либо команды 3, которая в свою очередь является зависимой по данным от команды 1

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

Зависимости по именам

Следующий тип зависимостей — зависимости по именам. Эти зависимости возникают при использовании командами одного и того же имени (регистра, ячейки памяти), но при отсутствии передачи данных между командами. Можно выделить два типа зависимости по именам между командами 1 и 2:

• Антизависимость — возникает, если команда 2 записывает в ячейку памяти, которую команда 1 считывает, и команда 1 выполняется первой.
• Зависимость по выходу — возникает, когда команда 1 и команда 2 пишут результат в одну и ту же ячейку памяти. Порядок выполнения этих команд должен сохраняться.

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

Зависимости по управлению

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

Имеются два ограничения, связанные с зависимостями по управлению:

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

Ссылки

1. ↑ John L. Hennessy; David A. Patterson Computer Architecture: a quantitative approach (3rd ed.). — Morgan Kaufmann, 2003. — ISBN 1-55860-724-2