Предсказатель переходов

Условный переход

Условный переход — любое изменение последовательности выполнения кода.

Условные переходы вперёд

if
break
switch

Условные переходы назад

do
while
for

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

Модуль предсказания переходов

Предсказатель переходов ⇔ Блок выборки команд

Спекулятивное исполнение

Выполнение команды раньше того, как станет известно, понадобится она или нет.

Важно: спекулятивно выполняются только команды, результат которых можно отменить.

Выполнение команды раньше того, как станет известно, понадобится эта команда или нет, называется спекулятивным исполнением.

Спекулятивное исполнение команд создает некоторые интересные проблемы. Например, очень важно, чтобы ни одна из спекулятивных команд не давала результата, который невозможно отменить, поскольку позднее может оказаться, что эту команду не нужно было выполнять. Что произойдет, если спекулятивная команда вызовет исключение?

Ядовитый бит

Poison bit — альтернативный механизм исключений.

Если спекулятивно выполненная команда вызвала ошибку, устанавливается ядовитый бит.

Если результат команды используется, проверяется ядовитый бит и выбрасывается исключение.

Если результат команды не используется, ядовитый бит сбрасывается.

Ядовитый бит

x = 0;
if(x > 0)
    z = y / x;

Если 3 строка выполнится спекулятивно, до if, деление на ноль вызовет установку ядовитого бита.

Более сложную ситуацию можно проиллюстрировать следующим оператором: if (x > 0) z = y/x; Здесь x, y и z — переменные с плавающей точкой. Предположим, что все эти переменные поступают в регистры заранее, а команда деления с плавающей точкой (эта команда выполняется медленно) перемещается вверх по графу и выполняется еще до условного оператора if. К сожалению, если значение x равно 0, то программа завершается в результате попытки деления на 0. Таким образом, спекулятивная команда приводит к сбою в изначально правильной программе. Еще хуже то, что программист изменяет программу, чтобы предотвратить подобную ситуацию, но сбой все равно происходит. Одно из возможных решений — специальные версии тех команд, которые могут вызывать исключения. Кроме того, к каждому регистру добавляется так называемый бит отравления (poison bit). Если спекулятивная команда дает сбой, она не инициирует перехват исключения, а устанавливает бит отравления в регистр результатов. Если затем этот регистр используется обычной командой, выполняется перехват исключения (как и должно быть в случае исключения). Однако если этот результат не используется, бит отравления сбрасывается и никак не влияет на ход выполнения программы.

Методы предсказания ветвлений

Статические — без анализа истории ветвлений.
Динамические — с анализом истории ветвлений.

Ветвление — условный переход.

Статический метод

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

Статический метод

Примеры:

В конвейер всегда загружаются инструкции, расположенные после инструкции условного перехода.
В конвейер всегда загружаются инструкции, расположенные по адресу условного перехода, если переход выполнется назад.

Счётчик

Сохраняет информацию о прошлом переходе.
Ошибочно срабатывает на первой и последней итерациях for.

Счётчик с насыщением

Двухбитный счётчик вероятности условного перехода:

11 — “будет выполнен”
10 — “возможно, будет выполнен”
01 — “возможно, не будет выполнен”
00 — “не будет выполнен”

Счётчик с насыщением

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

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

При выходе из цикла переход предсказывается неправильно, и, что еще хуже, этот неправильный прогноз изменяет бит в таблице, который после этого будет показывать, что переход совершать не требуется. То есть в следующий раз, когда опять потребуется выполнять цикл, переход в конце первого прохода цикла окажется спрогнозированным неправильно. Если цикл находится внутри другого цикла или внутри часто вызываемой процедуры, эта ошибка будет повторяться достаточно часто. Для решения проблемы можно немного изменить метод прогнозирования, чтобы прогноз менялся не после одного, а только после двух последовательных неправильных прогнозов. Такой подход требует наличия в таблице двух битов прогнозирования переходов: один должен указывать, предполагается совершать переход или нет, а второй — был сделан переход в прошлый раз или нет. В данной разработке используются только 2 бита, но возможно применение и 4, и 8 бит.

Адаптивный двухуровневый предсказатель

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

Другие

Гибридный — использование нескольких предсказателей одновременно.
Предсказатель цикла — использует счётчик цикла для отсчёта количества переходов.
Предсказатель адреса возврата из функций — используется таблица с адресами возврата.