为什么流式加载的步幅越大，每次迭代中的uops数量就会增加？

Question

为什么流式加载的步幅越大，每次迭代中的uops数量就会增加？

9

考虑以下循环：

.loop:
    add     rsi, OFFSET    
    mov     eax, dword [rsi]
    dec     ebp
    jg .loop

其中OFFSET是一个非负整数，rsi包含指向在bss部分定义的缓冲区的指针。这个循环是代码中唯一的循环。也就是说，在循环之前它没有被初始化或触及。在Linux上，假定缓冲区的所有4K虚拟页面将按需映射到同一个物理页面。因此，缓冲区大小的唯一限制是虚拟页面的数量。因此，我们可以轻松地尝试使用非常大的缓冲区。

该循环由4个指令组成。在Haswell上，每个指令都会解码为融合和非融合域中的单个uop。在连续的add rsi, OFFSET实例之间还存在一个循环相关依赖关系。因此，在空闲条件下，其中负载始终命中L1D时，循环应以大约每次迭代1个周期的速度执行。对于小的偏移量（步幅），这得益于基于IP的L1流预取器和L2流预取器。但是，两个预取器只能在4K页面内进行预取，L1预取器支持的最大步幅为2K。因此，对于小的步幅，每4K页应有约1个L1未命中。随着步幅的增加，L1未命中和TLB未命中的总数将增加，性能将相应恶化。

下图显示了各种步幅（0到128）的各种有趣的性能计数器（每次迭代）。请注意，所有实验的迭代次数都是恒定的。仅更改缓冲区大小以适应指定的步幅。此外，仅计算用户模式性能事件。

这里唯一奇怪的是随着步幅增加，退役uops的数量也在增加。它从每次迭代的3个uops（如预期）增加到128步幅的11个uops。为什么会这样？

随着步幅变大，情况变得更加奇怪，如下图所示。在这张图中，步幅范围从32到8192，每次增加32字节。首先，随着步幅从4到4096字节的线性增加，已退休指令的数量增加了从4到5，之后保持不变。加载uops的数量从1增加到3，每次迭代的L1D加载命中数量保持为1。对我来说，所有步幅的L1D加载缺失数量是有意义的。

较大步幅的两个明显影响是：

执行时间会增加，因此会发生更多硬件中断。但是，我计算用户模式事件，因此中断不应干扰我的测量。我还使用了 taskset 或 nice 重复了所有实验，并获得了相同的结果。
页面行走和页面故障的数量增加。（我已经验证过了，但出于简洁起见，我将省略图表。）页面故障由内核在内核模式下处理。根据 this 的答案，页面行走是使用专用硬件实现的（在 Haswell 上？）。尽管答案所依据的链接已经失效了。

为了进一步研究，下面的图表显示了来自微码协助的 uops 数量。每次迭代的微码协助 uops 数量会增加，直到步幅达到 4096 时达到最大值，就像其他性能事件一样。每个 4K 虚拟页面的微码协助 uops 数量为 506。"Extra UOPS" 行绘制了退役 uops 减去 3（每次迭代预期 uops 数量）的数量。

图表显示，对于所有步幅而言，额外uops的数量略大于微代码辅助uops的一半。我不知道这是什么意思，但它可能与页面遍历有关，并可能是观察到的扰动的原因。

尽管每次迭代中静态指令的数量相同，但随着步幅增加，已退休指令和uops的数量逐渐增加。这是由什么干扰引起的？

以下图表显示了不同步幅下每次迭代的循环次数与每次迭代的已退休uop数量之间的关系。循环次数增加得比已退役uop数量快得多。通过使用线性回归，我发现：

cycles = 0.1773 * stride + 0.8521
uops = 0.0672 * stride + 2.9277

对两个函数分别求导：

d(cycles)/d(stride) = 0.1773
d(uops)/d(stride) = 0.0672

这意味着，步长每增加1字节，循环次数增加0.1773，退休uops数量增加0.0672。如果中断和页面故障确实是扰动的唯一原因，那么这两个比率不应该非常接近吗？

- Hadi Brais

1

是的，自P6以来，页面行走使用专用硬件，而不是微代码uops。@Bee说L1缺失会“成本”执行额外的uop，显然它们会被重播或其他什么。[AVX 512改进？]（https://stackoverflow.com/posts/comments/91993393）。 - Peter Cordes

2

关于回放，对于每个缓存级别的缺失，似乎会有一个额外的p23 uop。也就是说，在L1命中时是1个uop，在L2命中时是2个uops，在L3命中时是3个uops（也许到这里就停止了）。我认为可能发生的是调度程序总是很乐观：它不知道你会在哪个缓存级别命中，因此在每次机会时都会按照最佳命中时间唤醒依赖操作：L1的4/5个周期，L2的12个周期，等等。因此，每次缺失都会得到一个额外的uop。还有其他情况会产生大量的uop，例如如果4个周期的快速路径失败。 - BeeOnRope

2

在Linux上，当页面故障发生时，如果它们是驻留的，操作系统可能会更新附近页面（在我的系统上为15个额外页面）的页面表。这意味着由于每个故障实际上都添加了16个页面，因此我的系统上的页面故障减少了16倍。这适用于文件支持的页面，但对于bss可能不适用，因为它是特殊的（隐式映射零页面或类似内容）。 - BeeOnRope

1

@BeeOnRope 那很有道理。引发实际页面错误需要微码协助。在这种情况下，结果表明引发页面错误需要506个uops。 - Hadi Brais

2

@PeterCordes和Hadi - 关于重放问题的最新更新 - 在进一步检查后，我发现了问题所在：通常是_依赖_操作会被重新执行，这就是为什么插入一些ALU操作可以防止我看到它（因为我没有查看p0156 uops）。所以基本上当一个load输入到另一个load时，只会重新执行load，因为它是唯一的依赖操作。如果之后有ALU操作，则将重新执行ALU操作。有时候会重播超过一个uop，包括非直接依赖的操作，看起来会重放在load执行的一个周期内的uops。 - BeeOnRope

显示剩余15条评论

2个回答

2

我认为@BeeOnRope的答案完全回答了我的问题。基于@BeeOnRope的答案和评论，我想在这里添加一些额外的细节。特别是，我将展示如何确定性能事件是否在所有负载步幅中每次迭代发生固定次数。

通过查看代码，很容易看出执行单个迭代需要3个微操作。前几次加载可能会错过L1缓存，但之后的所有加载都会命中缓存，因为所有虚拟页面都映射到同一个物理页面，而Intel处理器中的L1是物理标记和索引。所以是3个微操作。现在考虑UOPS_RETIRED.ALL性能事件，当微操作退役时会发生此事件。我们预计会看到大约3 * 迭代次数的这种事件。执行期间发生的硬件中断和页面故障需要微码辅助来处理，这可能会扰动性能事件。因此，对于性能事件X的特定测量，每个计数事件的来源可能是：

被分析代码的指令。让我们称其为X₁。
用于引发由被分析代码尝试的内存访问引起的页面故障的微操作。让我们称其为X₂。
用于调用中断处理程序的微操作，由于异步硬件中断或引发软件异常。让我们称其为X₃。

因此，X = X₁ +X₂ + X₃。

由于代码很简单，我们能够通过静态分析确定X₁ = 3。但是我们对X₂和X₃一无所知，它们可能不是每次迭代都恒定不变的。但是我们可以使用UOPS_RETIRED.ALL来测量X。幸运的是，对于我们的代码，页面故障的数量遵循正常模式：每个访问的页面恰好一个（可以使用perf进行验证）。合理地假设引发每个页面故障所需的工作量相同，因此每次都会对X产生相同的影响。请注意，这与每个迭代的页面故障数不同，对于不同的负载步幅也不同。每个访问的页面上直接由于执行循环而退役的微操作数量是恒定的。我们的代码不会引发任何软件异常，因此我们不必担心它们。那硬件中断呢？嗯，在Linux上，只要我们在未分配给处理鼠标/键盘中断的核心上运行代码，那么真正重要的中断就是本地APIC计时器。幸运的是，这个中断也会定期发生。只要每个页面花费的时间相同，计时器中断对X的影响将在每个页面上恒定。

我们可以简化前面的等式：

X = X₁ + X₄.

因此，对于所有的负载步长，

(每页X) - (每页X₁) = (每页X₄) = 常数。

现在我将讨论为什么这很有用，并提供使用不同性能事件的示例。我们需要以下符号：

ec = total number of performance events (measured)
np = total number of virtual memory mappings used = minor page faults + major page faults (measured)
exp = expected number of performance events per iteration *on average* (unknown)
iter = total number of iterations. (statically known)

请注意，通常情况下，我们不知道或不确定我们感兴趣的性能事件，这就是为什么我们需要进行测量的原因。退休的uops的情况很容易解决。但总的来说，这就是我们需要实验性地找出或验证的内容。本质上，exp是性能事件ec的计数，但不包括那些由于页面故障和中断而引起的事件。

基于上述论点和假设，我们可以得出以下方程式：

C = (ec/np) - (exp*iter/np) = (ec - exp*iter)/np

这里有两个未知数：常数C和我们感兴趣的值exp。因此，我们需要两个方程才能计算出这些未知量。由于该方程对所有步幅都成立，我们可以使用两个不同步幅的测量值：

C = (ec₁ - exp*iter)/np₁ C = (ec₂ - exp*iter)/np₂ 我们可以找到exp：

(ec₁ - exp*iter)/np₁ = (ec₂ - exp*iter)/np₂ ec₁*np₂ - exp*iter*np₂ = ec₂*np₁ - exp*iter*np₁ ec₁*np₂ - ec₂*np₁ = exp*iter*np₂ - exp*iter*np₁ ec₁*np₂ - ec₂*np₁ = exp*iter*(np₂ - np₁)

因此，

exp = (ec₁*np₂ - ec₂*np₁)/(iter*(np₂ - np₁))

让我们将此方程应用于UOPS_RETIRED.ALL。

stride₁ = 32 iter = 1000万 np₁ = 1000万 * 32 / 4096 = 78125 ec₁ = 51410801

stride₂ = 64 iter = 1000万 np₂ = 1000万 * 64 / 4096 = 156250 ec₂ = 72883662

exp = (51410801*156250 - 72883662*78125)/(10m*(156250 - 78125)) = 2.99

很好！非常接近预期的每次迭代3个已退役uops。

C = (51410801 - 2.99*10m)/78125 = 275.3

我已经计算出所有步幅的C。它不是一个完全的常数，但对于所有步幅来说，它都是275+-1。

exp可以类似地推导其他性能事件:

MEM_LOAD_UOPS_RETIRED.L1_MISS: exp = 0
MEM_LOAD_UOPS_RETIRED.L1_HIT: exp = 1
MEM_UOPS_RETIRED.ALL_LOADS: exp = 1
UOPS_RETIRED.RETIRE_SLOTS: exp = 3

那么这对所有性能事件都适用吗？嗯，让我们尝试一些不太明显的东西。例如考虑 RESOURCE_STALLS.ANY，它测量了任何原因造成的分配器停顿周期。仅仅通过查看代码很难确定应该有多少 exp。注意到对于我们的代码，RESOURCE_STALLS.ROB和RESOURCE_STALLS.RS为零。只有RESOURCE_STALLS.ANY在这里是显著的。利用exp的方程和不同步长的实验结果，我们可以计算exp。

步长₁ = 32
迭代次数 = 1000万
np₁ = 1000万 * 32 / 4096 = 78125
ec₁ = 9207261

步长₂ = 64
迭代次数 = 1000万
np₂ = 1000万 * 64 / 4096 = 156250
ec₂ = 16111308

exp = (9207261*156250 - 16111308*78125)/(10m*(156250 - 78125)) = 0.23

C = (9207261 - 0.23*10m)/78125 = 88.4

我已经为所有步长计算了C。看起来它并不是常数。也许我们应该使用不同的步长？试试也无妨。

步长₁ = 32
迭代次数₁ = 1000万
np₁ = 1000万 * 32 / 4096 = 78125
ec₁ = 9207261

步长₂ = 4096
迭代次数₂ = 100万
np₂ = 100万 * 4096 / 4096 = 100万
ec₂ = 102563371

exp = (9207261*1m - 102563371*78125)/(1m*1m - 10m*78125))
= 0.01

C = (9207261 - 0.23*10m)/78125 = 88.4

(请注意，这次我使用了不同数量的迭代，只是为了展示您可以这样做。)

我们得到了一个不同的值exp。我已经为所有步幅计算了C，它仍然看起来不是常数，如下图所示。对于较小的步幅，它变化明显，2048之后略微变化。这意味着有一个或多个假设，即每页固定数量的分配器停顿周期无效。换句话说，不同步幅的分配器停顿周期的标准差是显著的。

对于UOPS_RETIRED.STALL_CYCLES性能事件，exp = -0.32，标准差也很显著。这意味着有一个或多个假设，即每页固定数量的退役停顿周期无效。

我开发了一种简单的方法来纠正测量到的退役指令数。 每个触发的页面错误将向已退休指令计数器添加一个额外的事件。例如，假设页面错误在固定的迭代次数后定期发生，比如2次。也就是说，每两次迭代触发一次故障。当步幅为2048时，这在问题代码中发生。由于我们希望每次迭代有4条指令退役，因此直到发生页面错误的预期退役指令总数为4*2 = 8。由于页面错误会向已退役指令计数器添加一个额外的事件，因此它将被测量为9而不是8。也就是说，每次迭代4.5。当我实际测量2048步幅案例的退役指令计数时，它非常接近4.5。在所有情况下，当我应用此方法静态预测每次迭代测量到的已退役指令的值时，误差始终小于1％。尽管存在硬件中断，但这非常精确。我认为只要总执行时间少于50亿个核心周期，硬件中断就不会对已退役指令计数器产生任何重大影响。（我的每个实验都不超过50亿个周期，这就是为什么。）但是，如上所述，必须始终注意故障发生的次数。

如上所述，有许多性能计数器可以通过计算每页值来进行校正。另一方面，退役指令计数器可以通过考虑获取页面错误的迭代次数来进行校正。RESOURCE_STALLS.ANY和UOPS_RETIRED.STALL_CYCLES也可能类似于退役指令计数器进行校正，但我还没有调查过这两个计数器。

- Hadi Brais

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BeeOnRope · Accepted Answer

您多次在许多性能计数器中看到的效果，即值在步长 4096 之前呈线性增长，之后保持恒定，如果假定该效果纯粹是由于随着步长的增加导致页面错误增加，则完全合理。页面错误会影响观察到的值，因为许多计数器在中断、页面错误等情况下不精确。

例如，以从步长 0 到 4096 时从 4 增至 5 的 instructions 计数器为例。我们从其他来源知道，Haswell 上每个页面错误将在用户模式下计算一个额外的指令（在内核模式下也会计算一个额外的指令）。

因此，我们期望的指令数是循环中的 4 条指令基础上加上一些指令的分数，该分数基于我们每次执行的页面错误数。如果我们假设每个新的 4 KiB 页面都会导致一个页面错误，则迭代中的页面错误数为：

MIN(OFFSET / 4096, 1)

由于每个页面错误都计算了一条额外的指令，因此我们对于预期指令计数有：

4 + 1 * MIN(OFFSET / 4096, 1)

这与你的图表完全一致。

因此，所有计数器的倾斜图的大致形状都可以同时解释：其倾斜程度仅取决于每个页面故障的过度计数量。那么唯一剩下的问题是为什么页面故障会以你确定的方式影响每个计数器。我们已经讨论了指令，但让我们来看看其他的内容：

MEM_LOAD_UOPS.L1_MISS

每页只有1个缺失是因为只有接触下一页的负载才会错过任何东西（它会出现错误）。我并不认为是L1预取器导致没有其他缺失：我认为如果关闭预取器，您将获得相同的结果。我认为之所以没有更多的L1缺失，是因为相同的物理页面支持每个虚拟页面，一旦添加了TLB条目，所有线路都已经在L1中（第一次迭代将错过-但我猜您正在进行多次迭代）。

MEM_UOPS_RETIRED.ALL_LOADS

这显示每个页面错误有3个uops（2个额外的）。

我不确定在uop重放存在的情况下该事件如何工作。它是否始终根据指令计算固定数量的uops，例如您在Agner的指令-> uop表中看到的数量？还是它计算代表指令调度的实际uop数量？这通常是相同的，但当加载在各种缓存级别上错过时，它们会重播其uop。

例如，我发现在Haswell和Skylake ²上，当负载在L1中错过但在L2中命中时，在负载端口（port2和port3）之间总共看到2个uops。可能发生的情况是，uop被分派并假定它将在L1中命中，当这种情况没有发生时（当调度程序期望结果时未准备好），它会重新播放，并预计L2命中的新时间。这是“轻量级”的，因为它不需要任何类型的管道清除，因为没有执行错误路径指令。

类似地，对于L3错误，我观察到每个负载3个uops。

鉴于此，假设新页面上的错误导致加载 uop 被重放了两次（正如我所观察到的那样），这似乎是合理的，并且这些 uops 出现在 MEM_UOPS_RETIRED 计数器中。人们可以合理地认为，重播的 uops 没有退役，但在某种程度上，退役更与指令相关而不是 uops。也许这个计数器最好描述为“与退役负载指令相关的分派 uops”。

UOPS_RETIRED.ALL 和 IDQ.MS_UOPS

剩下的奇怪之处就是与每个页面关联的大量 uops。这似乎完全可能与页面错误机制有关。您可以尝试类似的测试，其中 TLB 错失，但不会发生页面错误（确保页面已经填充，例如使用带有 MAP_POPULATE 的 mmap）。

MS_UOPS 和 UOPS_RETIRED 之间的差异似乎并不奇怪，因为一些 uops 可能没有退役。也许它们在不同的域中计数（我忘记了 UOPS_RETIRED 是融合还是未融合域）。

在这种情况下，用户模式计数和内核模式计数之间也可能存在泄漏。

循环次数与微操作导数

在您问题的最后部分，您展示了“循环次数与偏移量”的“斜率”大约比退役的微操作与偏移量的斜率大约多2.6倍。

与上面一样，这种影响在4096处停止，我们再次预计这种影响完全是由于页面错误引起的。因此，斜率的差异只意味着页面错误的成本比微操作多花费2.6倍的周期。

您说：

“如果中断和页面错误确实是扰动的（唯一）原因，那么两个速率不应该非常接近吗？”

我不知道为什么会这样。微操作和周期之间的关系可能会有很大的变化，可能相差三个数量级：CPU可能每个周期执行四个微操作，或者可能需要100个周期才能执行单个微操作（例如缺失缓存的加载）。

每个微操作2.6个周期的值位于这个大范围的中间，并不让我感到奇怪：它有点高（如果您谈论优化的应用程序代码，则为“低效”），但是在这里，我们谈论的是页面错误处理，这是完全不同的事情，因此我们预计会有长时间的延迟。

研究过度计数

对于由于页面故障和其他事件而导致的过度计数感兴趣的任何人，可能会对这个Github存储库感兴趣，其中详尽地测试了各种PMU事件的“确定性”，并记录了许多这样的结果，包括在Haswell上。然而，它并未涵盖Hadi在此处提到的所有计数器（否则我们已经有了答案）。这是相关论文和一些更易消化的相关幻灯片 - 特别提到每次页面故障会产生一个额外的指令。

这里是来自Intel的结果引用：

Conclusions on the event determinism:
1.  BR_INST_RETIRED.ALL (0x04C4)
a.  Near branch (no code segment change): Vince tested 
    BR_INST_RETIRED.CONDITIONAL and concluded it as deterministic. 
    We verified that this applies to the near branch event by using 
    BR_INST_RETIRED.ALL - BR_INST_RETIRED.FAR_BRANCHES.
b.  Far branch (with code segment change): BR_INST_RETIRED.FAR_BRANCHES 
    counts interrupts and page-faults. In particular, for all ring 
    (OS and user) levels the event counts 2 for each interrupt or 
    page-fault, which occurs on interrupt/fault entry and exit (IRET).
    For Ring 3 (user) level,  the counter counts 1 for the interrupt/fault
    exit. Subtracting the interrupts and faults (PerfMon event 0x01cb and
    Linux Perf event - faults), BR_INST_RETIRED.FAR_BRANCHES remains a 
    constant of 2 for all the 17 tests by Perf (the 2 count appears coming
    from the Linux Perf for counter enabling and disabling). 
Consequently, BR_INST_RETIRED.FAR_BRANCHES is deterministic.

所以你期望每次页面错误会多出一条指令（特别是跳转指令）。

在许多情况下，“不精确性”仍然是“确定性的” - 即在外部事件存在时，过度计数或低估始终以相同方式行事，因此如果您还跟踪了发生的相关事件数量，则可以进行更正。

我并不是要将其限制在这两种微体系结构上：它们只是我测试过的其中两种。