确切地说，x86 微指令是如何安排的？
How are x86 uops scheduled, exactly?
现代 x86 CPU 将传入的指令流分解为微操作 (uops1)，然后在输入准备就绪时安排这些 uops out-of-order。虽然基本思路很清楚，但我想知道 如何 安排就绪指令的具体细节，因为它会影响微优化决策。
例如拿下面的玩具循环2:
top:
lea eax, [ecx + 5]
popcnt eax, eax
add edi, eax
dec ecx
jnz top
这样基本实现了循环（对应关系如下：eax -> total, c -> ecx）：
do {
total += popcnt(c + 5);
} while (--c > 0);
我通过查看 uop 故障、依赖链延迟等来熟悉优化任何小循环的过程。在上面的循环中，我们只有一个携带的依赖链：dec ecx。循环的前三个指令（lea、popcnt、add）是每个循环重新开始的依赖链的一部分。
最后的dec和jne融合了。所以我们总共有 4 个融合域 uops，和一个只有循环携带的依赖链，延迟为 1 个周期。因此，根据该标准，循环似乎可以在 1 cycle/iteration.
处执行
但是，我们也应该看看端口压力：
lea可以在端口1和5上执行- popcnt 可以在端口 1 上执行
add可以在0、1、5、6端口执行- predicted-taken
jnz 在端口 6 上执行
因此，要达到 1 个循环/迭代，您非常需要发生以下情况：
- popcnt 必须 在端口 1 上执行（它可以执行的唯一端口）
lea必须在端口 5 上执行（绝不能在端口 1 上执行）-
add 必须 在端口 0 上执行，并且绝不能在它可以在 上执行的其他三个端口中的任何一个上执行
- 无论如何
jnz只能在端口6上执行
条件真多！如果指令只是随机安排，您可能会得到更糟糕的吞吐量。例如，add 的 75% 会转到端口 1、5 或 6，这会使 popcnt、lea 或 jnz 延迟一个周期。同样，对于可以连接到 2 个端口的 lea，一个与 popcnt.
共享
另一方面，IACA 报告的结果非常接近最佳，每次迭代 1.05 个周期：
Intel(R) Architecture Code Analyzer Version - 2.1
Analyzed File - l.o
Binary Format - 64Bit
Architecture - HSW
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 1.05 Cycles Throughput Bottleneck: FrontEnd, Port0, Port1, Port5
Port Binding In Cycles Per Iteration:
---------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
---------------------------------------------------------------------------------------
| Cycles | 1.0 0.0 | 1.0 | 0.0 0.0 | 0.0 0.0 | 0.0 | 1.0 | 0.9 | 0.0 |
---------------------------------------------------------------------------------------
N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion happened
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256 instruction, dozens of cycles penalty is expected
! - instruction not supported, was not accounted in Analysis
| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | |
---------------------------------------------------------------------------------
| 1 | | | | | | 1.0 | | | CP | lea eax, ptr [ecx+0x5]
| 1 | | 1.0 | | | | | | | CP | popcnt eax, eax
| 1 | 0.1 | | | | | 0.1 | 0.9 | | CP | add edi, eax
| 1 | 0.9 | | | | | | 0.1 | | CP | dec ecx
| 0F | | | | | | | | | | jnz 0xfffffffffffffff4
它几乎反映了我上面提到的必要的“理想”调度，但有一个小偏差：它显示 add 在 10 个周期中有 1 个从 lea 窃取端口 5。它也不知道融合分支将去往端口 6，因为它被预测为被占用，所以它将分支的大部分微指令放在端口 0 上，add 的大部分微指令放在端口 6，而不是相反。
目前尚不清楚 IACA 报告的超过最优值的额外 0.05 个循环是深度、准确分析的结果，还是它使用的算法的洞察力较差的结果，例如，分析固定数量的循环循环，或者只是一个错误或其他什么。它认为将去往非理想端口的 uop 的 0.1 部分也是如此。也不清楚一个解释另一个 - 我认为错误分配端口 10 次中的 1 次会导致每次迭代的循环计数为 11/10 = 1.1 个循环，但我还没有计算出实际的下游结果 - 平均而言，影响可能较小。或者它可能只是四舍五入（0.05 == 0.1 到小数点后一位）。
那么现代 x86 CPU 实际上是如何调度的呢？特别是：
- 当多个微指令在保留站就绪时，它们按什么顺序调度到端口？
- 当一个 uop 可以到达多个端口时（如上例中的
add 和 lea），如何决定选择哪个端口？
- 如果任何答案涉及oldest 之类的概念来选择微指令，它是如何定义的？自从它交付给 RS 以来的年龄？准备就绪后的年龄？关系是怎么断的？程序顺序是否涉及其中？
Skylake 上的结果
让我们在 Skylake 上测量一些实际结果，以检查哪些答案解释了实验证据，所以这里是我的 Skylake 盒子上的一些真实世界测量结果（来自 perf）。令人困惑的是，我将切换到使用 imul 来执行我的“仅在一个端口上执行”指令，因为它有许多变体，包括允许您为源使用不同寄存器的 3 参数版本和目的地。这在尝试构建依赖链时非常方便。它还避免了 popcnt 所具有的整个“对目的地的错误依赖”。
独立指令
让我们先看看指令相对独立的简单 (?) 情况——除了循环计数器等微不足道的链之外没有任何依赖链。
这是一个 4 微指令循环（仅执行 3 微指令），压力适中。所有指令都是独立的（不共享任何来源或目的地）。 add 原则上可以窃取 imul 所需的 p1 或 dec:
所需的 p6
示例 1
instr p0 p1 p5 p6
xor (elim)
imul X
add X X X X
dec X
top:
xor r9, r9
add r8, rdx
imul rax, rbx, 5
dec esi
jnz top
The results is that this executes with perfect scheduling at 1.00 cycles / iteration:
560,709,974 uops_dispatched_port_port_0 ( +- 0.38% )
1,000,026,608 uops_dispatched_port_port_1 ( +- 0.00% )
439,324,609 uops_dispatched_port_port_5 ( +- 0.49% )
1,000,041,224 uops_dispatched_port_port_6 ( +- 0.00% )
5,000,000,110 instructions:u # 5.00 insns per cycle ( +- 0.00% )
1,000,281,902 cycles:u
( +- 0.00% )
正如预期的那样，p1 和 p6 分别被 imul 和 dec/jnz 充分利用，然后是 add 问题 大约 剩余可用端口之间的一半。注意 大致 - 实际比率是 56% 和 44%，并且这个比率在运行中非常稳定（注意 +- 0.49% 变化）。如果我调整循环对齐，拆分会发生变化（32B 对齐为 53/46，更像是 32B+4 对齐为 57/42）。现在，我们只改变 imul 在循环中的位置：
示例 2
top:
imul rax, rbx, 5
xor r9, r9
add r8, rdx
dec esi
jnz top
然后 p0/p5 拆分正好是 50%/50%，变化为 0.00%：
500,025,758 uops_dispatched_port_port_0 ( +- 0.00% )
1,000,044,901 uops_dispatched_port_port_1 ( +- 0.00% )
500,038,070 uops_dispatched_port_port_5 ( +- 0.00% )
1,000,066,733 uops_dispatched_port_port_6 ( +- 0.00% )
5,000,000,439 instructions:u # 5.00 insns per cycle ( +- 0.00% )
1,000,439,396 cycles:u ( +- 0.01% )
所以这已经很有趣了，但是很难说清楚发生了什么。也许确切的行为取决于循环入口处的初始条件并且对循环内的顺序敏感（例如，因为使用了计数器）。这个例子表明，除了“随机”或“愚蠢”的调度之外，还有一些事情正在发生。特别是，如果您只是从循环中删除 imul 指令，您会得到以下内容：
示例 3
330,214,329 uops_dispatched_port_port_0 ( +- 0.40% )
314,012,342 uops_dispatched_port_port_1 ( +- 1.77% )
355,817,739 uops_dispatched_port_port_5 ( +- 1.21% )
1,000,034,653 uops_dispatched_port_port_6 ( +- 0.00% )
4,000,000,160 instructions:u # 4.00 insns per cycle ( +- 0.00% )
1,000,235,522 cycles:u ( +- 0.00% )
在这里，add 现在大致平均分布在 p0、p1 和 p5 之间 - 所以 imul 的存在确实影响了add 调度：这不仅仅是某些“避免端口 1”规则的结果。
注意这里总的端口压力只有 3 uops/cycle，因为 xor 是一个调零惯用语，在重命名器中被删除了。让我们尝试使用 4 微秒的最大压力。我希望上面启动的任何机制也能够完美地安排它。我们只是把xor r9, r9改成了xor r9, r10，所以它不再是归零的成语了。我们得到以下结果：
示例 4
top:
xor r9, r10
add r8, rdx
imul rax, rbx, 5
dec esi
jnz top
488,245,238 uops_dispatched_port_port_0 ( +- 0.50% )
1,241,118,197 uops_dispatched_port_port_1 ( +- 0.03% )
1,027,345,180 uops_dispatched_port_port_5 ( +- 0.28% )
1,243,743,312 uops_dispatched_port_port_6 ( +- 0.04% )
5,000,000,711 instructions:u # 2.66 insns per cycle ( +- 0.00% )
1,880,606,080 cycles:u ( +- 0.08% )
糟糕！调度程序没有在 p0156 之间均匀地调度所有内容，而是未充分利用 p0（它只执行了约 49% 的周期），因此 p1 和 p6 被超额订阅，因为它们正在执行 imul 和 dec/jnz 的 必需的 操作。这种行为，我认为与 hayesti 在他们的回答中指出的 counter-based 压力指标一致，并且 uops 在发布时被分配给端口，而不是在执行时 作为两者
hayesti 和 Peter Cordes 提到。这种行为3 使得 执行最早的就绪uops 规则几乎没有那么有效。如果 uops 没有绑定到有问题的执行端口，而是在执行时，那么这个“最旧的”规则将在一次迭代后解决上面的问题——一旦一个 imul 和一个 dec/jnz 被阻止了在一次迭代中，它们总是比竞争的 xor 和 add 指令要早，所以应该总是先安排。不过，我正在学习的一件事是，如果端口是在发布时分配的，则此规则无济于事，因为端口是在发布时预先确定的。我想它仍然有助于支持作为长依赖链一部分的指令（因为它们往往会落后），但这并不是我认为的万能药。
这似乎也解释了上面的结果：p0 被赋予了比实际更大的压力，因为 dec/jnz 组合可以 理论上 在 p06 上执行。 事实上因为预测分支只会到达p6，但也许该信息无法输入压力平衡算法，所以计数器往往看起来相等p016 上的压力，意味着 add 和 xor 的分布与最佳分布不同。
也许我们可以通过稍微展开循环来测试这一点，这样 jnz 就不是一个因素...
1 好的，它写得正确 μops，但这会破坏搜索能力并实际键入“μ”字符 I我通常求助于从网页上复制粘贴字符。
2 我最初在循环中使用 imul 而不是 popcnt，但是令人难以置信的是，_IACA 没有 support it_！
3 请注意，我并不是在暗示这是一个糟糕的设计或其他任何东西 - 可能有非常好的硬件原因导致调度程序无法在执行时轻松做出所有决定时间。
你的问题很棘手，原因如下：
- 答案在很大程度上取决于处理器的微体系结构
代与代之间可能会有很大差异。
- 这些是英特尔通常不会向 public 发布的精细细节。
不过，我会尽力回答...
当多个微指令在保留站就绪时，它们按什么顺序调度到端口？
它应该是最老的 [见下文]，但您的里程可能会有所不同。 P6 微架构（用于 Pentium Pro，2 和 3）使用一个带有五个调度程序的保留站（每个执行端口一个）；调度程序使用优先级指针作为开始扫描准备好要调度的 uops 的地方。它只是伪 FIFO，所以最老的就绪指令完全有可能并不总是被调度。在 NetBurst 微架构（在 Pentium 4 中使用）中，他们放弃了统一的保留站，而是使用两个 uop 队列。这些是适当的折叠优先级队列，因此调度程序可以保证获得最旧的就绪指令。核心架构返回到保留站，我会冒险猜测他们使用了折叠优先级队列，但我找不到来源来证实这一点。如果有人有明确的答案，我会洗耳恭听。
当一个 uop 可以去多个端口时（如上例中的 add 和 lea），如何决定选择哪个端口？
这很难知道。我能找到的最好的是来自 Intel 的 a patent 描述了这种机制。本质上，他们为每个具有冗余功能单元的端口保留一个计数器。当 uops 离开前端到保留站时，它们会被分配一个调度端口。如果必须在多个冗余执行单元之间做出决定，则使用计数器来平均分配工作。当 uops 分别进入和离开保留站时，计数器递增和递减。
当然，这只是一种启发式方法，并不能保证完美无冲突的时间表，但是，我仍然可以看到它与您的玩具示例一起使用。只能去一个端口的指令最终会影响调度程序将 "less restricted" 微指令分派到其他端口。
无论如何，专利的存在并不一定意味着这个想法被采纳了（尽管如此，其中一位作者也是奔腾 4 的技术负责人，所以谁知道呢？）
如果任何一个答案都涉及到在微指令中选择最早的概念，它是如何定义的？自从它交付给 RS 以来的年龄？准备就绪后的年龄？关系是怎么断的？有程序顺序吗？
由于uops是按顺序插入保留站的，所以这里的oldest确实是指进入保留站的时间，即程序顺序最旧
顺便说一下，我会对那些 IACA 结果持保留态度，因为它们可能无法反映真实硬件的细微差别。在 Haswell 上，有一个名为 uops_executed_port 的硬件计数器，它可以告诉您线程中有多少个周期是端口 0-7 的 uops 问题。也许您可以利用这些来更好地了解您的程序？
这是我在 Skylake 上发现的，从 uops 在发布时间（即当它们被发布到 RS）而不是在调度时间（即，此刻他们被送去执行）。之前我明白港口决定是在发货时做出的。
我做了各种测试，试图隔离可以转到 p0156 的 add 操作序列和仅转到端口 0 的 imul 操作序列。典型的测试是像这样：
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
... many more mov instructions
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
imul ebx, ebx, 1
imul ebx, ebx, 1
imul ebx, ebx, 1
imul ebx, ebx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
... many more mov instructions
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
基本上有一个很长的 mov eax, [edi] 指令导入，它只在 p23 上发出，因此不会阻塞指令使用的端口（我也可以使用 nop 指令，但测试会有点不同，因为 nop 不向 RS 发出）。接下来是 "payload" 部分，这里由 4 个 imul 和 12 个 add 组成，然后是更多虚拟 mov 指令的引出部分。
首先，让我们看一下上面链接的 the patent，他描述了基本思想：每个端口的计数器跟踪分配给端口的微指令总数，这些微指令用于负载平衡端口分配。看看专利说明中包含的这个table：
此 table 用于在 p0 或 p1 之间为专利中讨论的 3-wide 架构的问题组中的 3-uops 选择。请注意，该行为取决于 uop 在组中的位置 ，并且有 4 个规则 1 基于计数，它们传播以合乎逻辑的方式进行。特别是，在为整个组分配未充分使用的端口之前，计数需要达到 +/- 2 或更大。
让我们看看是否可以观察 Sklake 上的 "position in issue group" 事项行为。我们使用单个 add 的有效载荷，例如：
add edx, 1 ; position 0
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
... 然后我们在 4 指令卡盘内滑动它，如：
mov eax, [edi]
add edx, 1 ; position 1
mov eax, [edi]
mov eax, [edi]
...等等，测试问题组2中的所有四个位置。这显示了以下内容，当 RS 已满（mov 指令）但没有任何相关端口的端口压力时：
- 第一个
add 指令转到 p5 或 p6，选择的端口通常随着指令变慢而交替（即，add 指令在偶数位置转到 p5，奇数位置转到 p6)。
- 第二个
add 指令也转到 p56 - 以第一个没有转到的两个指令为准。
- 在那之后，进一步的
add 指令开始围绕 p0156 进行平衡，p5 和 p6 通常领先，但总体上相当均匀（即差距p56 和其他两个端口之间没有增长）。
接下来，我查看了如果使用 imul 操作加载 p1 会发生什么，然后首先是一堆 add 操作：
imul ebx, ebx, 1
imul ebx, ebx, 1
imul ebx, ebx, 1
imul ebx, ebx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
结果表明调度程序处理得很好 - 所有 imul 都被调度到 p1（如预期的那样），然后 none 随后的 [=18] =] 指令去了 p1，而是散布在 p056 周围。所以这里的调度运行良好。
当然，当情况相反时，imul 系列出现在 add 之后，p1 会在 [= 之前加载它的添加份额20=]s 命中。这是端口分配在发布时按顺序发生的结果，因为在调度 add 时没有 "look ahead" 和查看 imul 的机制。
总的来说，调度程序看起来在这些测试用例中做得很好。
它没有解释在像下面这样更小、更紧密的循环中会发生什么：
sub r9, 1
sub r10, 1
imul ebx, edx, 1
dec ecx
jnz top
就像我的问题中的 示例 4 一样，尽管有两个 sub 指令应该能够在 每个 周期进入 p0。 p1 和 p6 超额订阅，每个迭代执行 1.24 微指令（1 是理想的）。我无法对这个答案顶部运行良好的示例与错误循环之间的差异进行三角测量 - 但仍有很多想法可以尝试。
我注意到没有说明的示例 延迟差异 似乎没有遇到这个问题。例如，这是另一个具有 "complex" 端口压力的 4-uop 循环：
top:
sub r8, 1
ror r11, 2
bswap eax
dec ecx
jnz top
uop图如下：
instr p0 p1 p5 p6
sub X X X X
ror X X
bswap X X
dec/jnz X
因此 sub 必须始终转到 p15，如果事情要解决，则与 bswap 共享。他们这样做：
“./sched-test2”的性能计数器统计数据（2 次运行）：
999,709,142 uops_dispatched_port_port_0 ( +- 0.00% )
999,675,324 uops_dispatched_port_port_1 ( +- 0.00% )
999,772,564 uops_dispatched_port_port_5 ( +- 0.00% )
1,000,991,020 uops_dispatched_port_port_6 ( +- 0.00% )
4,000,238,468 uops_issued_any ( +- 0.00% )
5,000,000,117 instructions:u # 4.99 insns per cycle ( +- 0.00% )
1,001,268,722 cycles:u ( +- 0.00% )
所以问题可能与指令延迟有关（当然，示例之间还有其他差异）。这是 this similar question 中出现的内容。
1table有5条规则，但是0和-1计数的规则是一样的。
2当然，我不能确定问题组的开始和结束位置，但无论如何我们测试四个不同的位置当我们向下滑动四个指令时（但标签可能是错误的）。我也不确定 确定 问题组的最大大小是 4 - 管道的早期部分更宽 - 但我相信它是并且一些测试似乎表明它是（循环与多个4 微指令显示一致的调度行为）。无论如何，结论适用于不同的调度组大小。
最近英特尔微体系结构上基本块的准确吞吐量预测[^1] 的第 2.12 节解释了如何分配端口，但它未能解释问题描述中的示例 4。我也没有弄清楚延迟在端口分配中扮演什么角色。
Previous work [19, 25, 26] has identified the ports that the µops of individual instructions can use. For µops that can use more than one port, it was, however, previously unknown how the actual port is chosen by the processor. We reverse-engineered the port assignment algorithm using microbenchmarks. In the following, we describe our findings for CPUs with eight ports; such CPUs are currently most widely used.
The ports are assigned when the µops are issued by the renamer to the scheduler. In a single cycle, up to four µops can be issued. In the following, we will call the position of a µop within a cycle an issue slot; e.g., the oldest instruction issued in a cycle would occupy issue slot 0.
The port that a µop is assigned depends on its issue slot and on the ports assigned to µops that have not been executed and were issued in a previous cycle.
In the following, we will only consider µops that can use more than one port. For a given µop m, let $P_{min}$ be the port to which the fewest non-executed µops have been assigned to from among the ports that m can use. Let $P_{min'}$ be the port with the second smallest usage so far. If there is a tie among the ports with the smallest (or second smallest, respectively) usage, let $P_{min}$ (or $P_{min'}$) be the port with the highest port number from among these ports (the reason for this choice is probably that ports with higher numbers are connected to fewer functional units). If the difference between $P_{min}$ and $P_{min'}$ is greater or equal to 3, we set $P_{min'}$ to $P_{min}$.
The µops in issue slots 0 and 2 are assigned to port $P_{min}$ The µops in issue slots 1 and 3 are assigned to port $P_{min'}$.
A special case is µops that can use port 2 and port 3. These ports are used by µops that handle memory accesses, and both ports are connected to the same types of functional units. For such µops, the port assignment algorithm alternates between port 2 and port 3.
我试图找出$P_{min}$和$P_{min'}$是否在线程之间共享（Hyper-Threading），即一个线程是否可以影响端口在同一个核心中分配另一个。
只需将 BeeOnRope 的答案中使用的代码分成两个线程即可。
thread1:
.loop:
imul rax, rbx, 5
jmp .loop
thread2:
mov esi,1000000000
.top:
bswap eax
dec esi
jnz .top
jmp thread2
其中指令 bswap 可以在端口 1 和 5 上执行，imul r64, R64, i 可以在端口 1 上执行。如果线程之间共享计数器，您会看到 bswap 在端口 5 上执行imul 在端口 1 上执行。
实验记录如下，其中线程1的端口P0和P5，线程2的p0应该记录了少量的non-user数据，但不影响结论。从数据可以看出，线程2的bswap指令是在P1和P5口交替执行的，并没有放弃P1
port
thread 1 active cycles
thread 2 active cycles
P0
63,088,967
68,022,708
P1
180,219,013,832
95,742,764,738
P5
63,994,200
96,291,124,547
P6
180,330,835,515
192,048,880,421
total
180,998,504,099
192,774,759,297
因此，线程之间不共享计数器。
这个结论与SMotherSpectre[^2]不冲突，SMotherSpectre[^2]使用时间作为边信道。 （例如，线程 2 在端口 1 上等待更长时间才能使用端口 1。）
Executing instructions that occupy a specific port and measuring their timing enables inference about other instructions executing on the same port. We first choose two instructions, each scheduled on a single, distinct, execution port. One thread runs and times a long sequence of single µop instructions scheduled on port a, while simultaneously the other thread runs a long sequence of instructions scheduled on port b. We expect that, if a = b, contention occurs and the measured execution time is longer compared to the a ≠ b case.
[^1]：Abel、Andreas 和 Jan Reineke。 “最新英特尔微体系结构上基本块的准确吞吐量预测。” arXiv 预印本 arXiv:2107.14210 (2021).
[^2]：Bhattacharyya、Atri、Alexandra Sandulescu、Matthias Neugschwandtner、Alessandro Sorniotti、Babak Falsafi、Mathias Payer 和 Anil Kurmus。 “SMoTherSpectre：通过端口争用利用推测执行。” 2019 年 ACM SIGSAC 计算机和通信安全会议论文集，2019 年 11 月 6 日，785-800。 https://doi.org/10.1145/3319535.3363194.
现代 x86 CPU 将传入的指令流分解为微操作 (uops1)，然后在输入准备就绪时安排这些 uops out-of-order。虽然基本思路很清楚，但我想知道 如何 安排就绪指令的具体细节，因为它会影响微优化决策。
例如拿下面的玩具循环2:
top:
lea eax, [ecx + 5]
popcnt eax, eax
add edi, eax
dec ecx
jnz top
这样基本实现了循环（对应关系如下：eax -> total, c -> ecx）：
do {
total += popcnt(c + 5);
} while (--c > 0);
我通过查看 uop 故障、依赖链延迟等来熟悉优化任何小循环的过程。在上面的循环中，我们只有一个携带的依赖链：dec ecx。循环的前三个指令（lea、popcnt、add）是每个循环重新开始的依赖链的一部分。
最后的dec和jne融合了。所以我们总共有 4 个融合域 uops，和一个只有循环携带的依赖链，延迟为 1 个周期。因此，根据该标准，循环似乎可以在 1 cycle/iteration.
但是，我们也应该看看端口压力：
lea可以在端口1和5上执行- popcnt 可以在端口 1 上执行
add可以在0、1、5、6端口执行- predicted-taken
jnz在端口 6 上执行
因此，要达到 1 个循环/迭代，您非常需要发生以下情况：
- popcnt 必须 在端口 1 上执行（它可以执行的唯一端口）
lea必须在端口 5 上执行（绝不能在端口 1 上执行）-
add必须 在端口 0 上执行，并且绝不能在它可以在 上执行的其他三个端口中的任何一个上执行
- 无论如何
jnz只能在端口6上执行
条件真多！如果指令只是随机安排，您可能会得到更糟糕的吞吐量。例如，add 的 75% 会转到端口 1、5 或 6，这会使 popcnt、lea 或 jnz 延迟一个周期。同样，对于可以连接到 2 个端口的 lea，一个与 popcnt.
另一方面，IACA 报告的结果非常接近最佳，每次迭代 1.05 个周期：
Intel(R) Architecture Code Analyzer Version - 2.1
Analyzed File - l.o
Binary Format - 64Bit
Architecture - HSW
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 1.05 Cycles Throughput Bottleneck: FrontEnd, Port0, Port1, Port5
Port Binding In Cycles Per Iteration:
---------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
---------------------------------------------------------------------------------------
| Cycles | 1.0 0.0 | 1.0 | 0.0 0.0 | 0.0 0.0 | 0.0 | 1.0 | 0.9 | 0.0 |
---------------------------------------------------------------------------------------
N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion happened
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256 instruction, dozens of cycles penalty is expected
! - instruction not supported, was not accounted in Analysis
| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | |
---------------------------------------------------------------------------------
| 1 | | | | | | 1.0 | | | CP | lea eax, ptr [ecx+0x5]
| 1 | | 1.0 | | | | | | | CP | popcnt eax, eax
| 1 | 0.1 | | | | | 0.1 | 0.9 | | CP | add edi, eax
| 1 | 0.9 | | | | | | 0.1 | | CP | dec ecx
| 0F | | | | | | | | | | jnz 0xfffffffffffffff4
它几乎反映了我上面提到的必要的“理想”调度，但有一个小偏差：它显示 add 在 10 个周期中有 1 个从 lea 窃取端口 5。它也不知道融合分支将去往端口 6，因为它被预测为被占用，所以它将分支的大部分微指令放在端口 0 上，add 的大部分微指令放在端口 6，而不是相反。
目前尚不清楚 IACA 报告的超过最优值的额外 0.05 个循环是深度、准确分析的结果，还是它使用的算法的洞察力较差的结果，例如，分析固定数量的循环循环，或者只是一个错误或其他什么。它认为将去往非理想端口的 uop 的 0.1 部分也是如此。也不清楚一个解释另一个 - 我认为错误分配端口 10 次中的 1 次会导致每次迭代的循环计数为 11/10 = 1.1 个循环，但我还没有计算出实际的下游结果 - 平均而言，影响可能较小。或者它可能只是四舍五入（0.05 == 0.1 到小数点后一位）。
那么现代 x86 CPU 实际上是如何调度的呢？特别是：
- 当多个微指令在保留站就绪时，它们按什么顺序调度到端口？
- 当一个 uop 可以到达多个端口时（如上例中的
add和lea），如何决定选择哪个端口？ - 如果任何答案涉及oldest 之类的概念来选择微指令，它是如何定义的？自从它交付给 RS 以来的年龄？准备就绪后的年龄？关系是怎么断的？程序顺序是否涉及其中？
Skylake 上的结果
让我们在 Skylake 上测量一些实际结果，以检查哪些答案解释了实验证据，所以这里是我的 Skylake 盒子上的一些真实世界测量结果（来自 perf）。令人困惑的是，我将切换到使用 imul 来执行我的“仅在一个端口上执行”指令，因为它有许多变体，包括允许您为源使用不同寄存器的 3 参数版本和目的地。这在尝试构建依赖链时非常方便。它还避免了 popcnt 所具有的整个“对目的地的错误依赖”。
独立指令
让我们先看看指令相对独立的简单 (?) 情况——除了循环计数器等微不足道的链之外没有任何依赖链。
这是一个 4 微指令循环（仅执行 3 微指令），压力适中。所有指令都是独立的（不共享任何来源或目的地）。 add 原则上可以窃取 imul 所需的 p1 或 dec:
p6
示例 1
instr p0 p1 p5 p6
xor (elim)
imul X
add X X X X
dec X
top:
xor r9, r9
add r8, rdx
imul rax, rbx, 5
dec esi
jnz top
The results is that this executes with perfect scheduling at 1.00 cycles / iteration:
560,709,974 uops_dispatched_port_port_0 ( +- 0.38% )
1,000,026,608 uops_dispatched_port_port_1 ( +- 0.00% )
439,324,609 uops_dispatched_port_port_5 ( +- 0.49% )
1,000,041,224 uops_dispatched_port_port_6 ( +- 0.00% )
5,000,000,110 instructions:u # 5.00 insns per cycle ( +- 0.00% )
1,000,281,902 cycles:u
( +- 0.00% )
正如预期的那样，p1 和 p6 分别被 imul 和 dec/jnz 充分利用，然后是 add 问题 大约 剩余可用端口之间的一半。注意 大致 - 实际比率是 56% 和 44%，并且这个比率在运行中非常稳定（注意 +- 0.49% 变化）。如果我调整循环对齐，拆分会发生变化（32B 对齐为 53/46，更像是 32B+4 对齐为 57/42）。现在，我们只改变 imul 在循环中的位置：
示例 2
top:
imul rax, rbx, 5
xor r9, r9
add r8, rdx
dec esi
jnz top
然后 p0/p5 拆分正好是 50%/50%，变化为 0.00%：
500,025,758 uops_dispatched_port_port_0 ( +- 0.00% )
1,000,044,901 uops_dispatched_port_port_1 ( +- 0.00% )
500,038,070 uops_dispatched_port_port_5 ( +- 0.00% )
1,000,066,733 uops_dispatched_port_port_6 ( +- 0.00% )
5,000,000,439 instructions:u # 5.00 insns per cycle ( +- 0.00% )
1,000,439,396 cycles:u ( +- 0.01% )
所以这已经很有趣了，但是很难说清楚发生了什么。也许确切的行为取决于循环入口处的初始条件并且对循环内的顺序敏感（例如，因为使用了计数器）。这个例子表明，除了“随机”或“愚蠢”的调度之外，还有一些事情正在发生。特别是，如果您只是从循环中删除 imul 指令，您会得到以下内容：
示例 3
330,214,329 uops_dispatched_port_port_0 ( +- 0.40% )
314,012,342 uops_dispatched_port_port_1 ( +- 1.77% )
355,817,739 uops_dispatched_port_port_5 ( +- 1.21% )
1,000,034,653 uops_dispatched_port_port_6 ( +- 0.00% )
4,000,000,160 instructions:u # 4.00 insns per cycle ( +- 0.00% )
1,000,235,522 cycles:u ( +- 0.00% )
在这里，add 现在大致平均分布在 p0、p1 和 p5 之间 - 所以 imul 的存在确实影响了add 调度：这不仅仅是某些“避免端口 1”规则的结果。
注意这里总的端口压力只有 3 uops/cycle，因为 xor 是一个调零惯用语，在重命名器中被删除了。让我们尝试使用 4 微秒的最大压力。我希望上面启动的任何机制也能够完美地安排它。我们只是把xor r9, r9改成了xor r9, r10，所以它不再是归零的成语了。我们得到以下结果：
示例 4
top:
xor r9, r10
add r8, rdx
imul rax, rbx, 5
dec esi
jnz top
488,245,238 uops_dispatched_port_port_0 ( +- 0.50% )
1,241,118,197 uops_dispatched_port_port_1 ( +- 0.03% )
1,027,345,180 uops_dispatched_port_port_5 ( +- 0.28% )
1,243,743,312 uops_dispatched_port_port_6 ( +- 0.04% )
5,000,000,711 instructions:u # 2.66 insns per cycle ( +- 0.00% )
1,880,606,080 cycles:u ( +- 0.08% )
糟糕！调度程序没有在 p0156 之间均匀地调度所有内容，而是未充分利用 p0（它只执行了约 49% 的周期），因此 p1 和 p6 被超额订阅，因为它们正在执行 imul 和 dec/jnz 的 必需的 操作。这种行为，我认为与 hayesti 在他们的回答中指出的 counter-based 压力指标一致，并且 uops 在发布时被分配给端口，而不是在执行时 作为两者
hayesti 和 Peter Cordes 提到。这种行为3 使得 执行最早的就绪uops 规则几乎没有那么有效。如果 uops 没有绑定到有问题的执行端口，而是在执行时，那么这个“最旧的”规则将在一次迭代后解决上面的问题——一旦一个 imul 和一个 dec/jnz 被阻止了在一次迭代中，它们总是比竞争的 xor 和 add 指令要早，所以应该总是先安排。不过，我正在学习的一件事是，如果端口是在发布时分配的，则此规则无济于事，因为端口是在发布时预先确定的。我想它仍然有助于支持作为长依赖链一部分的指令（因为它们往往会落后），但这并不是我认为的万能药。
这似乎也解释了上面的结果：p0 被赋予了比实际更大的压力，因为 dec/jnz 组合可以 理论上 在 p06 上执行。 事实上因为预测分支只会到达p6，但也许该信息无法输入压力平衡算法，所以计数器往往看起来相等p016 上的压力，意味着 add 和 xor 的分布与最佳分布不同。
也许我们可以通过稍微展开循环来测试这一点，这样 jnz 就不是一个因素...
1 好的，它写得正确 μops，但这会破坏搜索能力并实际键入“μ”字符 I我通常求助于从网页上复制粘贴字符。
2 我最初在循环中使用 imul 而不是 popcnt，但是令人难以置信的是，_IACA 没有 support it_！
3 请注意，我并不是在暗示这是一个糟糕的设计或其他任何东西 - 可能有非常好的硬件原因导致调度程序无法在执行时轻松做出所有决定时间。
你的问题很棘手，原因如下：
- 答案在很大程度上取决于处理器的微体系结构 代与代之间可能会有很大差异。
- 这些是英特尔通常不会向 public 发布的精细细节。
不过，我会尽力回答...
当多个微指令在保留站就绪时，它们按什么顺序调度到端口？
它应该是最老的 [见下文]，但您的里程可能会有所不同。 P6 微架构（用于 Pentium Pro，2 和 3）使用一个带有五个调度程序的保留站（每个执行端口一个）；调度程序使用优先级指针作为开始扫描准备好要调度的 uops 的地方。它只是伪 FIFO，所以最老的就绪指令完全有可能并不总是被调度。在 NetBurst 微架构（在 Pentium 4 中使用）中，他们放弃了统一的保留站，而是使用两个 uop 队列。这些是适当的折叠优先级队列，因此调度程序可以保证获得最旧的就绪指令。核心架构返回到保留站，我会冒险猜测他们使用了折叠优先级队列，但我找不到来源来证实这一点。如果有人有明确的答案，我会洗耳恭听。
当一个 uop 可以去多个端口时（如上例中的 add 和 lea），如何决定选择哪个端口？
这很难知道。我能找到的最好的是来自 Intel 的 a patent 描述了这种机制。本质上，他们为每个具有冗余功能单元的端口保留一个计数器。当 uops 离开前端到保留站时，它们会被分配一个调度端口。如果必须在多个冗余执行单元之间做出决定，则使用计数器来平均分配工作。当 uops 分别进入和离开保留站时，计数器递增和递减。
当然，这只是一种启发式方法，并不能保证完美无冲突的时间表，但是，我仍然可以看到它与您的玩具示例一起使用。只能去一个端口的指令最终会影响调度程序将 "less restricted" 微指令分派到其他端口。
无论如何，专利的存在并不一定意味着这个想法被采纳了（尽管如此，其中一位作者也是奔腾 4 的技术负责人，所以谁知道呢？）
如果任何一个答案都涉及到在微指令中选择最早的概念，它是如何定义的？自从它交付给 RS 以来的年龄？准备就绪后的年龄？关系是怎么断的？有程序顺序吗？
由于uops是按顺序插入保留站的，所以这里的oldest确实是指进入保留站的时间，即程序顺序最旧
顺便说一下，我会对那些 IACA 结果持保留态度，因为它们可能无法反映真实硬件的细微差别。在 Haswell 上，有一个名为 uops_executed_port 的硬件计数器，它可以告诉您线程中有多少个周期是端口 0-7 的 uops 问题。也许您可以利用这些来更好地了解您的程序？
这是我在 Skylake 上发现的，从 uops 在发布时间（即当它们被发布到 RS）而不是在调度时间（即，此刻他们被送去执行）。之前我明白港口决定是在发货时做出的。
我做了各种测试，试图隔离可以转到 p0156 的 add 操作序列和仅转到端口 0 的 imul 操作序列。典型的测试是像这样：
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
... many more mov instructions
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
imul ebx, ebx, 1
imul ebx, ebx, 1
imul ebx, ebx, 1
imul ebx, ebx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
... many more mov instructions
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
基本上有一个很长的 mov eax, [edi] 指令导入，它只在 p23 上发出，因此不会阻塞指令使用的端口（我也可以使用 nop 指令，但测试会有点不同，因为 nop 不向 RS 发出）。接下来是 "payload" 部分，这里由 4 个 imul 和 12 个 add 组成，然后是更多虚拟 mov 指令的引出部分。
首先，让我们看一下上面链接的 the patent，他描述了基本思想：每个端口的计数器跟踪分配给端口的微指令总数，这些微指令用于负载平衡端口分配。看看专利说明中包含的这个table：
此 table 用于在 p0 或 p1 之间为专利中讨论的 3-wide 架构的问题组中的 3-uops 选择。请注意，该行为取决于 uop 在组中的位置 ，并且有 4 个规则 1 基于计数，它们传播以合乎逻辑的方式进行。特别是，在为整个组分配未充分使用的端口之前，计数需要达到 +/- 2 或更大。
让我们看看是否可以观察 Sklake 上的 "position in issue group" 事项行为。我们使用单个 add 的有效载荷，例如：
add edx, 1 ; position 0
mov eax, [edi]
mov eax, [edi]
mov eax, [edi]
... 然后我们在 4 指令卡盘内滑动它，如：
mov eax, [edi]
add edx, 1 ; position 1
mov eax, [edi]
mov eax, [edi]
...等等，测试问题组2中的所有四个位置。这显示了以下内容，当 RS 已满（mov 指令）但没有任何相关端口的端口压力时：
- 第一个
add指令转到p5或p6，选择的端口通常随着指令变慢而交替（即，add指令在偶数位置转到p5，奇数位置转到p6)。 - 第二个
add指令也转到p56- 以第一个没有转到的两个指令为准。 - 在那之后，进一步的
add指令开始围绕p0156进行平衡，p5和p6通常领先，但总体上相当均匀（即差距p56和其他两个端口之间没有增长）。
接下来，我查看了如果使用 imul 操作加载 p1 会发生什么，然后首先是一堆 add 操作：
imul ebx, ebx, 1
imul ebx, ebx, 1
imul ebx, ebx, 1
imul ebx, ebx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
add r9, 1
add r8, 1
add ecx, 1
add edx, 1
结果表明调度程序处理得很好 - 所有 imul 都被调度到 p1（如预期的那样），然后 none 随后的 [=18] =] 指令去了 p1，而是散布在 p056 周围。所以这里的调度运行良好。
当然，当情况相反时，imul 系列出现在 add 之后，p1 会在 [= 之前加载它的添加份额20=]s 命中。这是端口分配在发布时按顺序发生的结果，因为在调度 add 时没有 "look ahead" 和查看 imul 的机制。
总的来说，调度程序看起来在这些测试用例中做得很好。
它没有解释在像下面这样更小、更紧密的循环中会发生什么：
sub r9, 1
sub r10, 1
imul ebx, edx, 1
dec ecx
jnz top
就像我的问题中的 示例 4 一样，尽管有两个 sub 指令应该能够在 每个 周期进入 p0。 p1 和 p6 超额订阅，每个迭代执行 1.24 微指令（1 是理想的）。我无法对这个答案顶部运行良好的示例与错误循环之间的差异进行三角测量 - 但仍有很多想法可以尝试。
我注意到没有说明的示例 延迟差异 似乎没有遇到这个问题。例如，这是另一个具有 "complex" 端口压力的 4-uop 循环：
top:
sub r8, 1
ror r11, 2
bswap eax
dec ecx
jnz top
uop图如下：
instr p0 p1 p5 p6
sub X X X X
ror X X
bswap X X
dec/jnz X
因此 sub 必须始终转到 p15，如果事情要解决，则与 bswap 共享。他们这样做：
“./sched-test2”的性能计数器统计数据（2 次运行）：
999,709,142 uops_dispatched_port_port_0 ( +- 0.00% )
999,675,324 uops_dispatched_port_port_1 ( +- 0.00% )
999,772,564 uops_dispatched_port_port_5 ( +- 0.00% )
1,000,991,020 uops_dispatched_port_port_6 ( +- 0.00% )
4,000,238,468 uops_issued_any ( +- 0.00% )
5,000,000,117 instructions:u # 4.99 insns per cycle ( +- 0.00% )
1,001,268,722 cycles:u ( +- 0.00% )
所以问题可能与指令延迟有关（当然，示例之间还有其他差异）。这是 this similar question 中出现的内容。
1table有5条规则，但是0和-1计数的规则是一样的。
2当然，我不能确定问题组的开始和结束位置，但无论如何我们测试四个不同的位置当我们向下滑动四个指令时（但标签可能是错误的）。我也不确定 确定 问题组的最大大小是 4 - 管道的早期部分更宽 - 但我相信它是并且一些测试似乎表明它是（循环与多个4 微指令显示一致的调度行为）。无论如何，结论适用于不同的调度组大小。
最近英特尔微体系结构上基本块的准确吞吐量预测[^1] 的第 2.12 节解释了如何分配端口，但它未能解释问题描述中的示例 4。我也没有弄清楚延迟在端口分配中扮演什么角色。
Previous work [19, 25, 26] has identified the ports that the µops of individual instructions can use. For µops that can use more than one port, it was, however, previously unknown how the actual port is chosen by the processor. We reverse-engineered the port assignment algorithm using microbenchmarks. In the following, we describe our findings for CPUs with eight ports; such CPUs are currently most widely used.
The ports are assigned when the µops are issued by the renamer to the scheduler. In a single cycle, up to four µops can be issued. In the following, we will call the position of a µop within a cycle an issue slot; e.g., the oldest instruction issued in a cycle would occupy issue slot 0.
The port that a µop is assigned depends on its issue slot and on the ports assigned to µops that have not been executed and were issued in a previous cycle.
In the following, we will only consider µops that can use more than one port. For a given µop m, let $P_{min}$ be the port to which the fewest non-executed µops have been assigned to from among the ports that m can use. Let $P_{min'}$ be the port with the second smallest usage so far. If there is a tie among the ports with the smallest (or second smallest, respectively) usage, let $P_{min}$ (or $P_{min'}$) be the port with the highest port number from among these ports (the reason for this choice is probably that ports with higher numbers are connected to fewer functional units). If the difference between $P_{min}$ and $P_{min'}$ is greater or equal to 3, we set $P_{min'}$ to $P_{min}$.
The µops in issue slots 0 and 2 are assigned to port $P_{min}$ The µops in issue slots 1 and 3 are assigned to port $P_{min'}$.
A special case is µops that can use port 2 and port 3. These ports are used by µops that handle memory accesses, and both ports are connected to the same types of functional units. For such µops, the port assignment algorithm alternates between port 2 and port 3.
我试图找出$P_{min}$和$P_{min'}$是否在线程之间共享（Hyper-Threading），即一个线程是否可以影响端口在同一个核心中分配另一个。
只需将 BeeOnRope 的答案中使用的代码分成两个线程即可。
thread1:
.loop:
imul rax, rbx, 5
jmp .loop
thread2:
mov esi,1000000000
.top:
bswap eax
dec esi
jnz .top
jmp thread2
其中指令 bswap 可以在端口 1 和 5 上执行，imul r64, R64, i 可以在端口 1 上执行。如果线程之间共享计数器，您会看到 bswap 在端口 5 上执行imul 在端口 1 上执行。
实验记录如下，其中线程1的端口P0和P5，线程2的p0应该记录了少量的non-user数据，但不影响结论。从数据可以看出，线程2的bswap指令是在P1和P5口交替执行的，并没有放弃P1
| port | thread 1 active cycles | thread 2 active cycles |
|---|---|---|
| P0 | 63,088,967 | 68,022,708 |
| P1 | 180,219,013,832 | 95,742,764,738 |
| P5 | 63,994,200 | 96,291,124,547 |
| P6 | 180,330,835,515 | 192,048,880,421 |
| total | 180,998,504,099 | 192,774,759,297 |
因此，线程之间不共享计数器。
这个结论与SMotherSpectre[^2]不冲突，SMotherSpectre[^2]使用时间作为边信道。 （例如，线程 2 在端口 1 上等待更长时间才能使用端口 1。）
Executing instructions that occupy a specific port and measuring their timing enables inference about other instructions executing on the same port. We first choose two instructions, each scheduled on a single, distinct, execution port. One thread runs and times a long sequence of single µop instructions scheduled on port a, while simultaneously the other thread runs a long sequence of instructions scheduled on port b. We expect that, if a = b, contention occurs and the measured execution time is longer compared to the a ≠ b case.
[^1]：Abel、Andreas 和 Jan Reineke。 “最新英特尔微体系结构上基本块的准确吞吐量预测。” arXiv 预印本 arXiv:2107.14210 (2021).
[^2]：Bhattacharyya、Atri、Alexandra Sandulescu、Matthias Neugschwandtner、Alessandro Sorniotti、Babak Falsafi、Mathias Payer 和 Anil Kurmus。 “SMoTherSpectre：通过端口争用利用推测执行。” 2019 年 ACM SIGSAC 计算机和通信安全会议论文集，2019 年 11 月 6 日，785-800。 https://doi.org/10.1145/3319535.3363194.