分支预测

分支预测允许流水线处理器在分支指令解析之前猜测其结果和目标，从而可以沿着可能的路径继续获取和执行指令，而不是停顿。

Definition

分支预测是一种微架构技术，用于预测条件分支是否会被执行以及执行到何处，从而允许处理器沿着预测路径推测性地获取和执行指令，并在预测错误时放弃该工作。

Scope

本主题涵盖了控制流预测技术：静态预测、基于分支历史的动态预测器（一比特和二比特计数器、相关预测器和锦标赛预测器）、分支目标缓冲区，以及预测错误的代价。它探讨了预测如何实现深度流水线和推测执行。它不包括更广泛的推测执行机制和恢复（乱序执行）以及基本的控制冒险本身（流水线和冒险）。

Core questions

• 为什么分支会使深度流水线停顿，预测如何提供帮助？
• 动态预测器如何利用分支历史来提高准确性？
• 什么是分支目标缓冲区，它提供了什么？
• 预测错误的惩罚是什么，以及如何恢复？

Key concepts

• 静态预测与动态预测
• 一比特和二比特饱和计数器
• 分支历史和相关性
• 锦标赛预测器
• 分支目标缓冲区
• 预测错误惩罚
• 推测性获取

Key theories

基于历史的动态预测

分支结果与其自身及其他分支的过去行为高度相关；通过在饱和计数器中记录历史并结合局部和全局历史（相关预测器和锦标赛预测器）的预测器可以实现非常高的准确性。

Mechanisms

预测器通过查询历史来猜测分支的方向，并通过分支目标缓冲区来猜测其目标，从而使前端能够继续推测性地获取指令。二比特饱和计数器跟踪每个分支的近期结果；相关预测器增加了全局历史；锦标赛预测器在局部和全局方案之间动态选择。当预测错误时，推测性指令被清除，并从正确地址重新开始获取，这会产生与流水线深度成比例的惩罚。

Clinical relevance

准确的分支预测对于现代深度、宽流水线至关重要：由于预测错误会消耗多个周期，因此需要准确率超过95%的预测器才能维持高性能。分支预测结构也变得与安全性相关，因为它们的推测行为是Spectre等瞬态执行攻击的基础。

History

简单的静态和一比特动态预测器逐渐被二比特饱和计数器取代，然后在1990年代早期发展为相关预测器和两级自适应预测器，并在高性能核心中发展为锦标赛预测器和神经网络式预测器。随着流水线深度的增加，预测器的复杂性也相应提高，以使预测错误的惩罚保持在可接受的范围内。

Key figures

• James E. Smith
• Yale Patt
• Tse-Yu Yeh
• John L. Hennessy

Seminal works

• hennessy2019
• patterson2020

Frequently asked questions

当分支预测错误时会发生什么？

处理器已经推测性地获取并部分执行了错误路径上的指令。当检测到预测错误时，它会丢弃（清除）该推测性工作，并从正确的目标重新开始获取，这会产生大致与流水线深度成比例的惩罚。

现代分支预测器的准确性如何？

现代动态预测器通过结合局部和全局分支历史，在常见工作负载上通常能达到95%以上的准确率。这种高准确率使得深度、宽流水线变得有价值，因为每一次预测错误都会浪费多个周期的推测性工作。