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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания[править | править исходный текст]

  1. www.pcmag.ru/issues/sub_detail.php?ID=10105&SUB_PAGE=8 Наследие RISC: Предсказание переходов // PC Magazine/RE, Октябрь 1995

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