x86 uops是如何安排的?
现代x86 CPU将传入的指令流分解为微操作(uops1),然后在输入准备就绪时将这些uop无序排列。 虽然基本思想很明确,但我想知道具体的细节安排,因为它会影响微观优化决策。
例如,采取以下玩具循环2:
top:
lea eax, [ecx + 5]
popcnt eax, eax
add edi, eax
dec ecx
jnz top
这基本上实现了循环(具有以下对应关系: eax -> total, i -> ecx
):
do {
total += popcnt(c + 5);
} while (--c > 0);
我熟悉通过查看uop故障,依赖链延迟等来优化任何小型循环的过程。 在上面的循环中,我们只有一个携带依赖链: dec ecx
。 循环的前三条指令( lea
, imul
, add
)是依赖链的一部分,每个循环都新开始。
最后的dec
和jne
融合在一起。 因此,我们总共有4个融合域uop,以及一个仅具有1个周期延迟的循环携带依赖链。 所以基于这个标准,似乎循环可以在1个循环/迭代中执行。
但是,我们也应该看看港口的压力:
lea
可以在端口1和5上执行 add
可以在端口0,1,5和6上执行 jnz
在端口6上执行 因此,要进行1次循环/迭代,您几乎需要以下事情发生:
lea
必须在端口5上执行(并且从不在端口1上) add
必须在端口0上执行,并且永远不会在其可执行的任何其他三个端口上执行 jnz
只能在端口6上执行 这是很多的条件! 如果指令是随机调度的,你可能会得到更糟糕的吞吐量。 例如,75%的add
将进入端口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
从窃取端口5 lea
1出来的10个循环。 它也不会知道,融合的分支要去口6,因为预计拍摄,所以它把大部分的微指令为分支端口0,而大部分的微指令的的add
端口6,而比其他方式。
目前尚不清楚IACA报告的最优的0.05个周期是由一些深入的,精确的分析得出的结果,还是由它使用的算法的不太深刻的结果,例如,分析固定周期数量的循环,或仅仅是一个循环错误或其他。 同样的情况也适用于它认为会进入非理想港口的0.1分之一的小区。 目前还不清楚是否解释另一个 - 我认为10次错误分配端口1会导致每次迭代11/10 = 1.1个周期的循环次数,但是我没有计算出实际的下游结果 - 可能平均影响较小。 或者它可能只是四舍五入(0.05 == 0.1到1位小数)。
那么现代x86 CPU如何实际安排? 尤其是:
add
和lea
)时,它是如何决定选择哪个端口的? Skylake上的结果
我们来测量Skylake上的一些实际结果,以检查哪些答案可以解释实验证据,因此我的Skylake盒子上有一些真实测量结果(来自perf
)。 令人困惑的是,我将切换到使用imul
因为我的“只能在一个端口上执行”指令,因为它有很多变体,包括允许您为源和目标使用不同寄存器的3参数版本。 当试图构造依赖关系链时,这非常方便。 它也避免了popcnt
具有的整个“对目的地的不正确依赖”。
独立指令
我们首先看看简单的(?)情况,指令是相对独立的 - 没有任何依赖链而不是像循环计数器那样的不重要的。
这是一个4 uop循环(只有3个被执行的uops),并且压力很低。 所有指示都是独立的(不要共享任何来源或目的地)。 原则上这个add
可以窃取该dec所需的imul
或p6
所需的p1
:
例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
然后突然p1
/ 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”规则的结果。
请注意,由于xor
是一个调零习惯用法,并且在重命名器中被淘汰,因此总端口压力仅为3个uops /周期。 让我们尝试一下4个uops的最大压力。 我期望上面的任何机制都能够完美安排这一点。 我们只将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
,因为他们都执行其所需的OPS被oversubcribed imul
和dec/jnz
。 我认为,这种行为与hayesti在回答中指出的基于反压力的压力指标是一致的,并且uops 在问题时间被分配到一个港口,而不是在 hayesti和Peter Cordes提到的执行时间 。 该行为3使得执行最早的准备好的uops规则几乎没有效果。 如果uops不是绑定到执行端口而是执行,那么这个“最老”的规则将在一次迭代后解决上述问题 - 一旦一个imul
和一个dec/jnz
被阻止进行一次迭代,他们将总是比旧的竞争xor
和add
说明,所以应该总是首先安排。 我正在学习的一点是,如果在问题时间分配端口,则此规则不起作用,因为端口是在问题时间预先确定的。 我认为它仍然有利于支持长期依赖链的一部分的指令(因为这些链将倾向于落后),但这不是我认为的治愈方法。
这也似乎是一个解释上述结果: p0
被分配更多的压力比它确实有因为dec/jnz
组合在理论上可以执行的p06
。 事实上,因为分支预测被采用,所以它只能到达p6
,但也许这个信息不能反馈到压力平衡算法中,所以计数器往往会在p016
上看到相同的压力,这意味着add
和xor
会在四周传播不同于最佳。
可能我们可以通过展开循环来测试这个,所以jnz
不是一个因素......
1好吧,它被正确写成μops,但是这会杀死搜索能力并实际输入“μ”字符,我通常会采取从网页上复制粘贴字符的方式。
2我最初在循环中使用了imul
而不是popcnt
,但令人难以置信的是,IACA不支持它!
3请注意,我并不是说这是一个糟糕的设计或任何其他的东西 - 可能有非常好的硬件原因,为什么调度程序无法在执行时轻松做出所有决定。
你的问题很困难,原因有两个:
不过,我会试着回答...
当保留站中有多个uops准备就绪时,他们按照什么顺序安排到端口?
它应该是最老的[见下文],但是你的里程可能会有所不同。 P6微架构(在Pentium Pro中使用,2和3)使用带有5个调度程序(每个执行端口一个)的保留站; 调度程序使用优先级指针作为开始扫描准备好的uops来分派的地方。 它只是伪FIFO,所以完全可能的是最老的就绪指令并不总是被调度。 在NetBurst微体系结构(在奔腾4中使用)中,他们放弃了统一的预留站,并使用了两个uop队列。 这些都是正确折叠的优先级队列,因此调度程序保证获得最早的就绪指令。 核心架构返回到一个保留站,我会冒险教育他们使用折叠优先级队列的猜测,但我找不到一个来源来证实这一点。 如果有人有明确的答案,我全都耳熟能详。
当一个uop可以进入多个端口(如上面例子中的add和lea)时,它是如何决定选择哪个端口的?
这很难知道。 我能找到的最好的是来自英特尔的专利,描述了这种机制。 实质上,它们为每个具有冗余功能单元的端口保留一个计数器。 当uops离开前端到保留站时,它们被分配一个调度端口。 如果必须在多个冗余执行单元之间做出决定,则使用计数器均匀分配工作。 当微机进入和离开保留站时,计数器递增和递减。
自然,这仅仅是一种启发式的方式,并不能保证完美的无冲突时间表,但是,我仍然可以看到它与您的玩具示例一起工作。 只能进入一个端口的指令最终会影响调度程序将“限制较少”的uop调度到其他端口。
无论如何,专利的存在并不一定意味着这个想法被采纳了(尽管这表示,其中一位作者也是Pentium 4的技术主管,所以谁知道呢?)
如果任何一个答案涉及像老年人这样的概念在uops之间进行选择,它是如何定义的? 自从交付给RS以来的年龄? 自成立以来的年龄? 领带如何断裂? 程序顺序是否会进入它?
由于微博顺序插入到保留站,因此这里的最老确实指的是它进入保留站的时间,即按照程序顺序最早。
顺便说一下,我会把这些IACA的结果放在一块盐里,因为它们可能不会反映真实硬件的细微差别。 在Haswell上,有一个称为uops_executed_port的硬件计数器,可以告诉您线程中端口0-7发生了多少次周期。 也许你可以利用这些来更好地理解你的程序?
这是我在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)。 接下来是“有效载荷”部分,这里由4个imul
和12个add
,然后是更多虚拟mov
指令的导出部分。
首先,我们来看看上面链接的hayesti专利,他描述了基本思想:每个端口的计数器跟踪分配给端口的uops总数,这些端口用于负载平衡端口分配。 看看专利说明中包含的这张表格:
该表用于针对专利中讨论的3范围架构的问题组中的3-uop在p0
或p1
之间进行选择。 请注意,行为取决于uop在组中的位置,并且根据计数有4条规则1,这些规则以合理的方式将uops分散开来。 特别是,在整个组被分配使用不足的端口之前,计数需要在+/- 2或更大。
让我们来看看我们能否观察到“问题组中的位置”对斯克莱克的行为有影响。 我们使用单个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
,在奇数位置add
指令到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
(如预期的那样),然后没有任何随后的add
指令进入p1
,而是分布在p056
周围。 所以这里的调度运作良好。
当然,当形势逆转,并且该系列的imul
来了后add
S, p1
被载入了它的份额之前添加imul
热播。 这是由于端口分配在问题发生时按顺序发生的结果,因为没有机制“ imul
”并在调度add
时看到最终imul
。
总的来说,调度程序看起来在这些测试用例中做得很好。
它不能解释如下所示的更小,更紧密的循环中会发生什么情况:
sub r9, 1
sub r10, 1
imul ebx, edx, 1
dec ecx
jnz top
就像我的问题中的示例4一样,尽管有两个sub
指令应该能够在每个周期转到p0
,但该循环仅在约30%的周期内填充p0
。 p1
和p6
是超额认购的,每次迭代执行1.24 uops(1是理想的)。 我无法对在这个答案的顶部工作得很好的例子与不好的循环之间的差异进行三角测量 - 但仍然有许多想法可以尝试。
我确实注意到没有指令延迟差异的例子似乎没有受到这个问题的影响。 例如,下面是另一个具有“复杂”端口压力的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% )
所以看起来这个问题可能与指令延迟有关(当然,这些例子之间还有其他差异)。 这是类似的问题。
1该表有5个规则,但0和-1计数的规则是相同的。
2当然,我不能确定问题组在哪里开始和结束,但是无论我们测试四个不同的位置,我们都会按照四条指令进行测试(但标签可能是错误的)。 我也不确定问题组的最大大小是4 - 更早的部分管道更宽 - 但我相信它是和一些测试似乎表明它是(循环与4个uops的倍数显示一致的调度行为)。 无论如何,这些结论都与不同的调度组大小有关。
链接地址: http://www.djcxy.com/p/28161.html上一篇: How are x86 uops scheduled, exactly?
下一篇: Does using xor reg, reg give advantage over mov reg, 0?