（非）确定性CPU行为及对（物理）执行时间的推理

Question

过去我曾经处理过时间关键的软件开发。这些应用程序的开发基本上是这样进行的:“让我们编写代码，测试延迟和抖动，并优化两者，直到它们在可接受的范围内。” 我觉得这非常令人沮丧；这不是我所说的合适的工程，我想做得更好。

所以我研究了一个问题:为什么我们会有抖动？当然，答案是:

缓存:从主存中获取代码或数据比从L1缓存中获取相同的数据需要多出2个数量级的时间。因此，物理执行时间取决于缓存中的内容。而这又取决于几个因素:

应用程序的代码和数据布局:我们都知道可怕的行对列主矩阵遍历示例

CPU的缓存策略，包括缓存行的推测性预取

同一核心上的其他进程正在执行任务

分支预测:CPU试图猜测哪个条件跳转的分支将被执行。即使相同的条件跳转被执行两次，预测也可能不同，因此有时会形成“流水线气泡”，有时则不会。

中断:异步行为显然会导致抖动

频率缩放：在实时系统中已经禁用

这是很多可以干扰代码行为的东西。尽管如此:如果我有两个指令，位于同一个缓存行上，不依赖任何数据，也不包含(条件)跳转。那么缓存和分支预测的抖动应该被消除了，只有中断应该起作用。对吗？好吧，我编写了一个小程序两次获取时间戳计数器(tsc)，并将差异写入stdout。我在一个rt-patched linux内核上执行它，并禁用了频率缩放。

该代码具有基于glibc的初始化和清除，调用printf，我认为有时在缓存中，有时不在。但在“rdtsc”(将tsc写入edx:eax)之间的所有内容都应该在每次执行二进制文件时都是确定性的。只是为了确保，我反汇编了elf文件，这里是两个rdtsc调用的部分:

00000000000006b0 <main>:
 6b0:   0f 31                   rdtsc  
 6b2:   48 c1 e2 20             shl    $0x20,%rdx
 6b6:   48 09 d0                or     %rdx,%rax
 6b9:   48 89 c6                mov    %rax,%rsi
 6bc:   0f 31                   rdtsc  
 6be:   48 c1 e2 20             shl    $0x20,%rdx
 6c2:   48 09 d0                or     %rdx,%rax
 6c5:   48 29 c6                sub    %rax,%rsi
 6c8:   e8 01 00 00 00          callq  6ce <print_rsi>
 6cd:   c3                      retq 

没有条件跳转，位于同一缓存行（虽然我不能百分之百确定 - ELF 加载器确切地将指令放在哪里？这里的 64 字节边界是否映射到内存中的 64 字节边界？）... 这个抖动是从哪里来的？如果我通过 zsh 执行该代码 1000 次（每次重新启动程序），我得到的值从 12 到 46 不等，并有几个中间值。由于我的内核已禁用频率缩放，因此只剩下中断。现在我愿意相信，在 1000 次执行中，会有一次被中断。但我不愿相信有 90% 被中断了（我们正在讨论 ns 级别的时间间隔！那么中断应该来自哪里呢？！）。

所以，我的问题如下：

• 为什么代码不是确定性的，即为什么每次运行都无法得到相同的数字？
• 是否可以推断出运行时间，至少对于这个非常简单的代码片段而言？我能保证运行时间的下限吗（使用工程原理，而不是测量加上希望）？
• 如果不能，那么非确定性行为的源是什么？CPU 的哪个部件（或计算机的其他部分？）在这里扔骰子？

- D. Veloper

Answer 1

一旦你消除了抖动的外部来源，CPU仍然不是完全确定性的 - 至少基于你可以控制的因素。

更重要的是，你似乎在一个模型下运行，每个指令串行执行，需要一定的时间。当然，现代的 乱序 CPU 通常会同时执行多个指令，并且通常可以重新排序指令流，使得指令在最老的未执行指令之前执行200多个或更多指令。

在这个模型中，很难准确地说出指令何时开始或结束（它是在解码、执行、退役或其他情况下），而且对于参与这种高度并行管道的“定时”指令来说，具有合理的周期精确解释是非常困难的。

由于 rdstc 不串行化管道，即使进程完全确定性，你得到的时间也可能相当随机 - 它将完全取决于管道中的其他指令等等。第二次调用 rdtsc 永远不会像第一次那样具有相同的管道状态，初始管道状态也将不同。

通常的解决方案是在发出rdstc之前发出cpuid指令，但一些改进已经讨论过。

如果您想了解一个CPU密集型代码如何运作的良好模型¹，可以通过阅读Agner Fog优化页面上的前三个指南（如果您只对汇编级别感兴趣，则跳过C++部分），以及程序员应该了解的有关内存的所有内容来实现大部分功能。后者有一个PDF版本，可能更容易阅读。

这将允许您获取一段代码并模拟其性能，而无需每次都运行它。我已经做过了，有时会得到精确的循环结果。在其他情况下，结果比模型预测的要慢，您需要深入挖掘以了解其他瓶颈 - 有时您会发现某个架构完全没有记录的东西！

如果你只是想获得短代码段的精确循环时间（或接近精确），我建议使用 libpfc，它在 x86 上可以使你用户态访问性能计数器，并在正确条件下（基本上你需要将进程固定到一个 CPU 并防止上下文切换，这似乎是你已经在做的）声称可以给出循环精确的结果。性能计数器可以比 rdstc 给出更好的结果。

最后，请注意 rdtsc 正在测量 挂钟时间，这在几乎所有现代核心上与 CPU 周期根本不同，特别是具有 DVFS 的核心。随着 CPU 减速，您所测得的表面成本将增加，反之亦然。这也会给指令本身增加一些减速，因为它必须去读取与 CPU 时钟不同的时钟域相连的计数器。

---

¹ 也就是说，受到计算、内存访问等限制的程序，而不是受到IO、用户输入、外部设备等限制的程序。

- BeeOnRope

Answer 2

加载器已将指令放置在左侧看到的地址上。我不知道缓存是在物理地址还是逻辑地址上工作的，但这并不重要，因为物理地址和逻辑地址之间映射的粒度相当粗糙（至少为4k，如果我没有记错），而且无论如何肯定是缓存行大小的倍数。因此，您可能在地址680处有一个缓存行边界，然后下一个缓存行边界位于6C0地址处，所以您很有可能与缓存行相关问题无关。

如果您的代码被中断抢占，则您的读取之一可能会偏离数百个甚至数千个周期，而不是您目睹的十多个周期。所以也不是那个原因。

除了您已经确定的因素之外，还有许多其他因素会影响读数：

- 代表另一个线程执行DMA访问 - CPU管道的状态 - CPU寄存器分配

CPU寄存器分配具有特定的兴趣，因为它提供了一个想法，即现代CPU有多么复杂，因此很难预测任何给定指令需要多少时间。您正在使用的寄存器不是真正的寄存器；它们在某种程度上是“虚拟”的。CPU包含一组通用寄存器，它将其中一些分配给您的线程，并将它们映射到您想要认为是“rax”或“rdx”的任何内容。这样的复杂性令人难以置信。

归根结底，您发现在基于x86-x64的现代桌面系统中，CPU计时实际上（不是真正的）非确定性的。这是可以预料的。

幸运的是，这些系统非常快，几乎从不影响使用。当确实需要时，我们不使用桌面系统，而使用嵌入式系统。

对于那些有预测指令执行时间学术需求的人来说，有模拟器可以根据书本上每个仿真指令所需的时钟周期总和进行绝对确定性的计算。

- Mike Nakis

Answer 3

简单来说，RDTSC不能可靠地用于测量两条指令之间的时间。它可用于测量更长时间段（例如，计算内存缓冲区校验和的子例程所需的时间）。

在早期的处理器上，时间戳计数器每个内部处理器时钟周期递增，但在Core之后的较新处理器上，时间戳计数器以恒定速率递增，不受内部时钟周期的影响。

对于更长的时间段，计数器递增的恒定速率与内部时钟周期匹配（如果处理器没有改变频率），但对于仅发生在两条指令之间的短时间段，计数器递增的恒定速率和处理器时钟周期之间可能存在不一致。

RDTSC不能用于测量两条指令之间的时间的第二个原因是乱序执行和指令流水线。CPU混合不依赖于彼此的指令的顺序，并将指令分割为微操作以进一步执行这些微操作，因此您可能永远不知道何时执行RDTSC本身。

- Maxim Masiutin