当CPU执行指令时,循环迭代之间存在数据依赖性时,关键路径是如何形成的



在《程序员视角下的计算机系统》一书中,有以下循环的汇编代码:

L3:
1. movq %rax, (%rsi)
2. movq (%rdi), %rax
3. addq $1, %rax
4. subq $1, %rdx
5. jne  .L3

用于建模问题的抽象CPU具有以下功能单元:

容量<1><2>
操作延迟问题
+114
负载4

是的,有许多单独的短3指令依赖链,每个依赖链在一次迭代中由load(2)开始,在下一次迭代结束于store(1)。(假设没有内存混叠)。

但除了循环计数器之外,没有循环承载依赖链;3指令dep链在下次执行时不会重新耦合到这些指令中任何一条的输入依赖项。负载(2)打破了对RAX旧值的依赖,因此这是另一个短dep链的开始,而不是上次运行时开始的链的延续。

如果add $1, %raxadd %rax, %rdi或使下一个加载地址依赖于上一个加载的某个其他指令,则它将被循环携带。在这种情况下,只有商店是";分叉";每次迭代。正如中的随机存储器访问微基准测试一样,为什么一行代码的性能会下降10倍

因此,一个大范围的无序执行CPU可以让任意数量的dep链并行运行,使它们的延迟重叠。


事实上,Sandybridge和更高版本应该能够在每个时钟1次迭代的情况下运行此循环,因为sub/jnz宏融合为前端和后端的单个uop。sub前端吞吐量和后端延迟瓶颈;冰湖的5宽前端不会跑得更快。

uiCA可以在Haswell上模拟它,看看这些指令如何真正通过实际管道的前端和后端,假设所有加载和存储都在L1d缓存中命中,并且没有别名。(通过反向工程尽可能准确地模拟,以模拟循环的前端行为和uop调度。它不模拟缓存。)该链接显示Haswell每次迭代都能维持1.0个周期。跟踪表可视化展开循环迭代,并显示从前端到后端发出的每条指令的周期,以及何时将其调度到执行单元、何时完成执行以及何时退出。(如果跟踪表链接失效,请使用第一个链接通过从源代码重新分析来重新生成;asm源代码是第一个链接的URL的一部分。)

非跟踪输出如下。(LSD=循环缓冲区,MITE=传统解码,DSB=uop缓存,MS=微码定序器。这里的所有uop都来自"锁定它们"的循环缓冲区。Issued与Exec是融合域uop与非融合域。Intel CPU将存储解码为单独的存储地址并存储数据uop,微融合到一个前端uop中,该前端uop在后端以2运行,但可以以1发布,并且只使用1个ROB条目。)

Throughput (in cycles per iteration): 1.00
Bottlenecks: Dependencies, Issue, LSD, Ports
The following throughputs could be achieved if the given property were the only bottleneck:
- LSD: 1.00
- Issue: 1.00
- Ports: 1.00
- Dependencies: 1.00
M - Macro-fused with previous instruction
┌───────────────────────┬────────┬───────┬───────────────────────────────────────────────────────────────────────┬───────┐
│ MITE   MS   DSB   LSD │ Issued │ Exec. │ Port 0   Port 1   Port 2   Port 3   Port 4   Port 5   Port 6   Port 7 │ Notes │
├───────────────────────┼────────┼───────┼───────────────────────────────────────────────────────────────────────┼───────┤
│                    1  │   1    │   2   │                    0.13     0.25      1                         0.63  │       │ mov qword ptr [rsi], rax
│                    1  │   1    │   1   │                    0.5      0.5                                       │       │ mov rax, qword ptr [rdi]
│                    1  │   1    │   1   │  0.32     0.33                                0.35                    │       │ add rax, 0x1
│                    1  │   1    │   1   │                                                         1             │       │ sub rdx, 0x1
│                       │        │       │                                                                       │   M   │ jnz 0x6
├───────────────────────┼────────┼───────┼───────────────────────────────────────────────────────────────────────┼───────┤
│                    4  │   4    │   5   │  0.32     0.33     0.63     0.74      1       0.35      1       0.63  │       │ Total
└───────────────────────┴────────┴───────┴───────────────────────────────────────────────────────────────────────┴───────┘

Zen 1和更高版本也可以在1/clock上跟上这个循环;AMD只将testcmpjcc融合,而不是同时修改整数寄存器的指令,因此需要5个uop才能发布/重命名。但Zen的前端是5条指令/6uops宽,因此其前端带宽几乎无法跟上subq $1, %rdx的1个周期延迟瓶颈

仅供参考,CS:APP使用的CPU型号基本上是Intel Haswell(https://www.realworldtech.com/haswell-cpu/):注意add/sub的4/clock吞吐量,高于Sandybridge家族的3。在其他CS:APP问题中,我们看到他们的CPU有2/时钟FP FMA/mul,但有1/时钟FP加法,延迟与Haswell匹配。例如对于必须按顺序发生的操作,处理器的延迟界限和吞吐量界限还要注意如何在每次迭代中读取mulsd结果,但由不同的dep链读取。

无论如何,如果有任何循环携带的依赖项超过1个周期,这将是一个瓶颈。例如,将or $0, %rdx添加到循环中,使其成为2个循环的依赖项,uiCA正确地模拟了瓶颈,平均每次迭代2.0个循环。


异常执行程序可以看到的范围的限制

如果我的推理有道理,那么是什么决定了一个CPU可以提前执行多少使用相同寄存器的写入操作(在本例中为loadq和addq到%rax)?

在这种情况下,前端瓶颈可能会阻止后端走得更远。但如果不是这样(或者在Ice Lake CPU上,用于4个uop循环的5宽前端),它将受到无序执行资源的限制,特别是要重命名到上的物理寄存器的数量。

Haswell的整数PRF有168个条目。(https://www.realworldtech.com/haswell-cpu/3/)。

还可能由ReOrder Buffer(ROB)容量决定。Haswell的ROB大小为192 uops。存储不写寄存器,因此通过一些非常简单的近似,循环中只有3/4的uop需要为其输出分配一个物理寄存器。168个PRF条目中已经需要16个以上来保持体系结构状态(包括未修改的寄存器的值),但作为手动波浪形粗略计算,用192个uop填充ROB也会占用192 * 3/4 = 144物理寄存器文件条目。

请参阅https://blog.stuffedcow.net/2013/05/measuring-rob-capacity/对于像这样的真实世界的实验。

一个明显较小的限制是调度器大小(RS=预留站)。在哈斯韦尔只有60个单位。它跟踪未执行的uop(在Sandybridge家族的未融合域中,因此商店在这里占用2个插槽。)与ROB跟踪未退役的uop相比。

请参阅理解lfence对具有两个长依赖链的循环的影响,了解增加长度re:RS大小对重叠长dep链的影响。

对于更宽的前端,填充RS的未执行的uop将主要是每时钟1个sub $1, %rdx + jnzuop(从sub+分支的宏融合到端口6的单个uop,因为它是预测的)和存储数据uop(在Haswell上也限制为1/clock,不像在这种简单寻址模式下可以在p2/p3/p7中的任何一个上运行的存储地址)。

加载和添加uop可以执行并释放它们的RS条目(平均每个周期超过1个),等待在所有早期指令都已执行时从ROB退出。

如果您在uiCA上为更宽的CPU(如Ice Lake)模拟此代码,请注意,在向下滚动跟踪时,从发布到退出之间的周期数不断增加。与Haswell不同,前端确实远远领先于后端。(Ice Lake具有包括存储数据在内的2/时钟存储吞吐量,因此只有延迟瓶颈会备份这些sub/jnz uops。除此之外,它看起来像是为您的Haswell后端提供了更宽的前端。当然,Ice Lak比Haswell有更大的ROB、RS和PRF。)

也相关:

  • 在预测现代超标量处理器上的操作延迟时需要考虑哪些因素,以及如何手动计算它们
  • 为什么mulss在Haswell上只需要3个周期,与Agner';s指令表?(使用多个累加器展开FP回路)
  • https://agner.org/optimize/尤其是他的微体系结构指南,其中描述了不同x86微体系结构的流水线细节
  • https://uops.info/
  • 现代微处理器90分钟指南!优秀的背景材料,以填补在理解管道和无序执行的基础知识方面可能存在的空白。以及CPU架构师所面临的设计权衡(电源、IPC、时钟频率)

相关内容

  • 没有找到相关文章

最新更新