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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

Статическое предсказание[править | править вики-текст]

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

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

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

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

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

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

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

  • Если инструкция перехода выполняет переход назад (на младшие адреса), в конвейер загружаются инструкции, расположенные по адресу перехода.
  • Если инструкция перехода выполняет переход вперёд (на старшие адреса), в конвейер загружаются инструкции, расположенные после инструкции перехода.

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

Динамическое предсказание[править | править вики-текст]

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

Счётчик с насыщением или бимодальный счётчик[править | править вики-текст]

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

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

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

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

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

Локальное предсказание перехода[править | править вики-текст]

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

Глобальное предсказание перехода[править | править вики-текст]

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

Гибридный предсказатель[править | править вики-текст]

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

Предсказатель для цикла[править | править вики-текст]

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

Предсказание косвенных переходов[править | править вики-текст]

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

Примечания[править | править вики-текст]

  1. Журнал «PC Magazine/Russian Edition». Статья «Наследие RISC: Предсказание переходов». Выпуск за октябрь 1995 года. Онлайн версия: [1]

Литература[править | править вики-текст]

См. также[править | править вики-текст]