24. Предсказание ветвлений. Статическое и динамическое предсказание. Таблица истории переходов, предсказатели, буфер адресов переходов, стек адресов возврата.

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

Статическое предсказание – прогноз устанавливается до выполнения.

Динамическое предсказание – адаптируется в процессе выполнения.

Предсказание может осуществляться компилятором или аппаратурой

Предсказание компилятором

У каждой инструкции ветвления указывается дополнительный бит (1 – ветвь будет выбрана, 0 – не будет). Требуется поддержка со стороны архитектуры команд. Для предсказания компилятор может использовать профилирование (запуск) или правила.

Достоинства:

  1. Нет ограничения по аппаратуре.
  2. Низкая цена.

Недостатки:

  1. Предсказание не изменяется в ходе выполнения.
  2. Плохая производительность.

Динамическое предсказание

Базируется на том, что каждая ветвь имеет свои особенности – «индивидуальность». Кроме того, наблюдается строгая «предрасположенность» ветвей к выбору того или иного перехода (например, циклы).

Достоинства:

  1. Точность изменяется динамически.

Недостатки:

  1. Затраты по площади кристалла, энергопотреблению.
  2. Ограниченная производительность.

Таблица истории переходов (BHT)

Branch History Table – небольшая память, индексируемая младшей частью счетчика команд (PC). При промахе, значение в таблице изменяется. Доступ к таблице осуществляется на фазе Instruction Fetch (IF). Поведение в прошлом используется для предсказания поведения в будущем. Может учитываться как локальное так и глобальное поведение.

Прочие предсказатели

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

Способы предсказания:

  1. Глобальные – один предсказатель для всех образцов.
  2. Поадресные – отдельный предсказатель для каждого образца каждой ветви.
  3. В пределах множества – один предсказатель для каждого образца ветвей в пределах одного множества.

Коррелирующий предсказатель (двухуровневый предсказатель) – предсказатель, в котором используется информация о поведении n ветвей для выбора среди m предсказателей данной ветви.

Соревнующийся предсказатель (Tournament Predictor) – использует попеременно глобальный предсказатель или локальный предсказатель, выбор между ними осуществляется с использованием селектора. Пример такого предсказателя будет показан при рассмотрении процессора Alpha.

Буфер адресов переходов (Branch Target Buffer, BTB)

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

Стек адресов возврата (Return Address Stack, RAS)