Какие существуют методы предсказания переходов в конвейере?

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

Статический метод работает по схеме, заложенной в процессор. 5 Считается, что переходы по одним условиям вероятнее всего произойдут, а по другим — нет. 5 Некоторые примеры статического предсказания:

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

Динамический метод опирается на предысторию вычислительного процесса. 5 Для каждого конкретного случая перехода накапливается статистика поведения, и переход предсказывается, основываясь именно на ней. 5 Некоторые примеры динамического предсказания:

• Счётчик с насыщением или бимодальный счётчик. 12 Анализируется таблица истории переходов. 1 Таблица содержит младшие значимые биты адреса инструкции и соответствующую им вероятность условного перехода. 1 Таблица обновляется после каждого перехода. 1
• Адаптивный двухуровневый предсказатель. 1 Для первого уровня выполняется история последних k ветвлений, второго уровня k указывает на таблицу шаблонов. 1
• Локальное предсказание перехода. 1 Каждый условный переход в области имеет собственную историю переходов. 1 Шаблоны переходов могут быть общими или отдельными. 1
• Глобальное предсказание перехода. 1 Глобальное предсказание переходов не хранит истории отдельно для каждого перехода, а использует общую историю. 1 Любые закономерности в переходах сказываются на этой истории, но историю могут загрязнять нерелевантные записи. 1
• Гибридный предсказатель. 1 Может выбирать результаты наиболее успешных предсказателей на основе истории либо использовать мажоритарную функцию нечётного количества предсказателей. 1
• Предсказатель для цикла. 1 Может использовать счётчик цикла для отсчёта количества переходов в начало цикла. 1
• Предсказание косвенных переходов. 1 Косвенный переход может иметь больше двух ветвлений. 1 Новейшие процессоры имеют возможность выбора более двух условий, используя двухуровневый адаптивный предсказатель. 1