(Un-)Deterministic CPU 行为和关于（物理）执行持续时间的推理
(Un-)Deterministic CPU behavior and reasoning about (physical) execution duration
过去我处理过时间紧迫的软件开发。这些应用程序的开发基本上是这样进行的： "let's write the code, test latency and jitter, and optimize both until they are in the acceptable range." 我觉得这非常令人沮丧；这不是我所说的
适当的工程，我想做得更好。
所以我研究了这个问题：为什么我们会有抖动？答案当然是：
- 缓存：从主存中获取一段代码或数据比从一级缓存中获取相同数据花费的时间多 2 个数量级。所以
物理执行时间取决于缓存中的内容。反过来，这取决于几个因素：
- 应用程序的代码和数据布局：我们都知道可怕的行与列主矩阵遍历示例
- CPU 的缓存策略，包括缓存行的推测预取
- 同一核心上的其他进程正在做事情
- 分支预测：CPU 尝试猜测将执行条件跳转的哪个分支。即使同一个条件跳转执行了两次，
预测可能不同，因此 "pipeline bubble" 可能形成一次，但不是另一次。
- 中断：异步行为显然会导致抖动
- 频率缩放：谢天谢地在实时系统中禁用
有很多东西会干扰一段代码的行为。尽管如此：如果我有两条指令，位于同一个缓存中
行，不依赖于任何数据且不包含（条件）跳转。然后应该消除缓存和分支预测的抖动，并且
只有中断应该起作用。正确的？好吧，我写了一个小程序，两次获取时间戳计数器 (tsc)，并将差值写入标准输出。我在禁用频率缩放的 rt-patched linux 内核上执行它。
该代码具有基于 glibc 的初始化和清理功能，并调用了我认为有时在缓存中有时不在缓存中的 printf。但是在对 "rdtsc" 的调用之间（将 tsc 写入 edx:eax），每次执行二进制文件时，一切都应该是确定性的。可以肯定的是，我反汇编了 elf 文件，这里是带有两个 rdtsc 调用的部分：
00000000000006b0 <main>:
6b0: 0f 31 rdtsc
6b2: 48 c1 e2 20 shl [=11=]x20,%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 [=11=]x20,%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！中断应该从哪里来？！）。
所以我的问题是：
- 为什么代码不是确定性的，即，为什么每个 运行 都没有得到相同的数字？
- 是否有可能对 运行ning 时间进行推理，至少是对这段非常简单的代码进行推理？我能保证的 运行ning 时间至少有一个界限吗（使用工程原理，而不是测量结合希望）？
- 如果没有，不确定行为的来源究竟是什么？ CPU（或计算机的其余部分？）的哪个组件在这里掷骰子？
加载程序已将指令放置在您在左侧看到的地址中。我不知道缓存是在物理地址上工作还是在逻辑地址上工作，但这无关紧要，因为物理地址和逻辑地址之间映射的粒度非常粗，（如果我没记错的话，至少 4k，）并且无论如何都是肯定是缓存行大小的倍数。因此，您可能在地址 680 处有一个缓存行边界，然后下一个在地址 6C0 处，因此您很可能对缓存行没有问题。
如果您的代码被中断抢占，那么您的其中一个读数可能会偏离数百甚至数千个周期，而不是您所看到的数十个周期。所以也不是这样。
除了您已确定的因素外，还有更多因素会影响读数：
- 代表另一个线程完成 DMA 访问
- CPU 管道的状态
- CPU寄存器分配
CPU 寄存器分配特别有趣，因为它给出了现代 CPUs 有多复杂的想法，因此预测要花费多少时间是多么困难通过任何给定的指令。您使用的寄存器不是真正的寄存器；他们在某种程度上是 "virtual"。 CPU 包含一个内部通用寄存器组，它将其中一些分配给您的线程，将它们映射到您想要的 "rax" 或 "rdx"。其复杂性令人难以置信。
归根结底，您发现 CPU 时间（不是真的，但是）实际上 在基于 x86-x64 的现代桌面系统中是不确定的。这是意料之中的事。
幸运的是，这些系统速度如此之快，以至于它几乎无关紧要，而在重要的时候，我们不使用桌面系统，而是使用嵌入式系统。
对于那些对可预测的指令执行时间有学术需求的人，可以使用仿真器，根据书中的说法，仿真器将每条仿真指令所用的时钟周期数相加。这些是绝对确定性的。
一旦消除了抖动的外部来源，CPUs 仍然不是完全确定的 - 至少基于您可以控制的因素。
更重要的是，您似乎在一个模型下操作，其中每条指令串行执行，需要一定的时间。当然，现代 out-of-order CPUs 通常一次执行多条指令，并且通常可能会重新排序指令流，以便指令在最旧的未执行指令之前执行 200 多条或更多指令.
在该模型中，很难准确地说出一条指令的开始或结束位置（它是在解码、执行、退役或其他时间），而且 "timing" 指令肯定很难在参与这个高度并行的管道时有合理的周期精确解释。
由于 rdstc 没有序列化管道，你得到的时间可能是非常随机的，即使这个过程是完全确定的 - 它完全取决于管道中的其他指令等等.对 rdtsc 的第二次调用永远不会具有与第一次相同的管道状态，并且初始管道状态也会不同。
此处通常的解决方案是在发出 rdstc 之前发出 cpuid 指令，但一些改进 have been discussed.
如果你想要一个CPU绑定代码如何运行的好模型1，你可以获得大部分通过阅读 first three guides on Agner Fog's optimization page (skip the C++ if you are only interesting in assembly level), as well as What every programmer should know about memory 的方式。后者有一个 PDF 版本，可能更容易阅读。
这将允许获取一段代码并对其执行方式进行建模，而无需每个 运行 它。我已经做到了，有时会因为我的努力而收到周期准确的结果。在其他情况下，结果比模型预测的要慢，您必须四处挖掘以了解您遇到的其他瓶颈 - 偶尔您会发现一些完全没有记录的架构！
如果您只想为短代码段提供周期准确（或接近准确）的计时，我建议 libpfc，它在 x86 上让您可以在用户空间访问性能计数器，并在右侧声明周期准确的结果条件（基本上你将进程固定到 CPU 并防止上下文切换，这似乎你可能已经在做）。性能计数器可以为您提供比 rdstc.
更好的结果
最后，请注意 rdtsc 正在测量 挂钟时间 ，这与 [=20] 几乎所有现代内核上的 CPU 周期根本不同=].随着 CPU 减慢，您的表观测量成本将增加，反之亦然。这也给指令本身增加了一些减速，指令本身必须出去并读取一个计数器，该计数器绑定到不同于 CPU 时钟的时钟域。
1 也就是说，它受限于我的计算、内存访问等 - 而不是受 IO、用户输入、外部设备等约束
简单解释一下：RDTSC 不能可靠地测量两条指令之间的时间。它可用于测量更长的时间段（例如，计算内存缓冲区校验和的子例程所花费的时间）。
在较旧的处理器上，时间戳计数器随每个内部处理器时钟周期递增，但在较新的处理器上，自 Core 以来，时间戳计数器以恒定速率递增，而不管内部时钟周期如何。
对于较长的时间段，计数器增加的恒定速率与内部时钟周期相匹配（如果处理器不改变频率），但对于较小的时间段，这只发生在两条指令之间，可能有计数器增加的恒定速率与处理器时钟周期之间的不协调。
RDTSC不能用于测量两条指令之间时间的第二个原因是乱序执行和指令流水线。 CPU 将互不依赖的指令顺序混在一起，将指令拆分成微操作进一步执行这些微操作，所以你可能永远不知道RDTSC本身什么时候会被执行。
过去我处理过时间紧迫的软件开发。这些应用程序的开发基本上是这样进行的： "let's write the code, test latency and jitter, and optimize both until they are in the acceptable range." 我觉得这非常令人沮丧；这不是我所说的 适当的工程，我想做得更好。
所以我研究了这个问题：为什么我们会有抖动？答案当然是：
- 缓存：从主存中获取一段代码或数据比从一级缓存中获取相同数据花费的时间多 2 个数量级。所以
物理执行时间取决于缓存中的内容。反过来，这取决于几个因素：
- 应用程序的代码和数据布局：我们都知道可怕的行与列主矩阵遍历示例
- CPU 的缓存策略，包括缓存行的推测预取
- 同一核心上的其他进程正在做事情
- 分支预测：CPU 尝试猜测将执行条件跳转的哪个分支。即使同一个条件跳转执行了两次， 预测可能不同，因此 "pipeline bubble" 可能形成一次，但不是另一次。
- 中断：异步行为显然会导致抖动
- 频率缩放：谢天谢地在实时系统中禁用
有很多东西会干扰一段代码的行为。尽管如此：如果我有两条指令，位于同一个缓存中 行，不依赖于任何数据且不包含（条件）跳转。然后应该消除缓存和分支预测的抖动，并且 只有中断应该起作用。正确的？好吧，我写了一个小程序，两次获取时间戳计数器 (tsc)，并将差值写入标准输出。我在禁用频率缩放的 rt-patched linux 内核上执行它。
该代码具有基于 glibc 的初始化和清理功能，并调用了我认为有时在缓存中有时不在缓存中的 printf。但是在对 "rdtsc" 的调用之间（将 tsc 写入 edx:eax），每次执行二进制文件时，一切都应该是确定性的。可以肯定的是，我反汇编了 elf 文件，这里是带有两个 rdtsc 调用的部分：
00000000000006b0 <main>:
6b0: 0f 31 rdtsc
6b2: 48 c1 e2 20 shl [=11=]x20,%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 [=11=]x20,%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！中断应该从哪里来？！）。
所以我的问题是：
- 为什么代码不是确定性的，即，为什么每个 运行 都没有得到相同的数字？
- 是否有可能对 运行ning 时间进行推理，至少是对这段非常简单的代码进行推理？我能保证的 运行ning 时间至少有一个界限吗（使用工程原理，而不是测量结合希望）？
- 如果没有，不确定行为的来源究竟是什么？ CPU（或计算机的其余部分？）的哪个组件在这里掷骰子？
加载程序已将指令放置在您在左侧看到的地址中。我不知道缓存是在物理地址上工作还是在逻辑地址上工作，但这无关紧要，因为物理地址和逻辑地址之间映射的粒度非常粗，（如果我没记错的话，至少 4k，）并且无论如何都是肯定是缓存行大小的倍数。因此，您可能在地址 680 处有一个缓存行边界，然后下一个在地址 6C0 处，因此您很可能对缓存行没有问题。
如果您的代码被中断抢占，那么您的其中一个读数可能会偏离数百甚至数千个周期，而不是您所看到的数十个周期。所以也不是这样。
除了您已确定的因素外，还有更多因素会影响读数：
- 代表另一个线程完成 DMA 访问
- CPU 管道的状态
- CPU寄存器分配
CPU 寄存器分配特别有趣，因为它给出了现代 CPUs 有多复杂的想法，因此预测要花费多少时间是多么困难通过任何给定的指令。您使用的寄存器不是真正的寄存器；他们在某种程度上是 "virtual"。 CPU 包含一个内部通用寄存器组，它将其中一些分配给您的线程，将它们映射到您想要的 "rax" 或 "rdx"。其复杂性令人难以置信。
归根结底，您发现 CPU 时间（不是真的，但是）实际上 在基于 x86-x64 的现代桌面系统中是不确定的。这是意料之中的事。
幸运的是，这些系统速度如此之快，以至于它几乎无关紧要，而在重要的时候，我们不使用桌面系统，而是使用嵌入式系统。
对于那些对可预测的指令执行时间有学术需求的人，可以使用仿真器，根据书中的说法，仿真器将每条仿真指令所用的时钟周期数相加。这些是绝对确定性的。
一旦消除了抖动的外部来源，CPUs 仍然不是完全确定的 - 至少基于您可以控制的因素。
更重要的是，您似乎在一个模型下操作，其中每条指令串行执行，需要一定的时间。当然，现代 out-of-order CPUs 通常一次执行多条指令，并且通常可能会重新排序指令流，以便指令在最旧的未执行指令之前执行 200 多条或更多指令.
在该模型中，很难准确地说出一条指令的开始或结束位置（它是在解码、执行、退役或其他时间），而且 "timing" 指令肯定很难在参与这个高度并行的管道时有合理的周期精确解释。
由于 rdstc 没有序列化管道，你得到的时间可能是非常随机的，即使这个过程是完全确定的 - 它完全取决于管道中的其他指令等等.对 rdtsc 的第二次调用永远不会具有与第一次相同的管道状态，并且初始管道状态也会不同。
此处通常的解决方案是在发出 rdstc 之前发出 cpuid 指令，但一些改进 have been discussed.
如果你想要一个CPU绑定代码如何运行的好模型1，你可以获得大部分通过阅读 first three guides on Agner Fog's optimization page (skip the C++ if you are only interesting in assembly level), as well as What every programmer should know about memory 的方式。后者有一个 PDF 版本，可能更容易阅读。
这将允许获取一段代码并对其执行方式进行建模，而无需每个 运行 它。我已经做到了，有时会因为我的努力而收到周期准确的结果。在其他情况下，结果比模型预测的要慢，您必须四处挖掘以了解您遇到的其他瓶颈 - 偶尔您会发现一些完全没有记录的架构！
如果您只想为短代码段提供周期准确（或接近准确）的计时，我建议 libpfc，它在 x86 上让您可以在用户空间访问性能计数器，并在右侧声明周期准确的结果条件（基本上你将进程固定到 CPU 并防止上下文切换，这似乎你可能已经在做）。性能计数器可以为您提供比 rdstc.
最后，请注意 rdtsc 正在测量 挂钟时间 ，这与 [=20] 几乎所有现代内核上的 CPU 周期根本不同=].随着 CPU 减慢，您的表观测量成本将增加，反之亦然。这也给指令本身增加了一些减速，指令本身必须出去并读取一个计数器，该计数器绑定到不同于 CPU 时钟的时钟域。
1 也就是说，它受限于我的计算、内存访问等 - 而不是受 IO、用户输入、外部设备等约束
简单解释一下：RDTSC 不能可靠地测量两条指令之间的时间。它可用于测量更长的时间段（例如，计算内存缓冲区校验和的子例程所花费的时间）。
在较旧的处理器上，时间戳计数器随每个内部处理器时钟周期递增，但在较新的处理器上，自 Core 以来，时间戳计数器以恒定速率递增，而不管内部时钟周期如何。
对于较长的时间段，计数器增加的恒定速率与内部时钟周期相匹配（如果处理器不改变频率），但对于较小的时间段，这只发生在两条指令之间，可能有计数器增加的恒定速率与处理器时钟周期之间的不协调。
RDTSC不能用于测量两条指令之间时间的第二个原因是乱序执行和指令流水线。 CPU 将互不依赖的指令顺序混在一起，将指令拆分成微操作进一步执行这些微操作，所以你可能永远不知道RDTSC本身什么时候会被执行。