分支目标预测与分支预测相结合？

Question

编辑:我的混乱是因为肯定通过预测采取了哪个分支,你是否也在有效地进行目标预测？

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

分支预测与分支目标预测

看看接受的答案:

无条件分支,固定目标

• 无限循环
• 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.BTP是否也恰好确定位于branch a/ 的代码的地址b,具体取决于BP的结果？

我问这个维基百科页面(http://en.wikipedia.org/wiki/Branch_target_predictor):

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

它表明BTP用于在预测条件后预测目标.

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

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

2)BTP如何处理fetch/decode/execute/write-back CPU阶段？

Answer 1

请阅读英特尔优化手册,当前下载位置在这里.陈旧时(他们一直在移动东西)然后在英特尔网站上搜索"架构优化手册".请记住,这些信息非常通用,它们只披露了编写高效代码所需的内容.分支预测实现细节被视为商业秘密,并且在架构之间进行更改.在手册中搜索"分支预测"以查找参考文献,它在各章之间相当普遍.

我将概述手册中的内容,并在适当的地方添加详细信息:

分支预测是核心(分支预测单元)中BPU单元的工作.与您的问题中的"BP"大致相关.它包含几个子单元:

• 分支历史表.该表跟踪先前采用的条件分支,并由预测器查询以确定是否可能采用分支.是由指令退休单元提供条目,该单元知道分支是否实际被采用.随着架构的改进,这个子单元发生了最大的变化,随着更多的房地产可用,它变得越来越智能.

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

• 返回堆栈缓冲区.该缓冲区作为"影子"堆栈,存储CALL指令的返回地址,使得RET指令的目标可以高度可靠地获得,而处理器不必依赖BTB,这对呼叫不太有效.记录为16级深度.

Bullet 2)有点难以准确回答,手册只讨论"前端"并没有细分管道的细节.足够合适,它依赖于架构.2.2.5节中的图表可能是说明性的.执行跟踪缓存起作用,它存储先前解码的指令,因此是BPU咨询的主要来源.否则就在指令翻译器(aka解码器)之后.

Answer 2

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

分支目标是此分支可能发送给您的地址(如果已执行).是否采用分支是一个完全不同的问题,并由分支预测器解决.实际上,这两个单元通常在管道的早期阶段一起工作 - 并且产生(如果需要)采取/不采用和地址预测.然后是基本上说的复杂逻辑 - 如果它是一个分支,并且它被预测(或者是无条件的),那么如果你拥有它(无论是已知的还是预测的),就跳转到目标.

正如你在分支类型列表中引用自己一样 - 分支是否需要预测被采取的问题(是否有条件),以及分支是否需要预测目标(当你调用它时它是直接/固定目标)是适用的,每个都可以双向无关,从而为您提供您列出的4个选择:

• 从理论上讲,无条件直接分支不需要任何预测 - CPU前端只需读取目标并"获取"分支(从新地址提供管道代码).但是,现代CPU仍然需要时间来解码分支并识别在那里编码的目标,因此为了避免分支预测器(通常位于管道的头部)处的停顿,他们还必须预测该地址.确认预测很简单(在解码后立即),因此错误预测的惩罚不是很高.由于代码缓存/ tlb未命中,它仍然可能会停滞,但是否则最快(但可能会说最弱)

• 条件直接分支在解码后知道它们的目标(但是再次 - 必须在它之前预测它),但是不能判断分支是否被采用,直到执行条件并且进行分辨,这可能是非常远的管.这反过来可能取决于先前的指令,并且可能会在条件源已知之前停止.所以有两个预测 - 目标和方向(除非方向是直通的,在这种情况下不需要目标),但方向分辨率更危险.分支预测器(实际上,在现代CPU上通常有几个),会做出有根据的猜测并继续从那里取出.有些研究甚至在学院中主要试图获取并执行两条路径(尽管你可以立即看到这可能会成倍地爆炸,因为你通常每隔几条指令都有一个分支,所以它通常被保留为难以 - 预测的).另一个流行的选择是"预测"(记住'a'那里......)两条路径,即沿管道发送一些位以标记它是哪条路径,以便在知道分辨率后轻松刷新错误的路径.由于语言结构的原因,这在数据流机器上非常流行,但这是一个全新的问题.

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

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

因此,决策是正交的,但这并不意味着预测者必须如此.请记住,您有一个分支历史记录的"流",因此以某种方式使预测变量相关,共享某些表或某些逻辑可能是值得的.一个设计决策究竟是什么,取决于实际的硬件实现,你可能不会得到很多有关英特尔/ AMD如何做到这一点的详细信息,但是有很多关于该主题的学术研究.

至于第二个问题 - 它有点宽泛,再次 - 你将无法获得真实CPU的所有细节,但你可以在这里和那里得到提示 - 参见例如Haswell评论中的图表(其中可能在某处出现在这里):

这个图并没有告诉你一切,它显然缺少BP/BTP的输入,甚至它们之间的区别(它本身已经告诉你它们可能是一起构建的),但它确实向你显示这显然是管道的第一个也是最重要的部分.您需要预先确定下一个指令指针,然后才能将其提供给fetch/decode/...管道(或替代的uop-cache管道).这可能意味着CPU开始每个周期(好吧,是的,一切都是并行完成的,但它有助于将管道视为一个分阶段的过程),通过思考下一步要执行的指令.假设他知道我们最后一次在哪里,所以它是一个非分支指令(啊,但是长度不一样......这个单元需要解决的另一个复杂因素),或者一个分支,在这种情况下这个单位应该猜测哪个此分支所属的上述类型,并相应地预测下一条指令.

请注意,我写了"猜测" - 如果图表说实话,解码阶段真的很远,你甚至不知道它在这一点上是一个分支.所以回答你的问题 - 这个BP/BTP单元需要与执行/ WB单元进行通信,这样才能知道条件分支的结果,使用解码单元,这样就可以知道当前正在决定的指令是一个分支,它是什么类型的是,使用不同的提取管道来输出它们.我猜测与其他单位有进一步的关系(例如,某些设计可能决定根据目标预测发送代码预取等).