如何安排x86 uops？

Question

现代x86 CPU将传入的指令流分解为微操作(uops ¹),然后在输入准备就绪时将这些uop 无序调度.虽然基本思路很清楚,但我想了解准备好指令的具体细节,因为它会影响微优化决策.

例如,采取以下玩具循环²:

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,imul,add)是开始新鲜每个环一个依赖关系链的一部分.

决赛dec和jne融合.因此,我们总共有4个融合域uop,以及一个仅循环携带的依赖链,延迟为1个周期.因此,基于该标准,似乎循环可以在1个周期/迭代时执行.

但是,我们也应该关注港口压力:

• 在lea能够在端口1和5执行
• popcnt可以在端口1上执行
• 在add可以在端口0,1,5和6执行
• 预测采用jnz在端口6上执行

因此,要进行1次循环/迭代,您几乎需要执行以下操作:

• popcnt 必须在端口1上执行(它可以执行的唯一端口)
• 在lea 必须在端口5执行(和从未在端口1)
• 在add 必须执行端口0,从来没有在任何其他三个端口的它可以执行上
• 将jnz只能在端口6执行反正

这是很多条件!如果指令是随机安排的,那么吞吐量会更差.例如,75%的add会去端口1,5或6,这将延迟popcnt,lea或jnz通过一个循环.同样地,lea它可以转到2个端口,一个共享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从lea10个循环中的1个开始窃取端口5 .它也不知道融合分支将会被预测到,因为它被预测,因此它将大部分uop用于端口0上的分支,而大多数uop用于addon端口6,而不是另一种方式.

目前尚不清楚IACA报告超过最优的额外0.05周期是一些深度,准确分析的结果,还是其使用的算法的不太富有洞察力的结果,例如,在固定数量的周期内分析环路,或者仅仅是错误或其他什么.对于它认为将进入非理想端口的uop的0.1分数也是如此.还不清楚是否有人解释了另一个 - 我认为错误分配10次端口1将导致循环计数为11/10 =每次迭代1.1个循环,但我还没有找到实际的下游结果 - 也许平均影响较小.或者它可能只是舍入(0.05 == 0.1到1小数位).

那么现代x86 CPU如何实际安排？特别是:

1. 当多个uop 在预留站中准备就绪时,它们按什么顺序安排到端口？
2. 当UOP可以去多个端口(如add与lea在上面的例子中),它是如何决定选择哪个端口？
3. 如果有任何问题的答案涉及类似概念最早的微操作中进行选择,它是如何定义的？自交付给RS以来的年龄？它准备好了以后的年龄？关系如何破裂？程序订单是否会进入它？

Skylake的结果

让我们测量一下Skylake的一些实际结果来检查哪些答案解释了实验证据,所以这里是perf我的Skylake盒子上的一些真实测量结果(来自).令人困惑的是,我将切换到使用imul"仅在一个端口上执行"指令,因为它有许多变体,包括允许您为源和目标使用不同寄存器的3参数版本.这在尝试构建依赖链时非常方便.它还避免了整个"对目的地的不正确依赖" popcnt.

独立指示

让我们从查看指令相对独立的简单(？)情况开始 - 没有任何依赖链,除了像循环计数器这样的简单依赖链.

这是一个4 uop循环(只有3个执行的uops),压力很小.所有说明都是独立的(不要共享任何来源或目的地).在add原则上可以偷p1需要通过imul或p6由DEC的需要:

例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/ p5split正好是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 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因为他们执行他们都被oversubcribed 需要的OPS imul和dec/jnz.我认为这种行为与hayesti在答案中指出的基于反压力的指标是一致的,并且在发行时将uops 分配到一个端口,而不是像hayesti和Peter Cordes所提到的那样在执行时分配.该行为³使得执行最早的准备好的uops规则几乎没有那么有效.如果微操作是没有问题势必执行港口,而是在执行,那么这个"最老"的规则将修复上面一个迭代后的问题-当一个人imul,一个dec/jnz耽搁回单次迭代,他们总是会比旧竞争xor和add指示,所以应始终先安排.我正在学习的是,如果在发布时分配端口,则此规则无效,因为端口是在发布时预先确定的.我想这仍然有助于支持长指令链的一部分指令(因为它们往往会落后),但它并不是我认为的全部治疗方法.

这也似乎是对上述结果的解释:p0因为dec/jnz组合可以在理论上执行,因此分配的压力比实际压力大得多p06.事实上,因为分支是预测的,它只能进行p6,但也许这些信息无法提供给压力平衡算法,因此计数器倾向于看到相等的压力p016,这意味着add并且xor得到的传播不同于最优.

可能我们可以通过展开循环来测试这个,所以jnz它不是一个因素......

---

¹好吧,它是正确编写的μops,但这会杀死搜索能力并实际输入"μ"字符,我通常会从网页上复制粘贴字符.

²我最初使用的是imul代替popcnt循环,但令人难以置信的是,IACA不支持它!

³请注意,我并不是说这是一个糟糕的设计或任何东西 - 可能有很好的硬件原因导致调度程序无法在执行时轻松做出所有决策.

Answer 1

由于以下几个原因,您的问题很难:

1. 答案很大程度上取决于处理器的微体系结构,它可以代代相传.
2. 这些都是细粒度的细节,英特尔通常不会向公众发布这些细节.

不过,我会试着回答......

当多个uop在预留站中准备就绪时,它们按什么顺序安排到端口？

它应该是最古老的[见下文],但您的里程可能会有所不同.P6微体系结构(用于Pentium Pro,2和3)使用了一个带有五个调度程序的预留站(每个执行端口一个); 调度程序使用优先级指针作为开始扫描准备好的uops以进行调度的地方.它只是伪FIFO,因此完全有可能最旧的就绪指令并不总是被调度.在NetBurst微体系结构(Pentium 4中使用)中,他们抛弃了统一预留站并使用了两个uop队列.这些是正确的折叠优先级队列,因此保证调度程序获得最早的就绪指令.核心架构返回到预订站,我会冒险猜测他们使用了折叠优先级队列,但我找不到确认这一点的来源.如果有人有明确的答案,我会全力以赴.

当uop可以进入多个端口时(如上例中的add和lea),如何确定选择哪个端口？

知道这很棘手.我能找到的最好的是来自英特尔的专利,描述了这种机制.从本质上讲,它们为每个具有冗余功能单元的端口保留一个计数器.当uops离开前端到保留站时,会为它们分配一个调度端口.如果必须在多个冗余执行单元之间做出决定,则计数器用于均匀分配工作.当uops分别进入和离开保留站时,计数器递增和递减.

当然,这只是一种启发式方法,并不能保证完美的无冲突时间表,但是,我仍然可以看到它与您的玩具示例一起使用.只能到达一个端口的指令最终会影响调度程序将"限制较少"的微指令发送到其他端口.

在任何情况下,专利的存在并不一定意味着该想法被采纳(虽然说,其中一位作者也是Pentium 4的技术主管,所以谁知道呢？)

如果任何答案涉及像uops这样的概念在uops中进行选择,它是如何定义的？自交付给RS以来的年龄？它准备好了以后的年龄？关系如何破裂？程序订单是否会进入它？

由于uops按顺序插入保留站,因此这里最老的确实是指它进入保留站的时间,即按程序顺序最旧.

顺便说一下,我会把那些IACA结果带到一块盐,因为它们可能无法反映真实硬件的细微差别.在Haswell上,有一个名为uops_executed_port的硬件计数器可以告诉你线程中有多少个循环是uops问题到端口0-7.也许您可以利用这些来更好地了解您的计划？

Answer 2

以下是我在Skylake上发现的内容,从发布时将uop分配给端口的角度来看(即,当它们发布到RS时),而不是在发送时(即,在发送执行时).在我了解港口决定是在派遣时做出之前.

我做了各种测试,试图隔离add可以进入的操作序列p0156和imul仅进入端口0的操作.典型的测试是这样的:

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上面提到的专利,并描述了基本思想:每个端口的计数器跟踪分配给端口的uop总数,用于负载均衡端口分配.请查看专利说明中包含的此表:

此表用于之间挑选p0或p1用于发布组在专利中讨论的3-宽架构在3微指令.请注意,行为取决于组中uop的位置,并且基于计数有4个规则¹,它们以逻辑方式分布uop.特别是,在为整个组分配未充分利用的端口之前,计数需要为+/- 2或更大.

让我们看看我们是否可以在Sklake上观察"问题组中的位置"问题.我们使用单个有效负载,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,另两个端口不生长).

接下来,我看了看,如果加载了会发生什么p1用imul行动在一堆,然后再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在adds之后,p1在imuls命中之前加载了它的份额.这是端口分配在发布时按顺序发生的结果,因为没有"向前看"的机制并且看到imul调度adds的时间.

总体而言,调度程序看起来在这些测试用例中做得很好.

它没有解释在更小,更紧密的循环中发生的情况,如下所示:

sub r9, 1
sub r10, 1
imul ebx, edx, 1
dec ecx
jnz top

就像我的问题中的例子4一样p0,尽管在每个周期都有两个sub指令应该可以进行,但这个循环只能填充~30%的周期.并且超额认购,每次迭代执行1.24微秒(1是理想的).我无法对在这个答案顶部工作得很好的例子与坏循环之间的差异进行三角测量 - 但仍有许多想法可以尝试.p0p1p6

我注意到没有指令延迟差异的示例似乎没有受到此问题的影响.例如,这是另一个具有"复杂"端口压力的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% )

所以似乎问题可能与指令延迟有关(当然,这些例子之间还存在其他差异).这是类似问题中出现的问题.

¹该表有5个规则,但0和-1计数的规则是相同的.

²当然,我无法确定问题组的开始和结束位置,但无论我们在下滑四条指令时测试四个不同的位置(但标签可能是错误的).我也不确定问题组最大大小是4 - 管道的早期部分更宽 - 但我相信它是,并且一些测试似乎表明它是(具有4个uop的倍数的循环显示一致的调度行为).在任何情况下,结论都适用于不同的调度组大小.