Branch Target Buffer检测到哪些分支错误预测？

Question

我目前正在查看CPU管道的各个部分,它们可以检测分支错误预测.我发现这些是:

1. 分支目标缓冲区(BPU CLEAR)
2. 分支地址计算器(BA CLEAR)
3. 跳转执行单元(这里不确定信号名称？)

我知道2和3检测到了什么,但我不明白在BTB中检测到了什么错误预测.BAC检测BTB错误地预测非分支指令的分支的位置,其中BTB未能检测到分支,或者BTB错误预测了x86 RET指令的目标地址.执行单元评估分支并确定它是否正确.

在分支目标缓冲区中检测到什么类型的错误预测？究竟在这里发现了什么错误预测？

我能找到的唯一线索是英特尔开发者手册第3卷(底部的两个BPU CLEAR事件计数器):

BPU在错误地认为未采取分支后预测了一个分支.

这似乎暗示预测并非"同步",而是"异步",因此"在错误地假设"之后？

更新:

Ross,这是CPU分支电路,来自最初的英特尔专利(如何用于"阅读"？):

我在任何地方都看不到"分支预测单位"？读过这篇论文的人会认为"BPU"是将BTB电路,BTB缓存,BAC和RSB分组在一起的懒惰方式吗？

所以我的问题仍然存在,哪个组件会引发BPU CLEAR信号？

Answer 1

这是一个很好的问题!我认为它造成的混乱是由于英特尔奇怪的命名方案,这些方案经常超出学术界的标准.我会尽力回答你的问题,并澄清我在评论中看到的困惑.

首先.我同意在标准计算机科学术语中,分支目标缓冲区不是分支预测器的同义词.然而,在英特尔术语中,分支目标缓冲区(BTB)[大写字母]是特定的东西,包含预测器和分支目标缓冲区高速缓存(BTBC),它只是一个分支指令表及其在所采用结果上的目标.这个BTBC是大多数人所理解的分支目标缓冲区[小写].那么什么是分支地址计算器(BAC)？如果我们有BTB,为什么还需要它呢？

因此,您了解现代处理器分为多个阶段的管道.无论这是一个简单的流水线处理器还是一个乱序的超级处理器,第一阶段通常是获取然后解码.在获取阶段,我们所拥有的只是程序计数器(PC)中包含的当前指令的地址.我们使用PC从内存加载字节并将它们发送到解码阶段.在大多数情况下,我们增加PC以加载后续指令,但在其他情况下,我们处理控制流指令,它可以完全修改PC的内容.

BTB的目的是猜测PC中的地址是否指向分支指令,如果是,那么PC中的下一个地址应该是什么？没关系,我们可以使用条件分支的预测器和下一个地址的BTBC.如果预测是正确的,那太好了!如果预测错了,那么呢？如果BTB是我们唯一的单位,那么我们将不得不等到分支到达管道的发布/执行阶段.我们必须冲洗管道并重新开始.但并非所有情况都需要这么晚才得到解决.这是分支地址计算器(BAC)的用武之地.

BTB用于流水线的获取阶段,但BAC位于解码阶段.一旦我们获取的指令被解码,我们实际上有更多可用的信息.我们所知道的第一条新信息是:"我提供的指令实际上是一个分支吗？" 在获取阶段,我们不知道和BTB只能猜测,但在解码阶段,我们知道这是肯定的.当实际上指令不是分支时,BTB可能预测分支; 在这种情况下,BAC将暂停获取单元,修复BTB,并重新正确地重新获取.

什么样的分支unconditional relative和call？这些可以在解码阶段验证.BAC将检查BTB,查看BTBC中是否有条目并将预测器设置为始终预测已采用.对于conditional分支机构,BAC无法确认它们是否被采用,但它可以至少验证预测的地址并在地址预测错误的情况下纠正BTB.有时BTB根本不会识别/预测分支.BAC需要纠正此问题并向BTB提供有关此指令的新信息.由于BAC没有自己的条件预测器,因此它使用一种简单的机制(采用向后分支,不采用前向分支).

有人需要确认我对这些硬件计数器的理解,但我认为它们意味着以下内容:

• BACLEAR.CLEAR 当获取中的BTB 做坏事并且解码中的BAC 可以修复它时,递增.
• BPU_CLEARS.EARLY当获取决定(错误地)加载下一条指令之前,如果BTB预测它应该实际从所采用的路径加载,则递增.这是因为BTB需要多个周期并且fetch使用该时间来推测性地加载连续的指令块.这可能是因为英特尔使用两个BTB,一个快速,另一个更慢但更准确.获得更好的预测需要更多周期.

这解释了为什么在BTB中检测到错误预测的惩罚是2/3周期,而在BAC中检测到错误预测的则是8个周期.

Answer 2

事实BPU_CLEARS.EARLY描述表明，当 BPU 预测时发生此事件，更正假设，这意味着前端有 3 个阶段。假设、预测和计算。我目前的猜测是，当预测被“采用”而不是“不采用”时，早期清除正在刷新来自 L1 BTB 的预测甚至已知阶段之前的管道阶段。

BTB 集包含 4 路，每 16 字节最多有 4 个分支（其中所有路都用相同的标签标记，指示特定的 16 字节对齐块）。每路都有一个偏移量，指示地址的 4 个 LSB，因此字节位置在 16 个字节内。每个条目还有一个推测位、有效位、pLRU 位、一个推测本地 BHR、一个真实本地 BHR，并且每条路共享集合 BPT（PHT）作为第二级预测。这可能与 GHR / 投机 GHR 混合。

我认为BPU为uop缓存和指令缓存提供了一个64B的预测块（以前是32B，P6上是16B）。对于传统路由，它需要提供一个 64（或 32/16）字节的预测块，它是一组 64 位掩码，用于标记预测的分支指令、预测方向以及哪个字节是分支目标。该信息将由 L1 BTB 提供，同时对 64 字节行的提取正在进行中，这样 16 字节对齐（IFU 一直是 16B）的块将不会被从它读出而根本没有使用位的块被提取指令预解码器（未使用是默认设置，因为在预测块小于行大小的体系结构上，BPU 可能只为行的 16 或 32B 提供位掩码）。因此，BPU 提供了做出的预测掩码，使用/未使用掩码（将第一个预测块中第一个分支后和第二个预测块中的分支目标之前的字节标记为未使用，其余使用），预测方向掩码；ILD 提供分支指令掩码。预测块中第一个使用的字节隐含地是分支目标或指令流的开始，在从 uop 缓存 (DSP) 重新转向或切换到传统流水线 (MITE) 之后。预测块内使用的字节构成预测窗口。

这是一个 P6 管道。以此为例，在第 3 个周期 (13) 中进行早期清除，此时进行预测（并且读取目标和条目类型，因此现在知道无条件分支目标以及有条件及其预测）。使用 16 字节块的集合中第一个预测的分支目标。此时，它之前的 2 个管道阶段已经填充了从下一个连续的 16 字节块开始的获取和查找，这意味着如果有任何预测，则需要刷新它们（否则不需要因为下一个连续的 16 字节块已经开始在它之前的管道阶段中查找），留下 2 个周期的间隙或气泡。缓存查找与 BTB 查找同时发生，因此，BTB 和缓存并行 2 个管道阶段都必须刷新，而第三阶段不需要从缓存或 BTB 中刷新，因为 IP 位于已确认的路径上，并且当前正在查找 IP下一个。事实上，在这个P6设计中，只有一个这个早期清除的一个周期气泡，因为新的 IP 可以被发送到第一阶段以在时钟的高沿再次解码一组，而其他阶段正在被刷新。

这种流水线操作比在开始查找下一个 IP 之前等待预测更有益。这意味着每隔一个周期进行一次查找。这将提供每 2 个周期 16 字节预测的吞吐量，因此为 8B/c。在 P6 流水线场景中，正确假设下的吞吐量为每周期 16 字节，错误假设下为 8B/c。显然更快。如果我们假设 2/3 的假设是正确的，因为 9 条指令中的 1 条指令是每块 4 条指令的分支，那么每个 ((1*0.666)+2*0.333)) =1.332 个周期的吞吐量为 16B，而不是 16B每 2 个周期。

如果这是真的，每个被采用的分支都会导致早期清除。但是，当我在 KBL 上使用该事件时，情况并非如此。希望该事件实际上是错误的，因为我的 KBL 不支持它，但确实显示了一个随机的低数，因此希望它计算其他内容。这似乎也不支持以下https://gist.github.com/mattgodbolt/4e2cbb1c9aa97e0c5478 https://github.com/mattgodbolt/agner/blob/master/tests/branch.py。鉴于 900k 指令和 100k 早期清除，如果您使用我对早期清除的定义然后查看他的代码，我不明白您如何拥有奇数数量的早期清除。如果我们假设该 CPU 的窗口是 32B，那么如果您在该宏中的每个分支指令上使用 4 对齐，则每 8 条指令都会得到一个清晰的结果，因为 8 将适合 32B 对齐的窗口。

我不确定为什么Haswell 和 Ivy Bridge对早期和晚期清除有这样的值，但这些事件 (0xe8)从 SnB 开始消失，这恰好与 BTB 统一为单个结构的时间相吻合。看起来延迟清除计数器现在正在计算早期清除事件，因为它与 Arrandale CPU 上的早期清除数量相同，而早期清除事件现在不计数。我也不确定为什么 Nehalem 有一个 2 周期的泡沫用于早期清除，因为 L1 Nehalem BTB 的设计似乎与 P6 BTB 没有太大变化，这两个条目都是 512 个条目，每组 4 个方式。这可能是因为由于更高的时钟速度以及更长的 L1i 缓存延迟，它已被分解为更多阶段。

晚晴 ( BPU_CLEARS.LATE)似乎发生在 ILD。在上图中，缓存查找只需要 2 个周期。在较新的处理器中，它显然需要 4 个周期。这允许插入另一个 L2 BTB 并在其中进行查找。“MRU 旁路”和“MRU 冲突”可能仅意味着 MRU BTB 中存在未命中，或者也可能意味着 L2 中的预测与 L1 中的预测不同，如果它使用不同的预测算法并且历史档案。在我的 KBL 上，它不支持任何一个事件，我总是得到 0ILD_STALL.MRU但不是BPU_CLEARS.LATE. 3 个周期的气泡来自第 5 阶段（也是 ILD 阶段）的 BPU，在第 1 阶段的低边缘重新引导管道并刷新第 2、3 和 4 阶段（这与引用的 4 个周期的 L1i 延迟一致，因为 L1i 查找发生在第 1-4 阶段，用于命中 + ITLB 命中）。一旦做出预测，BTB 就用做出的预测更新条目的推测性本地 BHR 位。

例如，当 IQ 将预测的掩码与预解码器产生的分支指令掩码进行比较时，就会发生 BACLEAR，然后对于某些指令类型（如相对跳转），它将检查符号位以执行静态分支预测。我想静态预测一旦从预解码器进入 IQ 就会发生，这样立即进入解码器的指令包含静态预测。现在被预测采取的分支会导致a BACLEAR_FORCE_IQwhen 分支指令被解码，因为BAC计算相对条件分支指令的绝对地址时不会有目标验证，需要在预测时验证采取。

解码器处的 BAC 还确保相对分支和直接分支在从指令本身计算绝对地址并与之比较后具有正确的分支目标预测，如果不是，则发出 BACLEAR。对于相对跳转，如果 BTB 不支持返回条目类型（它不在 P6 上并且不进行预测，而是 BAC 使用 BPU 的 RSB 机制，它是管道中确认返回指令的第一个点）并覆盖在 P6 上采用的所有寄存器间接分支预测（因为没有IBTB），因为它使用的统计数据是采用更多分支而不是采用。分配器使用 uop 中的这些字段稍后分配到 RS/ROB。BAC 还通知 BTB 任何需要从 BTB 取消分配条目的虚假预测（非分支指令）。在解码器中，分支指令在逻辑的早期被检测到（当前缀被解码并检查指令以查看它是否可以被解码器解码时），并且 BAC 与其余指令并行访问。将已知或以其他方式预测的目标插入uop的 BAC 称为将 auop 转换为 duop。预测被编码到 uop 操作码中。

BAC 可能会指示 BTB 针对检测到的分支指令的 IP 推测性地更新其 BTB。如果现在知道目标并且没有对其进行预测（意味着它不在缓存中）——它仍然是推测性的，虽然分支目标是确定的，但它仍然可能处于推测路径上，所以是标有推测位——这现在将立即提供早期转向，特别是对于现在进入管道的无条件分支，但也有条件的，具有空白历史，因此将预测下次不会被采用，而不必等到退休）。

上面的 IQ包含一个位掩码字段，用于分支预测方向 (BTBP) 和分支预测/未预测 (BTBH)（以区分 BTBP 中的哪些 0 没有被采用，而不是没有预测）。 IQ 行中的指令字节以及分支指令的目标，这意味着每个 IQ 行只能有一个分支，并结束该行。该图没有显示由预解码器生成的分支指令掩码，该掩码显示哪些指令实际上是分支，以便 IQ 知道它需要进行哪些未做出的预测（以及哪些根本不是分支指令）。

IQ 是一个连续的指令字节块，ILD 填充 8 位位掩码，这些位掩码标识每个宏指令的第一个操作码字节 (OpM) 和指令结束字节 (EBM)，因为它将圆形字节包装到 IQ 中。它还可能提供指示它是复杂指令还是简单指令的位（如许多 AMD 专利中的“预解码位”所建议的那样）。这些标记之间的间隙是以下指令的隐式前缀字节。我认为 IQ 的设计使得它在 IDQ/ROB 中发出的 uops 很少会超过 IQ，这样 IQ 中的头指针就会开始覆盖仍在等待分配的 IDQ 中标记的宏指令，当它发生时，有一个停顿，所以 IDQ 标签引用回分配器访问的 IQ。我认为 ROB 也使用这个 uop 标签。如果 16 字节 * 40 个条目，则 SnB 上的 IQ 在最坏情况下包含 40 个宏操作，在平均情况下为 320，在最佳情况下为 640。这些产生的 uops 数量会更多，所以它很少会超过，当它发生时，我猜它会停止解码，直到更多指令退出。尾指针包含ILD最近分配的标签，头指针包含等待退出的下一条宏指令指令，读指针是解码器要消耗的当前标签（向尾指针移动）。尽管如此，现在这变得很困难，因为自 SnB 以来，路径中的一些（如果不是大多数）uop 来自 uop 缓存。如果 uop 没有用 IQ 条目标记（并且 IQ 中的字段直接插入到 uops 中），则可以允许 IQ 超过后端，

当分配器为分支微操作分配物理目的地 (Pdst) 到 ROB 中时，分配器将 Pdst 条目号提供给 BPU。BPU 将其插入到 BAC 分配的正确 BIT 条目中（它可能位于尚未分配 Pdst 的活动 BIT 条目循环队列的头部）。分配器还从 uop 中提取字段并将数据分配到 RS。

RS 包含一个字段，该字段指示指令是 MSROM uop 还是由分配器填充的常规 uop。分配器还将确认的绝对目标或预测的绝对目标插入立即数据中，并作为源，重命名标志寄存器（或只是一个标志位），在间接分支的情况下，还有重命名的寄存器包含地址作为另一个来源。PRF 方案中的 Pdst 将是 ROB 条目，作为 Pdst，它将是退休宏 RIP 或微 IP 寄存器。JEU 将目标或失败写入该寄存器（如果预测正确，则可能不需要）。

当保留站向位于整数执行单元中的跳转执行单元调度分支微操作时，保留站将对应的分支微操作的Pdst表项通知给BTB。作为响应，BTB 访问 BIT 中分支指令的相应条目，并读出落入 IP（NLIP），减去 RS 中的 IP delta，并解码为指向分支条目将被设置的集合更新/分配。

然后将重命名的标志寄存器源 Pdst 的结果与调度器中操作码中的预测进行比较，如果分支是间接的，则将 BIT 中的预测目标与源 Pdst 中的地址（在调度和调度之前计算并在 RS 中可用），现在知道是否做出了正确的预测以及目标是否正确。

JEU 将异常代码传播到 ROB 并刷新管道（JEClear - 它在分配阶段之前刷新整个管道，并停止分配器）并使用 fallthrough 在管道开始处重定向下一个 IP 逻辑（在 BIT 中）/适当的目标 IP（以及微序列器，如果它是微分支错误预测；指向管道起点的 RIP 在整个 MSROM 过程中将是相同的）。推测条目被解除分配并且真正的 BHR 被复制到推测 BHR 中。如果 PRF 方案中存在 BOB，则 BOB 会为每个分支指令以及在出现错误预测时拍摄 RAT 状态的快照。JEU 将 RAT 状态回滚到该快照，并且分配器可以立即继续（这对于微分支错误预测特别有用，因为它更接近分配器，因此气泡不会被管道很好地隐藏），而不是停止分配器并且必须等到退休才能知道退休 RAT 状态并使用它来恢复 RAT，然后清除 ROB（ROClear，它使分配器停止运行）。使用 BOB，分配器可以在陈旧的 uops 继续执行时开始发出新指令，并且当分支准备退出时，ROClear 仅清除退出的错误预测和新的 uops 之间的 uops。如果是MSROM uop，因为可能已经完成，管道的开始还需要重新重定向到MSROM uop，

ROClear 响应 ROB 中的分支异常向量实际上发生在第二个退休阶段 RET2（实际上是典型退休管道的 3 个阶段中的第 3 个阶段）上，当 uops 退休时。当 EOM uop（宏指令结束）标记退出时，宏指令只退出，异常只触发，宏指令 RIP 只更新（新目标或在 ROB 中增加 IP 增量），即使非 EOM 指令写入它，它与其他寄存器不同，它不会立即写入 RRF——无论如何，分支 uop 很可能是解码器处理的典型分支宏指令中的最终 uop。如果这是 MSROM 程序中的微分支，则不会更新 BTB；它在退出时更新 uIP，直到程序结束才更新 RIP。

如果在 MSROM 宏操作执行期间发生通用非错误预测异常（即需要处理程序的异常），一旦它被处理，导致异常的 microip 由处理程序恢复到 uIP 寄存器（如果它是调用时传递给处理程序），以及触发异常的宏指令的当前 RIP，当异常处理结束时，在此 RIP+uIP 处恢复取指令：宏指令在 MSROM 中重新取回并重新尝试，它从向它发出信号的 uIP 开始。复杂的非 MSROM 宏指令中先前 uop 的 RRF 写入（或 PRF 方案上的退休 RAT 更新）可能发生在 EOM uop 退休之前的周期中，这意味着重启可以在常规复杂宏操作中的某个 uop 发生，而不仅仅是 MSROM 宏操作，在这种情况下，指令流在 RIP 的 BPU 处重启，复杂解码器在 PLA 上配置有效/无效位输出. 这个用于配置复杂解码器有效位的常规复杂指令的 uIP 是一个介于 0-3 之间的值，我认为 ROB 在每个 EOM 时设置为 0，并且每个微操作都退出了增量，以便非 MSROM 复杂指令可以被寻址，对于 MSROM 复杂指令，MSROM 例程包含一个 uop，它告诉 ROB 该指令的 uIP。然而，架构 RIP 寄存器，仅在 EOM uop 退出时才由 IP delta 更新仍然指向当前的宏操作，因为 EOM uop 未能退出），这只发生在异常情况下但不是硬件中断，它不能中断 MSROM 程序或复杂的指令中间退出（软件中断类似并在 EOM 触发——一旦完成，陷阱 MSROM 处理程序执行到软件陷阱处理程序的 RIP 的宏跳转）。

BTB 读取和标签比较发生在 RET1 中，而分支单元写回结果，然后在下一个循环中，也许也在 RET1 期间（或者这可能在 RET2 中完成），比较集合中的标签，然后，如果有命中，计算新的历史BHR；如果未命中，则需要在该 IP 上为该目标分配一个条目。只有当 uop 按顺序退出时（在 RET2 中）才能将结果放入真实历史中，并且使用分支预测算法来更新需要更新的模式表。如果分支需要分配，则利用替换策略来决定分配分支的方式。如果命中，则所有直接和相对分支的目标都已经正确，因此在没有 IBTB 的情况下不必进行比较。如果存在，现在从条目中删除推测位。最后，在下一个周期，该分支由 BTB 写控制逻辑写入 BTB 缓存中。BTB 查找的第一部分可能能够在整个 RET1 中继续进行，然后可能会在等待写入 BTB 的 ROB 条目的阶段退休时停止 BTB 写入管道，直到 RET2，否则，查找可以解耦并且第一部分完成并将数据写入，例如，BIT，并且在 RET2 处，将退休的相应条目写回 BTB（这意味着再次解码集合，再次比较标签，然后写入条目，所以可能不会）

如果 P6 有一个 uop 缓存，管道将是这样的：

• 1H：选择IP
• 1L：BTB设置解码+缓存设置解码（物理/虚拟索引）+ITLB查找+uop缓存设置解码
• 2H：缓存读+BTB读+uop缓存读
• 2L：缓存标签比较+BTB标签比较+uop缓存标签比较；如果 uop 缓存命中，则停止直到 uop 缓存可以发出，然后时钟门传统解码管道
• 3H：预测，如果采取，冲洗 3H,2L,2H,1L
• 3L 如果采用，则使用新 IP 开始 1L 以解码新组并继续分支指令所在的当前 16 字节块到 4L

至于 uop 缓存，因为已经过了 BAC 阶段，所以永远不会出现虚假分支或无条件分支的错误预测或非间接分支的错误目标。uop 缓存将使用来自 BPU 的已使用/未使用掩码为从这些字节开始的指令发出 uops，并将使用预测方向掩码将宏分支 uops 更改为预测未采用/预测采用宏分支 uop (T/NT预测被插入到 uop 本身中）。如果它被预测采用，那么它会停止为那个 64B 对齐的块（再次使用 32B，以前是 16B）发出 uops，并等待管道中紧随其后的下一个窗口。uop 缓存将知道哪些 uop 是分支，并且可能静态预测不采用所有非预测，或者可能有更高级的静态预测。来自 IBTB 的间接目标预测被插入到 uop 立即字段中，然后如果该分支也被预测采用，它将等待下一个 BPU 预测块。我会想象 uop 缓存在 BTB 中创建 BIT 条目并更新预测，以确保 uop 缓存和 MITE（传统解码）uop 以正确的顺序更新历史记录。