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

Модуль предсказания переходов (прогнозирования ветвлений) (англ. branch prediction unit) — устройство, входящее в состав микропроцессоров, имеющих конвейерную архитектуру, предсказывающее, будет ли выполнен условный переход в исполняемой программе. Предсказание ветвлений позволяет сократить время простоя конвейера за счёт предварительной загрузки и исполнения инструкций, которые должны выполниться после выполнения инструкции условного перехода. Прогнозирование ветвлений играет критическую роль, так как в большинстве случаев (точность предсказания переходов в современных процессорах превышает 90 %) позволяет оптимально использовать вычислительные ресурсы процессора.

Без предсказания переходов конвейер должен дождаться выполнения инструкции условного перехода, чтобы произвести следующую выборку. Предсказатель переходов позволяет избежать траты времени, пытаясь выяснить ответвление. Ответвление выбирается по предыдущим результатам проверки условия. Предполагаемое ответвление затем загружается и частично выполняется. Если затем обнаруживается, что предсказание было выполнено неверно, отменяются результаты неверного ветвления и в конвейер загружается правильное ответвление, производя задержку. Величина задержки зависит от длины конвейера. Для процессора Intel Core i7 глубина конвейера составляет 14 стадий.

Следует отличать «предсказание переходов» от «предсказания адреса перехода». Цель предсказания адреса перехода состоит в выборе адреса условного или безусловного перехода до декодирования и выполнения инструкции перехода.

Существует два основных метода предсказания переходов:

• статический;
• динамический.

Статическое предсказание

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

• либо выполняются всегда;
• либо не выполняются никогда.

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

Пример тривиального статического предсказания, реализованного в первых процессорах архитектур SPARC и MIPS.

• В конвейер всегда загружаются инструкции, расположенные после инструкции условного перехода. if(условие) {<предсказанный переход>} else {...}

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

Пример статического предсказания, реализованного в современных процессорах.

• Если инструкция перехода выполняет переход назад (на младшие адреса), в конвейер загружаются инструкции, расположенные по адресу перехода. do {<предсказанный переход>} while(условие); ...
• Если инструкция перехода выполняет переход вперёд (на старшие адреса), в конвейер загружаются инструкции, расположенные после инструкции перехода. if(условие) {<предсказанный переход>} else {...}

В данном случае принимается предположение о том, что любой переход назад будет выполнен, а любой переход вперёд — не будет. Метод используется в качестве «подстраховки».

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

Динамические методы, широко используемые в современных процессорах, подразумевают анализ истории ветвлений.

Счётчик с насыщением или бимодальный счётчик

Анализируется таблица истории переходов. Таблица содержит:

• младшие значимые биты адреса инструкции;
• соответствующую им вероятность условного перехода:
  • «скорее всего, будет выполнен»;
  • «возможно, будет выполнен»;
  • «возможно, не будет выполнен»;
  • «скорее всего, не будет выполнен».

Таблица обновляется после каждого перехода. Алгоритм изменяет выбор ветвления, если результат условия отклонился два раза от предыдущих результатов. Использование младших битов адреса инструкции позволяет производить предсказания нескольких инструкций до их декодирования.

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

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

Локальное предсказание перехода

Каждый условный переход в области имеет собственную историю переходов. Шаблоны переходов могут быть общими или отдельными.

Глобальное предсказание перехода

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

Гибридный предсказатель

Гибридный предсказатель может выбирать результаты наиболее успешных предсказателей на основе истории либо использовать мажоритарную функцию нечётного количества предсказателей.

Предсказатель для цикла

Предсказатель для цикла может использовать счетчик цикла для отсчета количества переходов в начало цикла. Этот предсказатель может использоваться в гибридном предсказателе.

Предсказание косвенных переходов

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

Литература

• http://www.agner.org/optimize/microarchitecture.pdf Архивная копия от 28 марта 2017 на Wayback Machine
• http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array Архивная копия от 22 июня 2016 на Wayback Machine
• http://www.ece.iupui.edu/~johnlee/ECE565/papers/Two-level_Adaptive_Branch-prediction.ppt Архивная копия от 15 июня 2010 на Wayback Machine
• https://web.archive.org/web/20060909134209/http://personals.ac.upc.edu/aramirez/papers/ishpc02-osantana.pdf
• http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-36.pdf Архивная копия от 21 ноября 2008 на Wayback Machine

См. также

• Предвыборка кода
• Внеочередное исполнение