跳转至

AMD Zen 3 的 BTB 结构分析

背景

在之前，我们分析了 AMD Zen 1 和 AMD Zen 2 的 BTB，接下来分析它的再下一代微架构：2020 年发布的 AMD Zen 3 的 BTB，看看 AMD 的 Zen 系列的 BTB 是如何演进的。

官方信息

AMD 在 Software Optimization Guide for AMD EPYC™ 7003 Processors (Publication No. 56665) 中有如下的表述：

The branch target buffer (BTB) is a two-level structure accessed using the fetch address of the previous fetch block.

Zen 3 的 BTB 有两级，相比 Zen 1 和 Zen 2 少了一级。BTB 是用之前 fetch block 的地址去查询，而不再是当前 fetch block 的地址。用当前 fetch block 的地址查询 BTB 很好理解，要寻找某个地址开始的第一个分支，就用这个地址去查询 BTB，Zen 1 和 Zen 2 都是如此；用之前 fetch block 的地址，则是用更早的信息，去获取当前 fetch block 的信息，例如：

entrypoint1:
    jmp entrypoint2

entrypoint2:
    # what's the first branch after entrypoint2?

在查询从 entrypoint2 开始的第一条分支指令的时候，如果使用当前 fetch block，就是用 entrypoint2 的地址去查询，那就必须等到前面 jmp entrypoint2 指令的目的地址被计算得出；如果使用之前 fetch block，就是用 entrypoint1 的地址去查询，不用等到 jmp entrypoint2 指令的目的地址被计算得出。因此，如果用之前 fetch block，可以更早地进行 BTB 的访问，从而减少 BTB 的延迟，或者在相同延迟下获得更大的容量。但是，代价是：

  • 从 entrypoint1 跳转到的 fetch block 可能有多个，例如最后一条是间接分支指令，那就需要找到正确的分支的信息
  • 可能会从不同的地址跳转到 entrypoint2 这个 fetch block，因此它的信息可能会保存多份

Each BTB entry can hold up to two branches if the last bytes of the branches reside in the same 64-byte aligned cache line and the first branch is a conditional branch.

Zen 3 的 BTB entry 有一定的压缩能力，一个 entry 最多保存两条分支，前提是两条分支在同一个 64B 缓存行中，并且第一条分支是条件分支。这样，如果第二条分支是无条件分支，分支预测的时候，可以根据第一条分支的方向预测的结果，决定要用哪条分支的目的地址作为下一个 fetch block 的地址。虽然有压缩能力，但是没有提到单个周期预测两条分支，所以只是扩大了等效 BTB 容量。和 Zen 1、Zen 2 一样。

L1BTB has 1024 entries and predicts with zero bubbles for conditional and unconditional direct branches, and one cycle for calls, returns and indirect branches.

Zen 3 的第一级 BTB 可以保存 1024 个 entry，但不确定这个 entry 是否可以保存两条分支，也不确定这个 entry 数量代表了实际的 entry 数量还是分支数量，后续会做实验证实；针对条件和无条件直接分支的预测不产生气泡，意味着它的延迟是一个周期。相比 Zen 2 容量翻倍，且延迟降低一个周期，猜测和使用 previous fetch block 有关。

L2BTB has 6656 entries and creates three bubbles if its prediction differs from L1BTB.

Zen 3 的第二级 BTB 可以保存 6656 个 entry，但不确定这个 entry 是否可以保存两条分支，也不确定这个 entry 数量代表了实际的 entry 数量还是分支数量，后续会做实验证实；预测会产生三个气泡，意味着它的延迟是四个周期。

简单整理一下官方信息，大概有两级 BTB：

  • 1024-entry L1 BTB, 1 cycle latency
  • 6656-entry L2 BTB, 4 cycle latency

相比 Zen 1 和 Zen 2 有比较大的不同：去掉了原来很小的 L0 BTB，扩大了 L1 BTB，同时延迟缩短了一个周期；虽然 L2 BTB 有所缩小，但是延迟也变短了一个周期。

下面结合微架构测试，进一步研究它的内部结构。

微架构测试

在之前的博客里，我们已经测试了各种处理器的 BTB，在这里也是一样的：按照一定的 stride 分布无条件直接分支，构成一个链条，然后测量 CPI。

考虑到 Zen 3 的 BTB 可能出现一个 entry 保存两条分支的情况，并且还对分支的类型有要求，因此下面的测试都会进行四组，分别对应四种分支模式：

  • uncond：所有分支都是无条件分支：uncond, uncond, uncond, uncond, ...
  • cond：所有分支都是条件分支：cond, cond, cond, cond, ...
  • mix (uncond + cond)：条件分支和无条件分支轮流出现，但 uncond 在先：uncond, cond, uncond, cond, ...
  • mix (cond + uncond)：条件分支和无条件分支轮流出现，但 cond 在先：cond, uncond, cond, uncond, ...

虽然 Zen 3 使用 previous fetch block 来访问 BTB，但在这几种分支模式中，使用 previous fetch block 还是访问 current fetch block，结果都是唯一的，所以并不会对结果带来影响。

stride=4B

首先是 stride=4B 的情况：

可以看到，图像上出现了三个比较显著的拐点：

  • 第一个拐点是 4 条分支，CPI=1，对应 L1 BTB，没有达到完整容量，可能是因为分支太过密集
  • 第二个拐点是 2048 条分支，CPI=3.6；第三个拐点是 4096 条分支，CPI=4/4.2/4.4

Zen 3 在 stride=4B 的情况下 L1 BTB 表现比较一般，应该是牺牲了高密度分支下的性能；而主要命中的是 L2 BTB，在不同的分支模式下，测出来差不多的结果。为了验证这一点，统计了如下的性能计数器（来源：Processor Programming Reference (PPR) for AMD Family 19h Model 21h, Revision B0 Processors）：

PMCx08B [L2 Branch Prediction Overrides Existing Prediction (speculative)] (Core::X86::Pmc::Core::BpL2BTBCorrect)

它代表了 L2 BTB 提供预测（准确地说，L2 BTB 提供了预测且和 L1 BTB 提供的预测结果不同，覆盖了 L1 BTB 的预测结果）的次数，当分支数不大于 4 的时候，这个计数器的值约等于零；此后快速上升，说明后续都是 L2 BTB 在提供预测。

更进一步观察，发现 2048 到 4096 的 CPI 上升，来自于 L1 BTB 完全失效：2048 条分支时，L1 BTB 还能提供约 10% 的预测，所以 CPI=0.1*1+0.9*4=3.7，但到 4096 条分支的时候，完全由 L2 BTB 提供分支，此时 CPI=4。

超过 4096 以后，则 L2 BTB 也开始缺失，出现了译码时才能发现的分支，如果这是一条 uncond 分支，那么会在译码时回滚，这一点可以通过如下性能计数器的提升来证明（来源：Processor Programming Reference (PPR) for AMD Family 19h Model 21h, Revision B0 Processors）：

PMCx091 [Decode Redirects] (Core::X86::Pmc::Core::BpDeReDirect): The number of times the instruction decoder overrides the predicted target.

但在 L2 BTB 缺失后，如果译码器发现了 cond 分支，会把它预测为不跳转，所以要等到执行才能发现分支预测错误。这就导致了 cond 模式下 L2 BTB 溢出时 CPI=16，而 uncond 模式下 L2 BTB 溢出时 CPI=12，提前在译码阶段发现了 uncond 分支并纠正。

但译码器的纠正能力不是万能的：假如它首先发现了一条 cond 分支，在它其后又发现了一条 uncond 分支，它会用 uncond 分支去纠正，但实际上前面的 cond 分支会跳转，所以此时译码器纠正也无法提升性能，即使 BpDeReDirect 计数器的值看起来很大。

stride=8B

接下来观察 stride=8B 的情况：

  • 第一个台阶在所有分支模式下都是 1024 个分支，CPI=1，对应 1024-entry 的 L1 BTB
  • 第二个台阶不太明显，但是在 4096 附近在所有分支模式下都是一个拐点，CPI=4，对应 L2 BTB；在 mix (uncond + cond) 模式下，超过 4096 分支后 CPI 缓慢上升，到 6144 条分支 CPI=4.25，到 6656 条分支 CPI=4.85，之后 CPI 快速上升；在 mix (cond + uncond) 模式下，到 5888 条分支 CPI=5。

L2 BTB 的容量不太确定，超过 4096 后需要一个 entry 保存两条分支才能获得更多容量，但也带来了一定的额外的延迟。与此同时 4096 也对应了 32KB ICache 的容量，这会对分析带来干扰。

从 BpDeReDirect 计数器来看，uncond 分支模式下，当分支数量超过 4096 后，L2 BTB 从 4096 时无缺失，之后缺失快速提升，说明此时 L2 BTB 容量确实是 4096。在 mix (cond + uncond) 模式下，分支数超过 4096 时，BpDeReDirect 计数器略微上升，直到 6144 条分支后才有明显的上升。

stride=16B

继续观察 stride=16B 的情况：

相比 stride=8B，L1 BTB 的行为没有变化。4096 对应的 CPI 有所下降，从 BpL2BTBCorrect 性能计数器可以发现是 L1 BTB 起了一定的作用。在 mix (cond + uncond) 模式下，直到 5632 条分支还维持了 CPI=3.25，之后 CPI 缓慢上升，到 6656 条分支时 CPI=3.75，到 6912 条分支时 CPI=4。

CPI=3.25 可能是来自于 1 和 4 的加权平均：25% 的时候是 1 周期，75% 的时候是 4 周期，平均下来就是 1*0.25+4*0.75=3.25。这意味着 L1 BTB 还要保持 25% 的命中率。观察 BpL2BTBCorrect 性能计数器，发现它的取值等于 75% 的分支执行次数，意味着 L1 BTB 确实提供了 25% 的预测，L2 BTB 提供了剩下 75% 的预测。这一点是挺有意思的，意味着 L1 BTB 可能采用了一些对这种循环访问模式友好的替换策略：朴素的 LRU（或类 LRU）替换策略会导致 L1 BTB 出现 100% 缺失。

stride=32B

继续观察 stride=32B 的情况：

相比 stride=16B，L1 BTB 的行为没有变化，但是出现了一些性能波动。所有分支模式下，L2 BTB 的拐点都出现在 5120，但性能波动比较大，mix (cond + uncond) 模式下的 CPI 达到了 4.6。通过 BpDeReDirect 性能计数器的变化，可以确认这个拐点确实是来自于 L2 BTB 的缺失。

前面提到，译码器的纠正能力可能会给出错误的答案，在 stride=32B 时，就会出现一个很有意思的现象：

  • 超出 L2 BTB 容量后，mix (uncond + cond) 模式下 BpDeReDirect 占分支数量的 50%
  • 超出 L2 BTB 容量后，mix (cond + uncond) 模式下 BpDeReDirect 占分支数量的接近 100%

解释起来也并不复杂：stride=32B 的情况下，一个 64B cacheline 只有两条分支，那么：

  • mix (uncond + cond) 模式下，第一条分支是 uncond，译码器会发现并 redirect；第二条分支是 cond，译码器会无视它，不进行 redirect；所以最后是 50% 的 redirect 比例
  • mix (cond + uncond) 模式下，第一条分支是 cond，译码器会看到后面的 uncond 分支并 redirect；第二条分支是 uncond，译码器会发现并 redirect；所以最后是接近 100% 的 redirect 比例

顺带一提，uncond 模式下的 BpDeReDirect 占分支数量的接近 100%，cond 模式下的 BpDeReDirect 占分支数量的 0%，都是符合预期的。

stride=64B

继续观察 stride=64B 的情况：

相比 stride=32B，L1 BTB 的容量减半，达到了 512。之后出现了比较明显的性能波动，但四种分支模式下，拐点依然都是出现在 5120 条分支的位置。通过 BpDeReDirect 性能计数器的变化，可以确认这个拐点确实是来自于 L2 BTB 的缺失。由于 uncond 模式下，BTB sharing 不会工作，意味着 L2 BTB 至少有 5120 个 entry。

stride=128B

继续观察 stride=128B 的情况：

相比 stride=64B，L1 BTB 的容量进一步减小，达到了 256；L2 BTB 的性能依然波动剧烈，但四种分支模式下，拐点依然都是出现在 5120 条分支的位置。

考虑到 5120 这个拐点频繁出现，认为 L2 BTB 在不考虑 BTB entry sharing 的情况下，实际容量应该是 5120。那么剩下的 1536 个分支就是来自于压缩。

小结

测试到这里就差不多了，更大的 stride 得到的也是类似的结果，总结一下前面的发现：

  • L1 BTB 是 1024-entry，1 cycle latency，容量随着 stride 变化，大概率是 PC[n:5] 这一段被用于 index，使得 stride=64B 开始容量不断减半
  • L2 BTB 是 5120-entry，4 cycle latency；其中有 1536 个 entry 最多保存两条分支，前提是这两条分支在同一个 cacheline 当中，并且第一条是 cond，第二条是 uncond

Zen 1 到 Zen 3 的 BTB 的对比

下面是对比表格：

uArch AMD Zen 1 AMD Zen 2 AMD Zen 3
L0 BTB size 4+4 branches 8+8 branches N/A
L0 BTB latency 1 cycle 1 cycle N/A
L1 BTB size 256 branches 512 branches 1024 branches
L1 BTB latency 2 cycles 2 cycles 1 cycle
L2 BTB size w/o sharing 2K branches 4K branches 5K branches
L2 BTB size w/ sharing 4K branches 7K branches 6.5K branches
L2 BTB latency 5 cycles 5 cycles 4 cycles
Technology Node 14nm 7nm 7nm
Release Year 2017 2019 2020

Zen 3 在 Zen 2 的基础上，没有更换制程，而是通过 previous fetch block 的方式，减少 L1 BTB 的延迟到 1 cycle，顺带去掉了 L0 BTB。L2 BTB 的大小进行了调整，减少了共享的部分，而增加了不限制分支类型的 BTB entry 数量，同时减少了一个周期的延迟，不确定这个延迟是单纯通过优化容量实现的，还是说也依赖了 previous fetch block 的方法来减少周期，更倾向于是后者，因为 L1 和 L2 BTB 都减少了一个周期的延迟。

如果按照 Intel 的 tick-tock 说法，那么 Zen 2 相比 Zen 1 是一次 tick，更换制程，微架构上做少量改动；Zen 3 相比 Zen 2 是一次 tock，不更换制程，但是在微架构上做较多改动。Zen 4 是 2022 年发布的，使用的是 5nm 制程；Zen 5 是 2024 年发布的，使用的是 4nm 制程。总结一下规律，AMD 会花费两年的时间来升级制程，并且实际上，Zen 4 和 Zen 5 不仅更新了制程，还在前端微架构上有较大的改动。

AMD Zen 3 和 ARM Neoverse V1 的 BTB 的对比

AMD Zen 3 和 ARM Neoverse V1 都是在 2020 发布的处理器，下面对它们进行一个对比：

uArch AMD Zen 3 ARM Neoverse V1
L1/Nano BTB size 1024 branches 48*2 branches
L1/Nano BTB latency 1 cycle 1 cycle
L1/Nano BTB throughput 1 branch 1-2 branches
L2/Main BTB size w/o sharing 5K branches 4K*2 branches
L2/Main BTB size w/ sharing 6.5K branches 4K*2 branches
L2/Main BTB latency 4 cycles 2 cycles
L2/Main BTB throughput 1 branch 1-2 branches
Technology Node 7nm 5nm

虽然 AMD Zen 3 通过 previous fetch block 优化，实现了 1 cycle 下更大的 L1 BTB，但这一点在 2022 年发布的 ARM Neoverse V2 上被追赶：ARM Neoverse V2 的 L1/Nano BTB 也做到了 1024 的容量。

在 L2 BTB 方面，ARM Neoverse V1 占据了领先，无论是延迟还是容量；当然了，ARM Neoverse V1 的制程也要更加领先，ARM 采用的 5nm 对比 AMD 采用的 7nm。

更进一步，ARM Neoverse V1 实现了一个周期预测两条分支，即 two taken（ARM 的说法是 two predicted branches per cycle），在 2 cycle 的 Main BTB 上可以实现接近 AMD Zen 3 的 L1 BTB 的预测吞吐。AMD 也不甘示弱，在 2022 年发布的 AMD Zen 4 处理器上，实现了 two taken。

评论