超标量处理器设计：基于竞争的分支预测分支预测的更新

★ 继续学习体系结构的知识。

接着上一讲继续写

★上一讲：超标量处理器设计：基于全局历史的分支预测-CSDN博客

★上上一讲：超标量处理器设计：两位饱和计数器&基于局部历史的分支预测-CSDN博客

知识回顾：

基于局部历史的分支预测法

核心概念：这种方法根据每条分支指令在过去执行状况（局部历史）进行预测。为每条分支指令分配一个分支历史寄存器（BHR），记录其局部执行历史。

预测机制：使用由两位饱和计数器组成的模式历史表（PHT）来捕捉每个BHR的规律。预测时，结合BHR和PHT的信息，判断分支指令未来是否跳转。

优点与适用场景：对于那些行为主要取决于自身执行历史的分支指令（如循环体内部条件判断），基于局部历史的预测方法能够准确捕捉其规律，实现较好的预测效果。

基于全局历史的分支预测法

核心概念：这种方法基于一条分支指令之前的一些分支指令（全局历史）的执行状况进行预测。使用全局历史寄存器（GHR）记录所有分支指令的执行情况。

预测机制：同样使用由两位饱和计数器组成的PHT来捕捉GHR的规律。预测时，结合GHR和PHT的信息，判断分支指令未来是否跳转。

优点与适用场景：对于那些行为受全局执行上下文影响较大的分支指令（如函数调用返回点的跳转决策），基于全局历史的预测方法更能准确预测其行为。

混合预测策略

从之前的两讲可以得知基于局部历史的分支预测和和基于全局历史的分支预测都有适用的范围。

理想的做法是使用混合预测策略，对不同的分支指令采用最适合其特性的预测方法。

根据实际情况，灵活选择或组合使用基于全局历史和基于局部历史的分支预测方法，以及其他可能的预测策略，以实现更优的预测效果。

这样的混合预测策略可以兼顾不同类型分支指令的需求，提升整体预测准确率。

自适应的分支预测方法：竞争的分支预测

由于不同分支指令可能更适合不同的预测方法，提出一种自适应的分支预测方法。该方法可以根据不同分支指令的执行情况自动选择基于局部历史或基于全局历史的预测方法。

Alpha 21264处理器的应用：Alpha 21264处理器采用了这种竞争的分支预测方法，它就像两种预测方法在进行竞争，根据实际表现选择最优预测策略。

此图展示了竞争的分支预测方法的原理图，描述如何根据分支指令特性动态选择或竞争使用基于局部历史和基于全局历史的预测方法，以及如何整合这两种预测结果，最终确定分支预测输出。

工作原理

核心组件CPHT（Choice PHT）、状态机转换机制、分支指令训练过程

Alpha 21264处理器的实现细节。

CPHT (Choice PHT):CPHT是一个由分支指令的PC值（程序计数器值）寻址的表格，类似于PHT，但它的目的是根据两种预测方法（P1：基于全局历史，P2：基于局部历史）的表现，动态决定使用哪一种方法进行分支预测。CPHT由两位饱和计数器组成，每个计数器关联一个状态机，用于记录两种预测方法的相对性能。

监控两种预测方法：CPHT同时跟踪两种不同的分支预测方法（如P1和P2）。每当遇到一个分支指令，CPHT会根据该指令的PC值访问相应的表项，并记录两种预测方法的预测结果。

计数器更新：对于被监控的每种预测方法，CPHT中对应的两位饱和计数器会根据预测结果进行更新。若预测正确，计数器值增加；预测错误，计数器值减小。饱和计数器的初始状态通常设置为中间值（如01），表示对两种预测方法无偏向。

状态切换触发条件：当某一种预测方法（如P1）连续两次预测失败，而另一种预测方法（如P2）在同一时段内连续两次预测成功时，CPHT中的计数器状态将触发切换。例如，P1对应的计数器可能变为00，表示强烈不信任P1；P2对应的计数器变为11，表示强烈信任P2。

状态机转换：触发条件满足后，CPHT将驱动状态机转换到使用另一种分支预测方法（如P2）的状态。此后，处理器将暂时放弃连续预测失败的方法（P1），转而采用连续预测成功的P2进行分支预测，直至再次触发状态切换条件。

状态转移规则：

P1正确，P2错误(1/0)；计数器减1，倾向于使用P1。

P1错误，P2正确(0/1)；计数器加1，倾向于使用P2。

P1和P2预测结果一致（1/1或0/0）：无论预测正确与否，计数器保持不变，维持当前预测方法选择。

饱和状态：

00状态：计数器饱和至00时，选择P1（基于全局历史）进行预测，此时认为P1的准确度较高。

11状态：计数器饱和至11时，选择P2（基于局部历史）进行预测，此时认为P2的准确度较高。

分支指令训练与预测选择:

训练过程：每条分支指令在经过一段训练时间后，根据P1和P2的执行情况，确定使用哪种预测方法。

动态选择：对于同一分支指令，随着执行环境变化（如GHR内容变化），可能需要在P1和P2之间切换，以获得最佳预测效果。

Alpha 21264处理器的实现:

仅使用全局历史寄存器（GHR）作为CPHT的寻址依据，未考虑分支指令的PC值。

问题：这种实现可能导致不同分支指令因GHR值相同而共享同一个CPHT计数器，引发冲突，降低预测准确度。

综合考虑PC与GHR：通过将PC值与GHR寄存器进行运算（如异或）得到混合地址，用于寻址CPHT和P1的PHT。这样既考虑了分支指令的地址信息，又考虑了全局历史，可以针对不同分支指令在不同执行情况下的特点，选择最适合的预测方法。

通过这种方式，CPHT实现了对多种分支预测方法的实时评估与动态选择，能够在不同分支行为模式下自动切换至预测效果更好的方法，从而提升整体分支预测准确率。

分支预测的更新

在理想分支预测方法中，处理器首先根据PC值进行分支预测，依据预测结果继续执行，待实际得到分支指令结果后更新分支预测器中的相关数据。然而，在实际的超标量处理器中，由于流水线的存在，何时更新分支预测器（特别是历史寄存器GHR或BHR以及PHT中的饱和计数器）对预测准确度有显著影响。

更新历史寄存器

流水线影响与预测准确度

在现代超标量处理器中，由于深流水线和多条指令并行执行的特点，一条分支指令从预测到退休可能经历较长的时间。若选择在退休阶段更新GHR（或BHR），可能导致在该分支指令退休前进入流水线的后续分支指令无法利用其实际结果进行预测，从而降低预测准确度。特别是当分支指令前有产生D-Cache缺失的load指令时，会延长分支指令到达退休阶段的时间，使得更多后续分支指令无法受益于其结果。

超标量处理器的流水线环境中，分支指令b从预测到退休期间，其他分支指令由于无法及时利用其结果而导致预测准确度下降的问题。

1. 分支指令预测与退休时间差（△t）的影响

时间点 t：分支指令b在时间t被分支预测器预测其执行方向。

时间点 t +△t：分支指令b在经过一段时间△t后，从流水线中退休并更新全局历史寄存器（GHR）。

△t时间段内：在分支指令b预测（t时刻）与退休（t+△t时刻）之间的△t时间段内，任何被预测的分支指令都无法利用分支指令b的实际执行结果来改进自身的预测。这是因为分支指令b的结果尚未写入GHR，而后续分支指令的预测依赖于当时的GHR状态。

2. D-Cache缺失导致退休延迟

D-Cache缺失：若分支指令b之前存在产生D-Cache缺失的load指令，会导致数据访问延迟。这种延迟会增加分支指令b在流水线中停留的时间，即延长其到达退休阶段所需的时间（△t增大)。

预测准确度下降：由于分支指令b退休时间延长，更多后续分支指令在进行预测时无法利用其实际执行结果。这些分支指令可能基于过时的GHR状态进行预测，从而降低了预测准确度。

图4.27直观展示了在流水线处理器中，分支指令b退休时更新GHR所带来的问题。

在图4.27中，分支指令Br2至Br5在进行分支预测时均使用了同一未更新的GHR值，直至分支指令Br1退休时才更新GHR，导致基于全局历史的分支预测效果大打折扣。

针对如何在适当时间点更新GHR以提高预测准确度，讨论三种方法及其优缺点：

(1) 方法一（取指令阶段）：当流水线的取指令阶段进行分支预测时，根据预测结果直接更新GHR。这种方法即时反映分支行为，但若预测错误，可能导致后续流水线阶段基于错误的GHR进行预测。

(2) 方法二（执行阶段）：当分支指令的实际方向在流水线执行阶段计算得出时，更新GHR。这种方法比方法一稍晚，减少了因预测错误导致的GHR误更新风险，但后续未执行的分支指令可能仍基于旧的GHR进行预测。

(3) 方法三（提交阶段/退休阶段）：当分支指令到达流水线最后的提交阶段并即将退休时，更新GHR。这种方法最为保守，确保更新GHR时分支指令的状态已完全确定，但可能导致大量后续分支指令在预测时未能利用到已退休分支指令的最新结果。

选择在取指令阶段根据分支预测结果更新GHR是一种有效的策略。这种方法能够让后续分支指令及时利用最新的GHR进行预测，提高预测准确性。即使遇到分支预测失败的情况，由于预测失败路径上的所有指令最终会被流水线抹除，这些指令使用错误GHR的事实对系统无实质性影响。然而，取指令阶段更新GHR属于推测性操作，当分支预测失败时，需要有相应的机制对GHR进行修复，确保其恢复到正确的状态。接下来将介绍两种修复GHR的方案。

（1）提交阶段修复法

在超标量处理器中，为了应对基于推测（speculative）更新的取指令阶段GHR（Speculative GHR）在分支预测失败时可能存在的错误，提出了提交阶段修复法。该方法在流水线后端的提交阶段引入一个额外的GHR，称为Retired GHR，用于记录分支指令在退休时的实际执行结果。具体操作如下：

1. 双GHR结构：处理器内部维护两个GHR：前端取指令阶段使用的Speculative GHR（用于分支预测，推测性更新）和后端提交阶段的Retired GHR（分支指令退休时更新，确保正确性）。

2. 分支指令退休：当一条分支指令到达提交阶段并退休时，将其实际执行结果更新到Retired GHR。

3. 预测失败修复：当检测到分支预测失败时，表明前端的Speculative GHR存在错误。此时，等待该分支指令退休，将Retired GHR的正确值写回前端的Speculative GHR，完成GHR状态修复。随后，根据分支指令的实际目标地址重新取指令执行。

4. 缺点：使用提交阶段修复法时，分支预测失败的惩罚（mis-prediction penalty）会增大，特别是当分支指令前面存在引发D-Cache缺失的load指令时，由于延迟退休导致惩罚更为显著，严重影响处理器性能。

图4.28详细展示了提交阶段修复法中GHR的状态转移过程、分支预测失败时的错误路径清理、Retired GHR向Speculative GHR的正确值传递以及相关控制逻辑等，直观呈现了该方法的运作机制。

综上，提交阶段修复法通过设立Retired GHR确保分支指令实际执行结果的正确记录，并在预测失败时用于修复前端Speculative GHR，从而维持分支预测的准确性。然而，这种方法增加了分支预测失败时的惩罚，特别是在存在D-Cache缺失延迟的情况下，可能显著降低处理器性能。

（2）Checkpoint修复法

为了减少分支预测失败时的惩罚并尽早执行正确路径上的指令，提出了Checkpoint修复法。该方法在取指令阶段更新前端GHR的同时保存旧的GHR值作为Checkpoint GHR，并在分支指令结果计算出来后（如执行阶段）快速进行状态修复。

1. Checkpoint GHR：在取指令阶段更新前端Speculative GHR时，保存旧的GHR值作为Checkpoint GHR。

2. 分支预测结果检查：当分支指令在执行阶段计算出实际结果时，检查其分支预测是否正确。若预测正确，继续执行；若预测失败，需进行GHR状态修复。

3. 状态修复：分支预测失败时，将该分支指令对应的Checkpoint GHR恢复至前端Speculative GHR，并从其正确目标地址重新取指令执行。图4.29展示了这一过程，包括一个专门存储所有Checkpoint GHR值的存储器，当发生预测失败时，将与分支预测结果相反的值直接写入前端GHR完成恢复。

4. 存储器操作：

顺序执行：在取指令阶段分支指令仍按顺序排列，因此存储Checkpoint GHR的存储器只需按照FIFO（先进先出）方式写入。后续流水线若顺序执行分支指令，读取存储器也按照FIFO方式即可。

乱序执行：若流水线采用乱序执行分支指令，读取存储器的顺序不再遵循FIFO，增加了存储器设计难度。

对于乱序执行分支指令的流水线，虽然在执行阶段可能获得分支指令的结果，但由于该指令可能位于分支预测失败或异常路径上，仍需要在提交阶段进行预测正确性检查。

为此，提交阶段保留一个Retired GHR，当分支指令退休时发现预测失败或发生异常，将Retired GHR写回前端GHR进行状态恢复。这种方法本质上是对方法一（提交阶段修复法）的补充，允许在执行阶段和提交阶段双重恢复GHR，从而加快分支预测失败时的修复速度，提升处理器效率。

对于基于局部历史的分支预测方法，BHR的更新时机与基于全局历史的方法相似，可以推测性更新或非推测性更新。BHR存储的是当前分支指令过去执行情况，通常只有在循环体较短的情况下，才可能出现分支指令在提交阶段更新BHR时，流水线中已再次使用该指令BHR进行预测的情况。

以图4.30所示的循环体（三条指令addi、addi、bne）为例，在一个3-way超标量处理器中，如图4.31所示的执行过程中，第一个bne指令更新BHR之前，后续所有bne指令均未利用其结果。尽管如此，经过训练期后，分支预测器将准确预测bne指令发生跳转，除了循环最后一次外，其余预测均为正确。这与基于全局历史的分支预测方法中GHR更新存在区别。