x86 bsr/bsf如何具有固定的延迟,而不是数据依赖？它不像伪代码那样循环比特吗？

Question

我正在试图分析一些x86二进制代码的"时序通道".我发布了一个问题来理解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周期来完成.

所以这是我的问题:

1. 我确认这些指令有固定的cpu周期.换句话说,无论给出什么操作数,它们总是花费相同的时间来处理,并且没有"时序通道".我在英特尔的官方文档中找不到相应的规格.

2. 那么为什么有可能呢？显然这是一个"循环"或某种程度,至少是高级别的.背后的设计决策是什么？CPU流水线更容易？

Answer 1

BSF/BSR性能不依赖于任何现代CPU的数据. 见https://agner.org/optimize/,https://uops.info/(英特尔只),或http://instlatx64.atw.hu/实验时序结果,以及所述的https:// gmplib你发现.org/~tege/x86-timing.pdf.

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

您的"8周期"(延迟和吞吐量)成本似乎是针对AMD K8上的32位BSF,来自您链接的Granlund表.Agner Fog的表格表示赞同,(并表示它解码为21 uop而不是专用的位扫描执行单元.但是微编码实现可能仍然是无分支的,而不是数据依赖的).不知道你为什么选择那个号码; K8没有SMT /超线程,因此大大减少了ALU定时侧信道的机会.

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

lzcnt/ tzcnt和popcntIntel CPU(但不是AMD)在Skylake之前和Cannon Lake之前具有相同的输出依赖性,即使在结构上,结果对所有输入都有明确的定义.它们都使用相同的执行单元.(POPCNT如何在硬件中实现？).AMD推土机/ Ryzen建立它们的比特扫描执行单元而不烘烤在输出相关,所以BSF/BSR比LZCNT/TZCNT较慢(多个微指令来处理输入= 0的情况下,大概也根据输入设定ZF,不结果).

手册中的伪代码不是实现.

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

重点是简单易懂,这意味着根据连续发生的简单双输入操作对事物进行建模. C/Fortran /典型伪代码没有多输入AND,OR或XOR的运算符,但是您可以在硬件中构建它直到某一点(受扇入限制,与扇出相反).

整数加法可以被模拟为位串行脉动进位,但仅此而已不是如何实现的!相反,我们使用诸如进位超前加法器之类的技巧获得64位加法的单周期延迟,远低于64门延迟.

在美国专利US8214414B2中描述了在英特尔的位扫描/弹出执行单元中使用的实际实现技术.

抽象

描述了PopCount和BitScan的合并数据路径.硬件电路包括用于PopCount功能的压缩器树,其由BitScan功能(例如,位扫描前向(BSF)或位扫描反向(BSR))重用.

选择器逻辑使压缩器树能够根据微处理器指令对PopCount或BitScan操作的输入字进行操作.如果选择了BitScan操作,则对输入字进行编码.

压缩器树接收输入字,对这些位进行操作,好像所有位具有相同的重要性级别(例如,对于N位输入字,输入字被视为N个一位输入).压缩器树电路的结果是二进制值,表示与所执行的操作有关的数字(PopCount的设置位数,或者通过扫描输入字遇到的第一设置位的位位置).

假设英特尔的实际芯片工作原理与此相似,这是相当安全的.其他英特尔专利,如无序机器(ROB,RS)确实倾向于与我们可以执行的性能实验相匹配.

AMD可能会做一些不同的事情,但无论我们从性能实验中得知它与数据无关.

众所周知,固定延迟对于无序调度是一个非常有益的事情,因此当指令没有固定延迟时,这是非常令人惊讶的. SandyBridge的甚至只要规范延迟,简化了调度,降低机会回写冲突(例如3个周期的延迟UOP之后是2个周期的延迟UOP到同一个端口将产生2周的结果在同一个周期)去.这意味着复杂的LEA(包含所有3个组件:) _BitScanReverse64需要3个周期,而不是像以前的CPU那样只增加2个.Sandybridge系列没有2周期延迟uops.(有一些2周期延迟指令,因为它们解码为2 uop,每个延迟1c,但调度程序调度uops,而不是指令).

ALU uops的固定延迟规则的少数例外之一是division/sqrt,它使用非完全流水线的执行单元.除了乘法之外,除法本身就是迭代的,你可以制作宽泛的硬件来并行处理部分产品和部分加法.

在Intel CPU上,如果调度程序乐观地希望数据没有准备就绪,则L1d缓存访问的可变延迟可以产生相关uop的重放.

• 当base + offset与基数不同时,是否存在惩罚？
• 为什么每次迭代的uops数量会随着流量负载的增加而增加？
• IvyBridge上指针追逐循环中附近依赖存储的奇怪性能影响.添加额外的负载会加快速度吗？