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 之间的各种有趣的性能计数器(每次迭代)。请注意,所有实验的迭代次数都是恒定的。只有缓冲区大小会更改以适应指定的步幅。此外,仅计算用户模式性能事件。

在此处输入图像描述

这里唯一奇怪的是退休的微指令的数量随着步伐的增加而增加。对于步幅 128,它从每次迭代 3 微秒(如预期)到 11 微秒。这是为什么呢?

如下图所示,步幅越大,事情就越奇怪。在此图中,步幅范围从 32 到 8192,增量为 32 字节。首先,退出指令的数量以 4096 字节的步幅从 4 线性增加到 5,之后它保持不变。加载 uops 的数量从 1 增加到 3,并且每次迭代的 L1D 加载命中数保持 1。对于我来说,只有 L1D 加载未命中的数量才有意义。

在此处输入图像描述

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

  • 执行时间增加,因此会发生更多的硬件中断。但是,我正在计算用户模式事件,因此中断不应干扰我的测量。我还用tasksetor重复了所有实验,nice并得到了相同的结果。
  • 页面遍历和页面错误的数量增加。(我已经验证了这一点,但为了简洁起见,我将省略这些图表。)页面错误由内核在内核模式下处理。根据这个答案,页面遍历是使用专用硬件(在 Haswell 上?)实现的。尽管答案所基于的链接已失效。

为了进一步研究,下图显示了微码辅助的微指令数。与其他性能事件一样,每次迭代的微码辅助 uops 数量会增加,直到在步幅 4096 处达到最大值。对于所有步幅,每个 4K 虚拟页面的微码辅助 uops 数量为 506。“额外的 uops”线绘制了退役 uops 的数量减去 3(每次迭代的预期 uops 数量)。

在此处输入图像描述

该图显示,对于所有步幅,额外微码数略大于微码辅助微码数的一半。我不知道这意味着什么,但它可能与页面漫游有关,并且可能是观察到扰动的原因。

为什么即使每次迭代的静态指令数量相同,每次迭代的退役指令和微指令的数量也会随着更大的步幅而增加?干扰来自哪里?


下图绘制了每次迭代的周期数与每次迭代不同步幅的退役微指令数。周期数的增加速度远快于退役的微指令数。通过使用线性回归,我发现:

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

取两个函数的导数:

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

这意味着周期数增加 0.1773,退休的微指令数增加 0.0672,步幅每增加 1 个字节。如果中断和页面错误确实是扰动的(唯一)原因,那么这两种速率不应该非常接近吗?

在此处输入图像描述

在此处输入图像描述

4

2 回答 2

7

您在许多性能计数器中反复看到的效果,其中值线性增加,直到步幅 4096 之后它保持不变,如果您假设该效果纯粹是由于随着步幅的增加而增加页面错误,则完全有意义。页面错误会影响观察到的值,因为在存在中断、页面错误等情况下,许多计数器并不准确。

例如,instructions当您从步幅 0 前进到 4096 时,计数器从 4 变为 5。我们从其他来源知道,Haswell 上的每个页面错误都会在用户模式下计算一条额外指令(在内核模式下也会额外计算一条指令) .

因此,我们期望的指令数是循环中 4 条指令的基数,加上基于每个循环发生多少页错误的指令的一部分。如果我们假设每个新的 4 KiB 页面都会导致页面错误,那么每次迭代的页面错误数为:

MIN(OFFSET / 4096, 1)

由于每个页面错误都会计算一条额外的指令,因此我们有预期的指令计数:

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

这与您的图表完全一致。

因此,一次为所有计数器解释了斜率图形的粗略形状:斜率仅取决于每个页面错误的过度计数量。那么剩下的唯一问题是为什么页面错误会以您确定的方式影响每个计数器。我们已经介绍过instructions,但让我们看看其他的:

MEM_LOAD_UOPS.L1_MISS

每页只有 1 次未命中,因为只有触及下一页的负载才会丢失任何内容(它需要出错)。我实际上并不同意 L1 预取器不会导致其他未命中:我认为如果您关闭预取器,您会得到相同的结果。我认为您不会再有 L1 未命中,因为相同的物理页面支持每个虚拟页面,并且一旦您添加了 TLB 条目,所有行都已经在 L1 中(第一次迭代将丢失 - 但我猜您正在进行多次迭代)。

MEM_UOPS_RETIRED.ALL_LOADS

这显示每个页面错误 3 uops(2 额外)。

我不是 100% 确定这个事件在 uop 重放的情况下是如何工作的。它是否总是根据指令计算固定数量的微指令,例如,您在 Agner 的指令 -> 微指令表中看到的数字?或者它是否计算代表指令发送的实际微指令数?这通常是相同的,但是当它们在不同的缓存级别丢失时,加载重放它们的微指令。

例如,我发现在 Haswell 和 Skylake 2上,当 L1 中的负载丢失但在 L2 中命中时,您会看到负载端口(端口 2 和端口 3)之间总共有 2 个微指令。据推测,发生的情况是 uop 是在假设它将在 L1 中命中的情况下分派的,并且当这没有发生时(当调度程序预期它时结果还没有准备好),它会以预计 L2 命中的新时间来重放。这是“轻量级”的,因为它不需要任何类型的管道清除,因为没有执行错误路径指令。

同样,对于 L3 未命中,我观察到每次负载 3 uops。

鉴于此,假设新页面上的未命中导致加载 uop 被重播两次(正如我所观察到的)似乎是合理的,并且这些 uop 出现在MEM_UOPS_RETIRED计数器中。有人可能会合理地争辩说,重放的微指令没有退役,但在某种意义上,退役与指令的关联比微指令更重要。也许这个计数器可以更好地描述为“与退役加载指令相关的调度微指令”。

UOPS_RETIRED.ALLIDQ.MS_UOPS

剩下的奇怪之处是与每个页面相关的大量微指令。这似乎完全有可能与页面错误机制有关。您可以尝试在 TLB 中遗漏的类似测试,但不会出现页面错误(确保页面已经填充,例如,使用mmapwith MAP_POPULATE)。

MS_UOPS和之间的区别UOPS_RETIRED似乎并不奇怪,因为有些微指令可能不会退役。也许他们也算在不同的域中(我忘了UOPS_RETIRED是融合域还是非融合域)。

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

循环与 uop 导数

在您问题的最后一部分中,您表明周期与偏移的“斜率”比退役 uops 与偏移的斜率大约 2.6 倍。

如上所述,这里的效果在 4096 处停止,我们再次预计这种效果完全是由于页面错误造成的。所以斜率的差异仅仅意味着页面错误的周期是 uops 的 2.6 倍。

你说:

如果中断和页面错误确实是扰动的(唯一)原因,那么这两种速率不应该非常接近吗?

我不明白为什么。微指令和周期之间的关系可能相差很大,可能相差三个数量级:CPU 可能每个周期执行四个微指令,或者执行单个微指令可能需要 100 秒的周期(例如缓存缺失加载)。

每 uop 2.6 个周期的值正好在这个大范围的中间,我并不觉得奇怪:它有点高(如果您在谈论优化的应用程序代码,“效率低下”)但这里我们正在谈论页面故障处理是完全不同的事情,所以我们预计会有很长的延迟。

过度计数的研究

由于页面错误和其他事件而对过度计数感兴趣的任何人都可能对这个 github 存储库感兴趣,该存储库对各种 PMU 事件的“确定性”进行了详尽的测试,并且已经注意到许多这种性质的结果,包括在 Haswell 上。然而,它并没有涵盖哈迪在这里提到的所有计数器(否则我们已经有了答案)。这是相关的论文和一些更易于使用的相关幻灯片- 他们特别提到每个页面错误都会产生一个额外的指令。

以下是英特尔结果的引述:

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. 

因此,您期望每个页面错误都有一条额外的指令(特别是分支指令)。


1 在许多情况下,这种“不精确性”仍然是确定性的——因为在存在外部事件的情况下,过度计数或计数不足总是以相同的方式表现,因此如果您还跟踪有多少相关事件已经发生。

2我并不是要把它限制在这两种微架构上:它们恰好是我测试过的那种。

于 2018-09-27T00:11:32.867 回答
2

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

通过查看代码很容易看出执行一次迭代需要 3 微秒。最初的几次加载可能会在 L1 缓存中丢失,但随后所有的加载都将在缓存中命中,因为所有虚拟页面都映射到同一个物理页面,并且英特尔处理器中的 L1 被物理标记和索引。所以3微秒。现在考虑UOPS_RETIRED.ALL性能事件,它在 uop 退出时发生。我们希望看到3 * number of iterations这样的事件。执行期间发生的硬件中断和页面错误需要微码辅助来处理,这可能会扰乱性能事件。因此,对于性能事件 X 的特定度量,每个计数事件的来源可以是:

  • 正在分析的代码的指令。我们称之为 X 1
  • Uops 用于引发由于正在分析的代码尝试访问内存而发生的页面错误。我们称之为 X 2
  • 由于异步硬件中断或引发软件异常,Uops 用于调用中断处理程序。我们称之为 X 3

因此,X = X 1 +X 2 + X 3

由于代码很简单,我们能够通过静态分析确定 X 1 = 3。但我们对 X 2和 X 3一无所知,这可能不是每次迭代的常数。UOPS_RETIRED.ALL我们可以使用来测量 X。幸运的是,对于我们的代码,页面错误的数量遵循一个常规模式:每页访问恰好一个(可以使用perf)。可以合理地假设引发每个页面错误都需要相同数量的工作,因此每次都会对 X 产生相同的影响。请注意,这与每次迭代的页面错误数相反,对于不同的加载步幅,这是不同的。作为执行每页访问的循环的直接结果而引退的微指令数是恒定的。我们的代码不会引发任何软件异常,因此我们不必担心它们。硬件中断怎么办?好吧,在 Linux 上,只要我们在未分配处理鼠标/键盘中断的内核上运行代码,唯一真正重要的中断就是本地 APIC 计时器。幸运的是,这种中断也经常发生。只要每页花费的时间量相同,定时器中断对 X 的影响将是每页恒定的。

我们可以将前面的等式简化为:

X = X 1 + X 4

因此,对于所有负载步幅,

(每页 X)-(每页 X 1)=(每页 X 4)= 常数。

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

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)

请注意,一般来说,我们不知道或不确定我们感兴趣的性能事件,这就是我们需要测量它的原因。退休的微商的案例很容易。但总的来说,这是我们需要通过实验来发现或验证的。本质上,exp是性能事件的计数,ec但不包括引发页面错误和中断的事件。

基于上述论点和假设,我们可以推导出以下等式:

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

这里有两个未知数:常数C和我们感兴趣的值exp。所以我们需要两个方程来计算未知数。由于该等式适用于所有步幅,因此我们可以对两个不同的步幅使用测量值:

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

我们可以找到exp

(ec 1 - exp*iter)/np 1 = (ec 2 - exp*iter)/np 2
ec 1 *np 2 - exp*iter*np 2 = ec 2 *np 1 - exp*iter*np 1
ec 1 *np 2 - ec 2 *np 1 = exp*iter*np 2 - exp*iter*np 1
ec 1 *np 2 - ec 2 *np 1 = exp*iter*(np 2 - np 1 )

因此,

exp = (ec 1 *np 2 - ec 2 *np 1 )/(iter*(np 2 - np 1 ))

让我们将此等式应用于UOPS_RETIRED.ALL

步幅1 = 32
iter = 1000 万
np 1 = 1000 万 * 32 / 4096 = 78125
ec 1 = 51410801

步幅2 = 64
iter = 1000 万
np 2 = 1000 万 * 64 / 4096 = 156250
ec 2 = 72883662

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

好的!非常接近每次迭代预期的 3 个退役微指令。

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.ROBRESOURCE_STALLS.RS是零。只有RESOURCE_STALLS.ANY在这里很重要。借助不同步幅的方程exp和实验结果,我们可以计算exp.

步幅1 = 32
iter = 1000 万
np 1 = 1000 万 * 32 / 4096 = 78125
ec 1 = 9207261

步幅2 = 64
iter = 1000 万
np 2 = 1000 万 * 64 / 4096 = 156250
ec 2 = 16111308

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

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

我计算C了所有的步幅。嗯,它看起来并不固定。也许我们应该使用不同的步幅?尝试没有坏处。

步幅1 = 32
iter 1 = 1000 万
np 1 = 1000 万 * 32 / 4096 = 78125
ec 1 = 9207261

步幅2 = 4096
iter 2 = 100 万
np 2 = 100 万 * 4096 / 4096 = 1m
ec 2 = 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可以像退休的指令计数器一样进行更正,但我没有调查这两个。

于 2018-09-27T19:10:08.067 回答