Двухбитовый предсказатель переходов¶

Двухбитовый предсказатель переходов — это аппаратный механизм динамического предсказания ветвлений в процессорах, использующий конечный автомат с четырьмя состояниями для повышения точности предсказания условных переходов. Относится к классу n-битовых предсказателей, где n=2, и является развитием однобитового предсказателя, устраняя его главный недостаток — чувствительность к повторяющимся циклам.

¶Принцип работы

Двухбитовый предсказатель хранит для каждой инструкции перехода двухбитовый счётчик в таблице истории переходов (Branch History Table, BHT). Значение счётчика интерпретируется как одно из четырёх состояний конечного автомата:

• 00 — «сильно не взят» (strongly not taken);
• 01 — «слабо не взят» (weakly not taken);
• 10 — «слабо взят» (weakly taken);
• 11 — «сильно взят» (strongly taken).

Предсказание выполняется по старшему биту счётчика: если он равен 1, переход считается взятым, если 0 — не взятым. После фактического выполнения инструкции состояние автомата обновляется: при реально взятом переходе счётчик увеличивается на 1 (с насыщением на 11), при не взятом — уменьшается на 1 (с насыщением на 00). Таким образом, для изменения предсказания с «взят» на «не взят» необходимо два подряд ошибочных предсказания, что обеспечивает инерционность.

¶Отличие от однобитового предсказателя

Однобитовый предсказатель (конечный автомат с двумя состояниями) меняет своё предсказание после каждой ошибки. В циклах с большим числом итераций, где переход берётся почти всегда, но в конце цикла не берётся, однобитовый предсказатель даёт две ошибки за цикл: одну на последней итерации (переход не взят) и одну на первой итерации следующего цикла (переход снова взят, а предсказание ещё «не взят»). Двухбитовый предсказатель в той же ситуации даёт только одну ошибку на последней итерации, поскольку после неё счётчик переходит из состояния 11 в состояние 10, и на первой итерации следующего цикла предсказание «взят» сохраняется.

¶Реализация и аппаратные особенности

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

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

¶Применение

Двухбитовый предсказатель исторически применялся в процессорах начиная с конца 1980-х годов. Он использовался в микропроцессорах Intel Pentium, AMD K5/K6, ARM и многих других архитектурах. В современных процессорах двухбитовые счётчики входят как составная часть более сложных гибридных предсказателей, например, предсказателей с выбором (gshare, tournament predictors), где они сочетаются с предсказателями на основе глобальной истории переходов.

¶Эффективность

Точность двухбитового предсказателя для типичных программ составляет 85–95%, что значительно выше однобитового (около 80%). Основные потери точности связаны с конфликтами в таблице и нерегулярными паттернами переходов, которые не улавливаются автоматом с четырьмя состояниями. Для таких случаев требуются более сложные алгоритмы, учитывающие корреляцию между различными переходами.

¶Ограничения

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

¶Литература

• Patterson D., Hennessy J. Computer Organization and Design: The Hardware/Software Interface.
• Smith J. E. A Study of Branch Prediction Strategies // Proceedings of the 8th Annual Symposium on Computer Architecture, 1981.
• Hennessy J., Patterson D. Computer Architecture: A Quantitative Approach.