分支目标预测与分支预测相结合的作用是什么？

Question

分支目标预测与分支预测相结合的作用是什么？

x86cpu-architecturebranch-prediction

27

编辑：我的困惑在于，预测哪个分支被执行实际上也等于进行了目标预测吗？

这个问题与我关于此主题的第一个问题有着内在关联：

分支预测与分支目标预测

看着被接受的答案：

无条件跳转，固定目标

无限循环
goto 语句
break 或 continue 语句
if/else 语句的“then”子句结束（跳过else子句）
非虚函数调用

无条件跳转，可变目标

从函数返回
虚函数调用
函数指针调用
switch 语句（如果编译成跳转表）

有条件跳转，固定目标

if 语句
switch 语句（如果编译成一系列if/else语句）
循环条件测试
&& 和 || 运算符
三元 ?: 运算符

有条件跳转，可变目标

在正常情况下不太可能出现，但编译器可能将两种情况合并为优化。例如，在 x86 上，如果出现在函数末尾由于尾调用优化，编译器可以将代码像if (condition) { obj->VirtualFunctionCall(); }优化为条件间接跳转，如 jne *%eax。

如果我有以下代码：

if(something){
    //a
}
else{
    //b
}

(BP = "分支预测"，BTP = "分支目标预测")

很明显BP用于评估条件“something”。然而，我正在尝试了解BTP是否也参与确定分支“a”中发生的情况。根据BP的结果，BTP是否还确定了位于分支“a”/“b”处的代码的地址？

我之所以问是因为在这个维基百科页面上（http://en.wikipedia.org/wiki/Branch_target_predictor）：

在计算机体系结构中，分支目标预测器是处理器的一部分，它在处理器的执行单元计算分支指令的目标之前，预测取出条件分支或无条件分支指令的目标。

它暗示BTP用于在预测条件后预测目标。

1）有人可以澄清上述内容吗？

一道相关的问题——BP和BTP在与CPU的取指/译码/执行/写回流水线交互方面有何不同？BP从取指或译码阶段开始吗？在条件代码的执行阶段之后，我们可以检查预测是否正确并更新分支预测缓存。 2) BTP如何与取指/译码/执行/写回CPU阶段相关？

- user997112

2个回答

17

请阅读Intel优化手册，当前下载位置在这里。如果过期了（他们总是在移动东西），那么请在Intel网站上搜索“架构优化手册”。请记住，那里的信息相当通用，他们只透露足够的信息来允许编写高效代码。分支预测实现细节被认为是商业机密，并且在不同的体系结构之间会发生变化。搜索手册中的“分支预测”以找到参考资料，它分布在各个章节中。

手册中的内容概括如下：分支预测是核心中BPU单元（分支预测单元）的工作。它包含几个子单元：

- 分支历史表。此表跟踪先前采取的条件分支，并由预测器查询以决定是否可能采取分支。它由指令退役单元提供条目，该单元知道分支是否实际采取。随着架构的改进，该子单元发生了最大的变化，随着更多的房地产变得更深和更智能。 - BTB，分支目标缓冲区。该缓冲区存储先前采取的间接跳转或调用的目标地址。这对应于您问题中的“BTP”。手册没有说明缓冲区是否可以存储每个地址的多个目标，由历史表索引，我认为对于后期体系结构来说可能是有可能的。 - 返回堆栈缓冲区。该缓冲区充当“阴影”堆栈，存储CALL指令的返回地址，使RET指令的目标可用，并具有高度的信心，而不必依赖BTB，对于调用可能不太有效。据文档记录，它的深度为16级。

第二个问题有些难以准确回答，手册只涉及“前端”而没有详细阐述流水线的细节。相当合理，因为它在很大程度上取决于架构。2.2.5节中的图表可能是说明性的。执行跟踪缓存扮演了一个角色，它存储先前解码的指令，因此是BPU查询的主要来源。否则就在指令翻译器（又名解码器）之后。

- Hans Passant

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Leeor · Accepted Answer

BP和BTP天然密切相关，但它们显然不是同一件事。我认为你最大的困惑来自于这样一个说法：由于BTP预测了给定分支的目标，因此可以告诉您结果（即下一条将执行的指令）。但事实并非如此。

分支目标是该分支可能带您到达的地址，如果它被选中。该分支是否被选中是完全不同的问题，并由分支预测器解决。实际上，这两个单元通常在流水线的早期阶段一起工作 - 并且产生（如果需要）被选中/未被选中以及地址预测。然后就会出现复杂的逻辑，基本上是说 - 如果它是分支，而且它被预测为被选中（或者是无条件的），那么如果您有（已知或预测的）目标，请跳转到该目标。

正如您在分支类型列表中引用自己的话 - 分支是否需要预测被选中或不被选中（是否有条件），以及分支是否需要预测目标（您所称的直接/固定目标）都是适用的，每个都可以无关地走向另一个方向，从而为您提供了您列出的4个选择：

理论上，无条件直接分支不需要任何预测 - CPU前端将简单地读取目标并“跳转”到该分支（从新地址提供流水线代码）。然而，现代CPU仍需要时间来解码分支并识别其中编码的目标，因此为了避免在分支预测器（通常位于管道头部）处出现停顿，它们也必须预测该地址。但确认预测很简单（在解码后立即进行），因此误判的惩罚并不高。尽管由于代码缓存/TLB misses可能会被阻塞，但仍然是最快的（但也有人可能会说它是最弱的）。
有条件直接分支，解码后可以知道它们的目标（但必须在此之前预测），但不能确定分支是否被执行，直到执行条件被满足并作出决定，这可能非常耗时。这又取决于早期指令，并且可能会被阻塞，直到条件来源被识别。因此，需要进行两个预测-目标和方向（除非方向是“穿过”，则不需要目标），但方向的解析更加危险。分支预测器（实际上，在现代CPU上通常有几个分支预测器）会做出有根据的猜测并继续从那里获取。甚至在学院里也进行了一些研究，试图获取和执行两条路径（尽管你可以立即看到，由于您通常每几个指令就有一个分支，所以这可能呈指数级增长，因此通常保留给难以预测的分支）。另一个流行的选项是“预测”（注意那里的“a”...）这两个路径，即向管道发送一些位来标记它是哪个路径，以便在解析后轻松清除错误的路径。由于语言结构原因，这在数据流机器上非常受欢迎，但这是一个全新的问题。
无条件间接分支-这些非常讨厌，因为它们既普遍（例如，每个ret），又更难以预测。虽然在前面的情况下分支解决方案很简单（并且总是可以依赖一些启发式或模式猜测），但这需要提供一个实际地址，因此您可能需要多次访问具有特定目标的特定分支，以便BTP学习那里的模式。
有条件的间接分支-对于您来说真是倒霉，您需要两个预测...

因此，决策是正交的，但这并不意味着预测器也必须如此。请记住，您只有一个“分支历史记录”流，因此可能付出代价使预测器相关，共享一些表或一些逻辑。确切的设计决策取决于实际的硬件实现，您可能不会获得有关Intel / AMD如何做到这一点的详细信息，但有大量的学术研究涉及该主题。

关于第二个问题——它有点宽泛，而且你也不能在真实的CPU上得到所有确切的细节，但是你可以从这里和那里得到一些线索，例如从这篇Haswell评论中的图表（可能以前在这里出现过）：

Haswell block diagram

这张图并没有告诉你所有的事情，显然它缺少BP/BTP的输入，甚至没有区分它们之间的差异（这本身就告诉你它们可能是一起构建的），但它确实显示这是流水线的首要部分。在将其馈送到取指、解码等流水线（或替代的uop-cache流水线）之前，您需要预测下一个指令指针。这可能意味着CPU每个周期都需要考虑执行哪个指令。（好吧，是的，一切都是并行完成的，但把流水线看作分阶段的过程有助于我们理解）。假设他知道上一次我们在哪里，那么它要么是一个非分支指令（啊，但变长怎么办，这个单元还有其他的复杂之处需要解决），要么是一个分支指令，在这种情况下，该单元应该猜测上面的哪种类型属于该分支，并相应地预测下一个指令。

请注意我写的“猜测” - 如果图表说的是真的，解码阶段真的很远，你甚至不知道这时候是分支。因此，回答您的问题-这个BP/BTP单元需要与执行/WB单元通信，以便它可以知道条件分支的结果，与解码单元通信，以便它可以知道当前正在决定的指令是分支还是其他类型，与不同的取指流水线通信，以提供输出。我猜想与其他单元也有进一步的关系（例如，某些设计可能会根据目标预测发送代码预取等）。