Прогнозирование ветвлений. Статическое и динамическое.

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

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

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

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

Существует два способа отмены команд. Первый способ — продолжать выполнять команды, вызванные после спрогнозированного условного перехода до тех пор, пока одна из этих команд не попытается изменить состояние машины (например, сохранить значение в регистре). Тогда вместо того, чтобы перезаписывать регистр, нужно поместить вычисленное значение во временный (скрытый) регистр, а затем, когда выяснится, что прогноз был правильным, просто скопировать это значение в обычный регистр. Второй способ — сохранять (например, в скрытом временном регистре) значение любого регистра, который может быть переписан. В результате машина сможет вернуться в предыдущее состояние в случае неправильно спрогнозированного перехода. Реализация обоих подходов очень сложна и требует громоздкой системы учета использования системных ресурсов. А если встретится второй условный переход еще до того, как станет известно, был ли правильно спрогнозирован первый условный переход, ситуация может совершенно запутаться.

Статическое и динамическое:

Динамическое прогнозирование ветвлений

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

Статическое прогнозирование ветвлений

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