Кратко — есть две группы подходов: прогнозирование (предсказание направления и цели перехода) и аппаратно‑программные механизмы для уменьшения простоя при ошибке предсказания. Ниже — методы, краткое объяснение работы и ключевые компромиссы.
Формула влияния ветвлений на производительность:
$CPI=CP{I}_{base}+f_b\cdot p_{mis}\cdot Penalty$,
где $f_b$ — доля ветвлений, $p_{mis}$ — вероятность промаха предиктора, $Penalty$ — число тактов простоя при промахе. Цель — уменьшить либо $p_{mis}$, либо $Penalty$.
1) Статические стратегии
- Всегда не‑taken / всегда taken: просто, нет HW; хороши при очень простой нагрузке.
Компромисс: нулевая аппаратная стоимость, плохая точность на сложных потоках.
- Backward‑taken / forward‑not (для циклов): простая эвристика, улучшает точность для циклов.
Компромисс: простота vs не покрывает другие паттерны.
- Profile‑guided (компилятор/сборка): используется информация профиля для вставки подсказок.
Компромисс: требует профилирования/перекомпиляции, устойчива только для похожих входных данных.
2) Простые динамические предикторы
- 1‑бит предиктор: хранит последнее направление ветвления в таблице (BHT).
Компромисс: малая память и простота, чувствителен к чередованию (строгое «бит» колебания).
- 2‑bit saturating counter (Bimodal): два‑битный счётчик уменьшает промахы при кратковременных колебаниях.
Компромисс: чуть больше памяти, значительно лучше точность для реальных программ.
3) Коррелирующие / двухуровневые предикторы
- Local history (per‑branch history + local table): учитывает локальную историю конкретного ветвления.
- Global history (Gshare, global‑history + pattern history table): учитывает глобальные паттерны между ветвлениями.
- Tournament/hybrid: комбинирует локальный и глобальный предикторы и выбирает лучший.
Компромисс: высокая точность при сложных паттернах, но значительно больше аппаратных ресурсов (таблицы, индексация), большая латентность и энергопотребление.
4) Структуры для предсказания цели
- Branch Target Buffer (BTB): кеширует адрес цели и тип ветвления для быстрого перехода.
Компромисс: требует ассоциативной памяти, конфликты приводят к дополнительной задержке.
- Return Address Stack (RAS): LIFO стек для предсказания возвращений из функций.
Компромисс: очень эффективен для вызовов/возвратов, малый HW, но ломается при переполнении/некорректном управлении стеком.
5) Механизмы предвычисления и уменьшения Penalty
- Спекулятивная выборка/выполнение: инструкций по предсказанному пути выполняются заранее.
Компромисс: повышает параллелизм, но требует механизмов отката и увеличивает энергопотребление при ошибке.
- Раннее разрешение ветвей (branch resolution earlier stages): вычислять условие быстрее (ALU‑пересылки, предвычисление флагов).
Компромисс: усложняет datapath, может увеличить критический путь.
- Branch folding / branch fusion: удалять/сворачивать простые ветви аппаратно.
Компромисс: ограниченная применимость.
- Fetch redirect / multi‑way fetch (fetch from multiple targets): выбор нескольких потоков для уменьшения простоя при промахе.
Компромисс: большая пропускная способность и сложность.
- Delayed branch (компилятор): вставка полезных инструкций в «отложенные» слоты после ветви.
Компромисс: упрощает HW, но требует тщательной компиляции и плоха в современных deep‑pipeline/OOO CPU.
- Predication (условные инструкции / conditional move): заменяет ветвления инструкциями, убирая ветвление.
Компромисс: код растёт, и неоправданно применённая предикация может увеличить нагрузку на процессорные ресурсы.
6) Общие компромиссы и практические замечания
- Точность vs стоимость: более сложные предикторы (gshare, tournament, neural) дают более низкий $p_{mis}$ но нуждаются в больших таблицах, энергии и логике; у них также больше латентность доступа.
- Латентность предиктора: если предсказание делается поздно, уменьшение $p_{mis}$ может не уменьшить $Penalty$ — важно быстродействие таблиц (BTB/BHT).
- Энергопотребление и площадь: крупные предикторы и большие BTB дорогостоящи в мобильных системах.
- Сложность валидации: сложные предикторы и speculative execution усложняют верификацию и безопасность (спектр атак).
- Комбинации: в реальности используют и BTB, и RAS, и 2‑bit/ correlating предикторы + tournament; для сервера — большие сложные предикторы, для embedded — простые/статические или predication.
Рекомендация по выбору (кратко):
- Встраиваемые/простые CPU: static heuristics + 2‑bit BHT, небольшой BTB, возможно predication.
- Высокопроизводительные OoO CPU: BTB + RAS + large hybrid correlating predictor (gshare/local + tournament) + агрессивная спекуляция и раннее разрешение ветвей.
- Компиляторные оптимизации: profile‑guided и delayed/ставка на predication там, где выгодно.
Если нужно, могу кратко описать архитектурные схемы (BHT/B TB/Gshare) или дать оценку влияния разных $p_{mis}$ на $CPI$ для конкретных чисел.