performance - x86 bsr/bsf 如何具有固定延迟，而不依赖于数据？它不是像伪代码显示的那样循环遍历位吗？

Question

我正在分析一些 x86 二进制代码的一些“时序 channel ”。我发布了一个问题来理解 bsf/bsr操作码。

所以从高层次上讲，这两个操作码可以被建模为一个“循环”，它计算给定操作数的前导零和尾随零。 x86手册对这些操作码有很好的形式化，如下所示:

IF SRC = 0
  THEN
    ZF ← 1;
    DEST is undefined;
  ELSE
    ZF ← 0;
    temp ← OperandSize – 1;
    WHILE Bit(SRC, temp) = 0
    DO
      temp ← temp - 1;
    OD;
    DEST ← temp;
FI;

但令我惊讶的是， bsf/bsr说明书好像有 固定 CPU 周期 .根据我在这里找到的一些文件: https://gmplib.org/~tege/x86-timing.pdf ，似乎它们总是需要 8 个 CPU 周期才能完成。

所以这里是我的问题:

我确认这些指令具有固定的 CPU 周期。换句话说，无论给出什么操作数，它们处理的时间总是相同的，后面没有“时序 channel ”。我在英特尔的官方文档中找不到相应的规范。

那为什么有可能呢？显然，这是一个“循环”或某种程度的，至少是高级别的。背后的设计决策是什么？ CPU管道更容易？

Answer 1

BSF/BSR 性能不是依赖于任何现代 CPU 的数据。 请参阅 https://agner.org/optimize/ 、 https://uops.info/ (仅限英特尔)或 http://instlatx64.atw.hu/ 以了解实验时序结果，以及您找到的 https://gmplib.org/~tege/x86-timing.pdf。

在现代英特尔上，它们以 3 个周期延迟和 1/时钟吞吐量解码为 1 uop，仅在端口 1 上运行。 Ryzen 也以 3c 延迟 BSF 和 4c 延迟 BSR 运行它们，但有多个 uop。早期的 AMD 有时甚至更慢。

根据您链接的 Granlund 表，您的“8 个周期”(延迟和吞吐量)成本似乎是针对 AMD K8 上的 32 位 BSF。 Agner Fog 的表同意，(并显示它解码为 21 uop，而不是具有专用的位扫描执行单元。但微编码实现大概仍然是无分支的，不依赖于数据)。不知道你为什么选择那个数字； K8 没有 SMT/超线程，因此 ALU 时序侧 channel 的机会大大减少。

请注意，它们对目标寄存器具有输出依赖性，如果输入为零，它们将保持不变。 AMD 记录了这种行为，英特尔在硬件中实现了它，但是 documents it as an "undefined" result ，所以不幸的是编译器不会利用它，人类程序员可能应该谨慎。 IDK 如果某些古老的 32 位 CPU 有不同的行为，或者英特尔计划改变(可疑!)，但我希望英特尔至少记录 64 位模式(不包括任何旧 CPU)的行为。

Intel CPU(但不是 AMD)上的 lzcnt/tzcnt 和 popcnt 在 Skylake 和 Cannon Lake 之前(分别)具有相同的输出依赖性，即使在架构上，结果对于所有输入都是明确定义的。它们都使用相同的执行单元。 ( How is POPCNT implemented in hardware? )。 AMD Bulldozer/Ryzen 构建了他们的位扫描执行单元而没有输出依赖，所以 BSF/BSR 比 LZCNT/TZCNT 慢(多个 uops 来处理 input=0 的情况，并且可能还根据输入设置 ZF，而不是结果)。

(利用内在函数是不可能的；即使使用 MSVC 的 _BitScanReverse64 也不行，它使用您可以首先设置的按引用输出 arg。MSVC 不尊重先前的值并假设它是仅输出的。 VS: unexpected optimization behavior with _BitScanReverse64 intrinsic )

手册中的伪代码不是实现

(即不一定是硬件或微码的工作方式)。

它在所有情况下都给出完全相同的结果，因此您可以使用它来准确了解文本让您想知道的任何极端情况下会发生什么。就这些。

重点是要简单易懂，这意味着根据连续发生的简单 2 输入操作对事物进行建模。 C/Fortran/典型的伪代码没有用于多输入 AND、OR 或 XOR 的运算符，但您可以在硬件中构建它( limited by fan-in ，与扇出相反)。

整数加法可以 建模为 作为位串行纹波进位，但这不是它的实现方式!相反，我们使用 carry lookahead adders 之类的技巧获得了远少于 64 个门延迟的 64 位加法的单周期延迟。

US Patent US8214414 B2 中描述了英特尔的位扫描/popcnt 执行单元中使用的实际实现技术。

Abstract

A merged datapath for PopCount and BitScan is described. A hardware circuit includes a compressor tree utilized for a PopCount function, which is reused by a BitScan function (e.g., bit scan forward (BSF) or bit scan reverse (BSR)).

Selector logic enables the compressor tree to operate on an input word for the PopCount or BitScan operation, based on a microprocessor instruction. The input word is encoded if a BitScan operation is selected.

The compressor tree receives the input word, operates on the bits as though all bits have same level of significance (e.g., for an N-bit input word, the input word is treated as N one-bit inputs). The result of the compressor tree circuit is a binary value representing a number related to the operation performed (the number of set bits for PopCount, or the bit position of the first set bit encountered by scanning the input word).

可以相当安全地假设英特尔的实际芯片与此类似。其他英特尔在乱序机器(ROB、RS)等方面的专利确实倾向于与我们可以执行的性能实验相匹配。

AMD 可能会做一些不同的事情，但不管我们从性能实验中知道它与数据无关。

众所周知，固定延迟对于乱序调度是非常有益的，所以当指令没有固定延迟时，这是非常令人惊讶的。 Sandybridge 甚至将延迟标准化以简化调度程序并减少写回冲突的机会(例如，3 周期延迟 uop 后跟 2 周期延迟 uop 到同一端口将在同一周期产生 2 个结果)。这意味着使 complex-LEA(包含所有 3 个组件: [disp + base + idx*scale] )需要 3 个周期，而不是像以前的 CPU 那样只需要 2 个周期来添加 2 个。 Sandybridge 系列上没有 2 周期延迟 uops。 (有一些 2 周期延迟指令，因为它们解码为 2 个 uops，每个延迟为 1c，但调度程序调度 uops，而不是指令)。

ALU uops 固定延迟规则的少数异常(exception)之一是除法/sqrt，它使用非完全流水线的执行单元。除法本质上是迭代的，与乘法不同，乘法可以制作并行执行部分乘积和部分加法的宽硬件。

在 Intel CPU 上，如果数据未准备好而调度程序乐观地希望它准备好，则 L1d 缓存访问的可变延迟可以产生依赖 uops 的重播。

Is there a penalty when base+offset is in a different page than the base?

Why does the number of uops per iteration increase with the stride of streaming loads?

Weird performance effects from nearby dependent stores in a pointer-chasing loop on IvyBridge. Adding an extra load speeds it up?