caching - (非)确定性 CPU 行为和关于(物理)执行持续时间的推理

Question

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

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

缓存:从主内存中获取一段代码或数据比从一级缓存中获取相同数据要多 2 个数量级。所以
物理执行时间取决于缓存中的内容。反过来，这取决于几个因素:

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

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

同一核心上的其他进程在做事

分支预测:CPU 尝试猜测条件跳转的哪个分支将被执行。即使同一个条件跳转被执行两次，
预测可能会有所不同，因此可能会形成一次“管道泡沫”，但不会形成另一次。

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

频率缩放:幸好在实时系统中禁用

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

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

所以我的问题是:

为什么代码不是确定性的，即为什么我每次运行都没有得到相同的数字？

是否有可能推断出运行时间，至少是这段非常简单的代码？我可以保证的运行时间是否至少有一个界限(使用工程原理，而不是测量与希望相结合)？

如果没有，非确定性行为的确切来源是什么？ CPU 的哪个组件(或计算机的其余部分？)在这里掷骰子？

Answer 1

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

更重要的是，您似乎在一个模型下操作，其中每条指令都按顺序执行，需要一定的时间。当然，现代out-of-order CPU 通常一次执行多于一条指令，并且通常可以重新排序指令流，使得指令在最旧的未执行指令之前执行 200+ 条或更多条指令。

在该模型中，很难准确地说出指令在何处开始或结束(即在解码、执行、退役或其他时间)，而且“定时”指令很难有一个合理的周期精确解释同时参与这个高度并行的管道。

由于rdstc不序列化流水线，你得到的时间可能是相当随机的，即使这个过程是完全确定的——它将完全取决于流水线中的其他指令等等。第二次调用rdtsc永远不会有与第一个相同的管道状态，并且初始管道状态也将不同。

这里通常的解决方案是发出 cpuid发出 rdstc 之前的指令, 但有些改进 have been discussed .

如果您想要一个很好的模型来了解一段受 CPU 限制的代码如何运行1，您可以通过阅读 first three guides 来了解大部分情况。在 Agner Fog 的优化页面上(如果您只对汇编级别感兴趣，请跳过 C++)，以及 What every programmer should know about memory .后者有一个 PDF 版本，可能更容易阅读。

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

如果您只想要短代码段的周期准确(或几乎如此)计时，我建议 libpfc在 x86 上，它使您可以在用户空间访问性能计数器并在正确的条件下声明周期准确的结果(基本上，您将进程固定到 CPU 并防止上下文切换，这似乎您可能已经在做)。性能计数器可以为您提供比 rdstc 更好的结果.

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

1 也就是说，它绑定(bind)了我的计算、内存访问等 - 而不是 IO、用户输入、外部设备等。