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

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

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

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

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

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

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

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

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

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

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

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

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

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

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