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

Question

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

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

• 缓存：从主内存获取一段代码或数据比从 L1 缓存获取相同数据要多花费 2 个数量级的时间。所以物理执行时间取决于缓存中的内容。这又取决于几个因素：
  • 应用程序的代码和数据布局：我们都知道可怕的行主与列主矩阵遍历示例
  • CPU 的缓存策略，包括缓存行的推测性预取
  • 同一核心上的其他进程正在做事情
• 分支预测：CPU 尝试猜测条件跳转的哪个分支将被执行。即使相同的条件跳转执行两次，预测也可能不同，因此一次可能会形成“管道泡沫”，而另一次则不会。
• 中断：异步行为显然会导致抖动
• 频率缩放：幸好在实时系统中被禁用

有很多事情会干扰一段代码的行为。尽管如此：如果我有两条指令，位于同一缓存行，不依赖于任何数据，也不包含（条件）跳转。然后，应该消除缓存和分支预测带来的抖动，并且只有中断才能发挥作用。正确的？好吧，我编写了一个小程序，获取时间戳计数器 (tsc) 两次，并将差异写入标准输出。我在一个打了 rt 补丁的 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 

没有条件跳转，位于同一个缓存行上（尽管我对此不是 100% 确定 - elf 加载器到底把指令放在哪里？这里的 64 字节边界映射到内存中的 64 字节边界吗？）...在哪里抖动从何而来？如果我执行该代码 1000 次（通过 zsh，每次都重新启动程序），我会得到从 12 到 46 的值，中间有几个值。由于我的内核中禁用了频率缩放，因此会出现中断。现在我愿意相信，在1000次处决中，有一次被中断。我不准备相信 90% 都被中断了（我们这里讨论的是 ns 间隔！中断应该从哪里来？！）。

所以我的问题是：

• 为什么代码不是确定性的，即为什么我每次运行都没有得到相同的数字？
• 是否有可能推断出运行时间，至少是这段非常简单的代码的运行时间？我可以保证运行时间至少有一个界限（使用工程原理，而不是与希望相结合的测量）？
• 如果不存在，那么不确定性行为的根源究竟是什么？CPU（或计算机的其余部分？）的哪个组件在这里掷骰子？

Answer 1

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

更重要的是，您似乎在一个模型下操作，其中每条指令都串行执行，需要一定的时间。当然，现代乱序CPU通常会同时执行多个指令，并且通常可能会对指令流重新排序，使得指令在最旧的未执行指令之前执行200多条或更多指令。

在该模型中，很难确切地说指令在哪里开始或结束（即何时解码、执行、退出或其他），并且“定时”指令当然很难有合理的周期精确解释同时参与这个高度并行的管道。

由于rdstc不会序列化管道，因此即使该过程是完全确定性的，您获得的计时也可能非常随机 - 它将完全取决于管道中的其他指令等。第二次调用rdtsc永远不会具有与第一次相同的管道状态，并且初始管道状态也将不同。

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

如果您想要了解一段CPU 绑定代码如何运行的良好模型^{1 ，您可以通过阅读 Agner Fog 优化页面上的}前三个指南来获得大部分内容（如果您只对汇编级别感兴趣，请跳过 C++），如下所示以及每个程序员都应该了解的有关内存的知识。后者有一个 PDF 版本，可能更容易阅读。

这将允许获取一段代码并对其执行方式进行建模，而无需每次都运行它。我已经做到了，有时我的努力会收到周期准确的结果。在其他情况下，结果比模型预测的要慢，您必须深入挖掘以了解您遇到的其他瓶颈 - 有时您会发现有关架构的一些完全未记录的内容！

如果您只想对短代码段进行周期精确（或接近如此）的计时，我推荐libpfc，它在 x86 上使您可以在正确的条件下让用户访问性能计数器并声明周期精确的结果（基本上您可以固定进程到 CPU 并防止上下文切换，您似乎已经在这样做了）。性能计数器可以为您提供比rdstc.

最后，请注意，这rdtsc是测量挂钟时间，这与几乎所有具有DVFS 的现代内核上的 CPU 周期根本不同。随着 CPU 速度减慢，您的表观测量成本将会增加，反之亦然。这也增加了指令本身的速度，指令本身必须出去读取与 CPU 时钟不同的时钟域相关的计数器。

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