我正在分析一些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周期，也就是说，不管给什么操作数，处理的时间总是一样的，背后没有“时序通道”，我在英特尔的官方文件中找不到相应的规范。
1.那么为什么这是可能的呢？显然这是一个“循环”，或者说，至少是高水平的。背后的设计决策是什么？更容易的CPU流水线？
3条答案
按热度按时间fzwojiic1#
**BSF/BSR性能不依赖于任何现代CPU的数据。**请参阅https://agner.org/optimize/、https://uops.info/或http://instlatx64.atw.hu/以了解实验时序结果，以及您找到的https://gmplib.org/~tege/x86-timing.pdf。
在现代的Intel上，它们解码为1个微操作，3个周期的延迟和1/时钟的吞吐量，只在端口1上运行。Ryzen也运行它们，BSF的延迟为3c，BSR的延迟为4c，但多个微操作。早期的AMD有时甚至更慢。
（如果您不需要
bsf和tzcnt之间的FLAGS差异来实现零输入，则在可能运行于AMD CPU上的代码中首选rep bsf（又名tzcnt）。lzcnt和tzcnt在AMD上也很快，例如Zen 2（https://uops.info/）上lzcnt的1个周期延迟和3个/时钟的吞吐量。不幸的是lzcnt和bsr在这种方式下不兼容，因此您不能以“乐观”向前兼容的方式使用它，你必须知道你得到的是什么。）你的“8周期”（延迟 * 和 * 吞吐量）成本似乎是AMD K8上的32位BSF，来自你链接的Granlund的表。Agner Fog的表同意，（并显示它解码到21微操作，而不是有一个专用的位扫描执行单元。但微代码的实现可能仍然是无分支的，不依赖于数据）。不知道你为什么选择 * 这个 * 数字; K8没有SMT /超线程，因此ALU定时侧通道的机会大大减少。
**请注意，它们对目标寄存器具有输出依赖性，如果输入为零，则不修改目标寄存器。**AMD记录了这种行为，英特尔在硬件中实现了这种行为，但documents it as an "undefined" result，因此不幸的是，编译器不会利用它，人类程序员可能应该谨慎。IDK如果一些古老的32位CPU具有不同的行为，或者英特尔是否计划改变（值得怀疑！），但我希望英特尔至少为64位模式（不包括任何旧的CPU）记录行为。
英特尔CPU上的
lzcnt/tzcnt和popcnt（AMD除外）在Skylake和Cannon Lake之前具有相同的输出依赖性（分别），即使在体系结构上，所有输入的结果都定义良好。它们都使用相同的执行单元。（How is POPCNT implemented in hardware?）。AMD Bulldozer/Ryzen构建其位扫描执行单元时没有内置输出相关性，因此BSF/BSR比LZCNT/TZCNT慢（多个微操作处理input=0的情况，并且可能还根据输入而不是结果设置ZF）。（对内部函数利用这一点是不可能的;即使使用MSVC的
_BitScanReverse64也不行，它使用了一个可以首先设置的引用输出参数。MSVC不考虑以前的值，并假定它是仅输出的。VS：使用_BitScanReverse64内在函数时出现意外优化行为）手册中的伪代码不是实现
(i.e.不一定是硬件或 * 微码 * 的工作方式）。
它在所有情况下都给出了完全相同的结果，因此你可以用它来确切地理解文本中让你感到困惑的任何角落情况会发生什么，这就是 all。
**关键是要简单易懂，这意味着要按照串行发生的简单2输入操作来建模。**C / Fortran / typical伪代码没有用于多输入AND、OR或XOR的运算符，但您可以在硬件中将其构建到某个点（limited by fan-in，与扇出相反）。
整数加法 * 可以建模为位串行涟漪进位，但这不是它的实现方式！相反，我们使用carry lookahead adders等技巧获得了64位加法的单周期延迟，远低于64个门延迟。
US Patent US8214414 B2中介绍了英特尔bit-scan / popcnt执行单元中使用的实际实施技术。
摘要
描述了一种用于PopCount和BitScan的合并数据路径。硬件电路包括用于PopCount函数的压缩器树，其被BitScan函数（例如，位扫描前向（BSF）或位扫描反向（BSR））重用。
选择器逻辑根据微处理器指令使压缩器树能对PopCount或BitScan操作的输入字进行操作。如果选择了BitScan操作，则对输入字进行编码。
压缩器树接收输入字，对比特进行操作，就好像所有比特具有相同的有效性级别（例如，对于N位输入字，输入字被视为N个1位输入）。压缩器树电路的结果是二进制值，其表示与所执行的操作相关的数（PopCount的设置位数，或扫描输入字时遇到的第一个设置位的位位置）。
我们可以很有把握地认为，英特尔的实际芯片工作原理与此类似。英特尔的其他专利，如无序机器（ROB，RS），确实倾向于与我们可以进行的性能实验相匹配。
AMD可能会做一些不同的事情，但无论如何，我们从性能实验中知道，它不依赖于数据。
**众所周知，固定延迟对于无序调度来说是一件 * 非常 * 有益的事情，因此，当指令 * 不 * 具有固定延迟时，这是非常令人惊讶的。**Sandybridge甚至将延迟标准化，以简化调度程序并减少写回冲突的机会（例如，一个3周期延迟uop，随后是一个2周期延迟uop，发往同一端口，将在同一周期内产生2个结果）。这意味着使复杂LEA（具有所有3个组件：
[disp + base + idx*scale]）需要3个周期，而不是像以前的CPU那样，2次加法只需要2个周期。Sandybridge-family上没有2个周期延迟的微操作。（有一些2个周期延迟的指令，因为它们解码为2个微操作，每个微操作的延迟为1c，但调度程序调度微操作，而不是指令）。ALU微操作的固定延迟规则的少数例外之一是除法/ sqrt，它使用的是一个非完全流水线化的执行单元。除法本身是迭代的，不像乘法，你可以用宽硬件来并行执行部分积和部分加。
在英特尔CPU上，如果数据未在调度程序乐观预期的时间准备就绪，则L1 d缓存访问的可变延迟可能会产生相关微操作的重放。
ff29svar2#
80 x86手册很好地描述了预期行为，但这与它在任何制造商的任何型号的芯片中的实际实现方式无关。
假设英特尔有50种不同的CPU设计，AMD有25种，其他制造商还有25种（VIA、Cyrix、SiS/Vortex、NSC......）。在这100种不同的CPU设计中，可能有20种完全不同的
BSF实现方式，其中可能有10种具有固定的时序，5具有取决于源操作数的每一位的时序，且5取决于源操作数的位群组（例如，可能类似于“如果64位操作数的最高32位为零{切换到32位逻辑，其快2个循环}”）。我正在确认这些指令都有固定的cpu周期，也就是说，不管给什么操作数，处理的时间总是一样的，背后没有“时序通道”，我在英特尔的官方文件中找不到相应的规范。
你不能。更具体地说，你可以测试或研究现有的CPU，但这是浪费时间，因为下周英特尔（或AMD或VIA或其他人）可以发布一个新的CPU，有完全不同的时序。
**一旦您依赖“从现有CPU测量”，您就做错了。**您必须依赖适用于所有未来CPU的“体系结构保证”。没有“体系结构保证”。您必须假设可能存在计时侧通道（即使当前CPU没有）
那么为什么这是可能的呢？显然这是一个“循环”，或者说，至少是高水平的。背后的设计决策是什么？更容易的CPU流水线？
为什么不把它分成一对32位的片段，然后并行处理，然后合并结果？为什么不把它分成8个8位的片段？为什么不对每个8位片段使用表查找？
mqkwyuun3#
上面的答案已经很好地解释了这种实现与伪代码的不同。但是如果你仍然好奇为什么延迟是固定的，而不依赖于数据，或者使用任何循环，那么你需要看看电子方面的东西。你可以在硬件中实现这种特性的一种方法是使用Priority encoder。
一个优先级编码器将接受n个输入行，可以是1或off（0或1），并给予最高优先级行的索引。下面是一个表格，从链接的维基百科文章修改为一个最高有效位设置函数。
x表示位值无关紧要，可以是任何值
如果你看到文章上的电路图，没有任何形式的回路，它都是平行的。