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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Зависимость данных в информатике — это ситуация, в которой очередная команда программы зависит от какой-либо предыдущей команды. В теории компиляции техника обнаружения зависимости называется анализом зависимостей (англ. 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