27

编辑：我的困惑出现了，因为肯定通过预测采用哪个分支，您也在有效地进行目标预测？？

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

分支预测与分支目标预测

查看接受的答案：

无条件分支，固定目标

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

无条件分支，可变目标

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

条件分支，固定目标

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

条件分支，可变目标

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

如果我有以下代码：

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

（BP =“分支预测”和 BTP =“分支目标预测”）

其非常明显的 BP 用于评估条件something. 但是，我试图了解 BTP 是否也参与确定分支中发生的情况a。BTP 是否也会根据 BP 的结果确定位于分支a/的代码的地址？b

我在这个维基百科页面（http://en.wikipedia.org/wiki/Branch_target_predictor）上询问：

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

它建议在条件预测后使用 BTP 来预测目标。

1）有人可以澄清一下吗？

第二个相关问题 - BP 和 BTP 在与 CPU 的 fetch/decode/execute/write-back 管道交互的方式上有何不同？BP 是否从获取或解码阶段开始？在条件代码的执行阶段之后，我们可以检查预测是否正确并更新分支预测缓存。

2) BTP 在获取/解码/执行/写回 CPU 阶段如何工作？

4

2 回答 2

17

请阅读英特尔优化手册，当前下载位置在此处。当陈旧时（他们一直在移动东西）然后在英特尔网站上搜索“架构优化手册”。请记住，那里的信息相当通用，它们只披露允许编写高效代码所需的尽可能多的信息。分支预测实现细节被认为是商业秘密，并且会在架构之间发生变化。在手册中搜索“分支预测”以查找参考资料，它在各章之间分布相当广泛。

我将总结手册中的内容，并在适当的地方添加详细信息：

分支预测是核心中 BPU 单元（Branch Prediction Unit）的工作。与您的问题中的“BP”大致相关。它包含几个子单元：

  • 分支历史表。该表跟踪先前采用的条件分支，并由预测器查询以确定是否可能采用分支。Is 由指令引退单元提供条目，该单元知道是否实际采用了分支。这是随着架构的改进而变化最大的子单元，随着更多房地产的出现，它变得更深入和更智能。

  • BTB，分支目标缓冲区。此缓冲区存储先前采用的间接跳转或调用的目标地址。这与您问题中的“BTP”相关。手册没有说明缓冲区是否可以在每个地址存储多个目标，由历史表索引，我认为它可能适用于以后的架构。

  • 返回堆栈缓冲区。该缓冲区充当“影子”堆栈，存储 CALL 指令的返回地址，使 RET 指令的目标可以高度可靠地可用，而处理器不必依赖 BTB，不太可能对调用有效。它被记录为 16 级深。

Bullet 2）有点难以准确回答，该手册仅谈论“前端”，并没有分解管道的细节。足够合适，它严重依赖于架构。第 2.2.5 节中的图表可能是说明性的。执行跟踪缓存发挥作用，它存储以前解码的指令，因此是 BPU 咨询的主要来源。否则就在指令翻译器（又名解码器）之后。

于 2014-03-23T16:17:11.627 回答
16

BP 和 BTP 自然密切相关，但它们显然不是一回事。我认为您最大的困惑来自声称由于 BTP 预测给定分支的目标，它可以告诉您结果（即 - 下一条执行的指令将是什么）。事实并非如此。

分支目标是该分支可能会将您发送到的地址（如果已被占用）。是否采用分支是一个完全不同的问题，由分支预测器解决。事实上，这两个单元通常会在流水线的早期阶段一起工作 - 并产生（如果需要）被采用/不被采用和地址预测。然后是基本上说的复杂逻辑 - 如果它是一个分支，并且它被预测采用（或无条件），那么如果你有它（无论是已知的还是预测的）跳转到目标。

正如您在分支类型列表中引用自己的那样 - 分支是否需要预测被采用的问题（是否有条件），以及分支是否需要预测目标（您称之为直接/固定目标）两者都适用，并且每个都可以双向进行，彼此无关，从而为您提供列出的 4 个选择：

  • 理论上，无条件直接分支不需要任何预测——CPU 前端将简单地读取目标并“采用”分支（从新地址提供管道代码）。然而，现代 CPU 仍然需要时间来解码分支并识别在那里编码的目标，因此为了避免分支预测器（通常位于管道的头部）处的停顿，它们还必须预测该地址。虽然确认预测很简单（在解码后立即），所以预测错误的惩罚不是很高。由于代码缓存/ tlb 未命中，它仍可能停滞不前，但它是最快的（但有人可能会说是最弱的）

  • 条件直接分支在解码后知道他们的目标（但再次 - 必须提前预测它），但在执行条件并做出解决方案之前无法判断是否采用分支，这可能在很远的地方管道。这反过来可能取决于早期的指令，并且可能会停止，直到条件源已知为止。所以有两个预测 - 目标和方向（除非方向是失败的，在这种情况下不需要目标），但方向分辨率是风险更大的一个。分支预测器（实际上，在现代 CPU 上通常有几个）会做出有根据的猜测并继续从那里获取。甚至已经进行了一些研究，主要是在学院中，在尝试获取和执行两条路径时（尽管您可以立即看到这可能会呈指数级增长，因为您通常每隔几条指令就有一个分支，因此它通常保留给难以预测的路径）。另一个流行的选项是“预测”（注意那里的'a'..）这两个路径，即沿着管道发送一些位以标记它是哪条路径，以便在知道分辨率后轻松刷新错误的路径。由于语言结构，这在数据流机器上非常流行，但这是一个全新的问题。一旦知道分辨率，就可以轻松冲洗错误的路径。由于语言结构，这在数据流机器上非常流行，但这是一个全新的问题。一旦知道分辨率，就可以轻松冲洗错误的路径。由于语言结构，这在数据流机器上非常流行，但这是一个全新的问题。

  • 无条件的间接分支 - 这些很讨厌，因为它们都很常见（每个ret例如），而且更难预测。虽然在前一种情况下分支解析很简单（并且总是依赖于一些启发式或模式猜测），但这个需要提供一个实际地址，因此您可能需要使用这个特定目标访问这个特定分支几次才能让BTP 在那里学习模式。

  • 有条件的间接分支 - 好吧，你运气不好，你需要两个预测......

因此，决策是正交的，但这并不意味着预测变量必须如此。请记住，您只有一个分支历史“流”，因此以某种方式与预测器相关联，共享一些表或一些逻辑可能是值得的。设计决策究竟如何，取决于实际的硬件实现，您可能不会获得有关英特尔/AMD 如何做到这一点的大量细节，但有大量关于该主题的学术研究。

至于第二个问题 - 它有点宽泛，而且 - 你将无法获得真实 CPU 的所有确切细节，但你可以在这里和那里得到提示 - 例如参见这个Haswell 评论中的图表（其中可能在某个地方之前出现过）：

哈斯韦尔框图

这张图并不能告诉你一切，它显然缺少 BP/BTP 的输入，甚至它们之间的区别（这本身已经告诉你它们可能是一起构建的），但它确实向你表明这显然是管道的首要部分. 您需要预测下一条指令指针，然后才能继续并将其输入 fetch/decode/... 管道（或替代的 uop-cache 管道）。这可能意味着 CPU 通过考虑接下来要执行的指令来启动每个周期（嗯，是的，所有事情实际上都是并行完成的，但将管道视为分阶段的过程会有所帮助）。假设他知道我们上次在哪里，所以它要么是非分支指令（啊，但是长度变化呢......这个单元需要解决的另一个复杂问题），或者是一个分支，

请注意，我写了“猜测”——如果图表告诉你，解码阶段真的很远，你甚至不知道它是一个分支。所以要回答你的问题 - 这个 BP/BTP 单元需要与执行/WB 单元通信，以便它可以知道条件分支的结果，使用解码单元，这样它就可以知道当前决定的指令是什么分支以及它的类型是，使用不同的 fetch 管道为它们提供输出。我猜测与其他单元有进一步的关系（例如，某些设计可能决定根据目标预测发送代码预取等）。

于 2014-03-22T22:29:16.153 回答