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

7z5jn7bk  于 2023-01-17  发布在  其他
关注(0)|答案(1)|浏览(124)

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

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

用于建模问题的抽象CPU具有以下功能单元:
| 操作|潜伏期|问题|容量|
| - ------|- ------|- ------|- ------|
| + |1个|1个|四个|
| 负载|四个|1个|第二章|
假设%rsi%rdi指向不同的存储器位置,作者说关键路径由subq指令形成,实际上存在数据依赖性,因为在每次迭代中减小%rdx,我们需要来自前一次迭代的值。
但是第2-3行第1行之间不是也有数据依赖关系吗?如果有,为什么没有形成关键路径?我的回答是这样的:

  • CPU可以使用称为 * 寄存器重命名 * 的技术提前执行第2行第3行,以便进行下一次迭代
  • 因此,当第1行将要被执行以用于一些稍后的迭代时,用于它的数据已经准备好。

如果我的推理是有道理的,那么是什么决定了CPU可以提前执行多少个使用同一寄存器的write操作(在本例中是loadqaddq%rax)?
我在这里的目标是对这些东西可能如何工作有一个非常高层次的理解。

jogvjijk

jogvjijk1#

是的,存在许多独立的短3指令相关性链,每个链在一次迭代中从load(2)开始,在下一次迭代中以store(1)结束。
但是除了循环计数器之外,没有“循环承载”依赖链;该3指令dep链在它们下次执行时不耦合回到这些指令中的任何指令的输入依赖性。load(2)打破了对RAX的旧值的依赖性,因此这是另一个短dep链的开始,而不是上次运行时开始的链的延续。
如果add $1, %raxadd %rax, %rdi或其他一些指令,使得下一个加载地址依赖于前一个加载地址,那么它将是循环进位的。在这种情况下,只有存储将在每次迭代中“分叉”。就像 * 为什么一行代码会使性能下降10倍?* 中的随机内存访问微基准测试一样。
因此,一个广泛无序的exec CPU可以有任意数量的dep链并行运行,使它们的延迟重叠。
事实上,Sandybridge和以后的版本应该能够以每时钟1次迭代的速度运行这个循环,由于sub/jnz的宏融合,前端和后端都可以运行4个uop。冰湖的5宽前端不会运行它任何更快。
uiCA can simulate it on Haswell以了解这些指令将如何真正通过实际管线的实际前端和后端,假设所有加载和存储命中L1 d高速缓存并且不混叠。(通过逆向工程尽可能精确地模拟前端行为和循环的uop调度。它不模拟缓存。)该链接显示Haswell每次迭代维持1.0个循环。trace table visualization展开循环迭代,并显示每个指令从前端发到后端的周期,以及它何时被分派到执行单元、何时完成执行、何时退休。(如果跟踪表链接失效,则使用第一个链接通过从源重新分析来重新生成它;asm源是第一个链接的URL的一部分。)
非跟踪输出如下所示。(LSD =循环缓冲器,MITE=传统解码,DSB=微指令高速缓存,MS=微代码定序器。这里所有的微指令都来自“锁定它们”的循环缓冲器。发布与执行是融合域微指令与未融合。IntelCPU将存储解码为单独的存储地址微指令和存储数据微指令,微融合为一个前端微指令,该前端微指令在后端作为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/时钟上跟上这个环路;AMD只将testcmpjcc融合在一起,而不是同时修改整数寄存器的指令,因此发布/重命名需要5个uop。但Zen的前端是5个指令/ 6个uop宽,因此其前端带宽只能勉强跟上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/clock FP FMA/穆尔,但有1/clock FP add,延迟与Haswell匹配。例如,* Latency bounds and throughput bounds for processors for operations that must occur in sequence * 还注意每次迭代如何读取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/)。
也可能通过重新排序缓冲区(ROB)容量。Haswell的ROB大小为192微指令。存储不写寄存器,因此通过一些非常简单的近似,循环中只有3/4的微指令需要为它们的输出分配物理寄存器。168个PRF条目中已经需要超过16个来保持体系结构状态(包括您没有修改的寄存器值),但是作为一个粗略的计算,用192个微指令填充ROB也会使用192 * 3/4 = 144个物理寄存器文件条目。
有关此类真实实验,请参见https://blog.stuffedcow.net/2013/05/measuring-rob-capacity/
调度器大小(RS =保留站)是一个明显更小的限制,在Haswell中只有60个微指令。它跟踪未执行的微指令(在Sandybridge-family的未融合域中,因此存储占用2个插槽),而ROB跟踪未 * 退休 * 的微指令。
请参见Understanding the impact of lfence on a loop with two long dependency chains, for increasing lengths:RS大小对重叠长dep链的影响。

对于更宽的前端,填充RS的未执行微指令将主要是每时钟1个sub $1, %rdx + jnz微指令(从sub-branch的宏融合到端口6的单个微指令,因为它是预测执行的),以及存储数据微指令(在Haswell上也限于1/时钟,不像存储地址,它可以在这种简单寻址模式的p2/p3/p7中的任何一个上运行)。
加载与加法微指令可以执行并释放它们的RS条目(平均每个周期超过1个),等待所有较早的指令执行完毕后从ROB中退出。
如果您在uiCA上为更宽的CPU(如Ice Lake)模拟这段代码,请注意,当您向下滚动跟踪时,发出和收回之间的周期数不断增加。与Haswell不同,前端确实远远领先于后端。(Ice Lake具有2/时钟的存储吞吐量,包括存储数据,因此只有延迟瓶颈将备份那些子/时钟微操作。除此之外,看起来像是Haswell后端的前端更宽。当然,Ice Lake的ROB、RS和PRF比Haswell更大。)
还涉及:

相关问题