提问者:小点点

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


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

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

  • 缓存:从主存中获取一段代码或数据比从L1缓存中获取相同数据需要大约2个数量级的时间。因此物理执行时间取决于缓存中的内容。这反过来又取决于几个因素:
    • 应用程序的代码和数据布局:我们都知道可怕的行与列主矩阵遍历示例
    • CPU的缓存策略,包括缓存行的推测预取
    • 同一内核上的其他进程在做事情

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

    代码有基于glibc的初始化和清理,并调用printf,我认为它有时在缓存中,有时不在。但是在对“rdtsc”的调用(将tsc写入edx: eax)之间,每次执行二进制文件时,一切都应该是确定的。为了确定,我拆解了精灵文件,这里是两个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%确定——精灵加载器到底把指令放在哪里?这里的64字节边界映射到内存中的64字节边界吗?)……抖动是从哪里来的?如果我执行该代码1000次(通过zsh,每次重新启动程序),我得到的值从12到46,中间有几个值。由于在我的内核中禁用了频率缩放,这留下了中断。现在我愿意相信,在1000次执行中,有一次被中断。我不准备相信90%被中断(我们在这里谈论的是ns间隔!中断应该从哪里来?!)。

    所以我的问题是:

    • 为什么代码不是确定性的,即为什么我每次运行都没有得到相同的数字?
    • 是否可以对运行时间进行推理,至少对这段非常简单的代码,完全可以推理?运行时间上是否至少有一个我可以保证的界限(使用工程原理,而不是结合希望的度量)?
    • 如果没有,非确定性行为的来源到底是什么?CPU的哪个组件(或计算机的其余部分?)在这里掷骰子?

共3个答案

匿名用户

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

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

在该模型中,很难准确说出指令的开始或结束位置(它是在解码、执行、退役或其他时间),并且“定时”指令在参与这个高度并行的管道时肯定很难有合理的循环精确解释。

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

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

如果你想了解一段绑定CPU代码如何运行1,你可以通过阅读Agner Fog优化页面上的前三个指南(如果你只对汇编级别感兴趣,请跳过C)以及每个程序员都应该了解的内存。后者的PDF版本可能更容易阅读。

这将允许获取一段代码并对其执行情况进行建模,而无需每次运行它。我已经做到了,有时我会收到周期精确的结果。在其他情况下,结果比模型预测的要慢,你必须四处挖掘,以了解你遇到的其他瓶颈——偶尔你会发现一些关于架构的完全没有文档记录的东西!

如果你只是想要短代码段的周期精确(或几乎如此)的计时,我推荐libpfc,它在x86上允许你用户访问性能计数器,并在正确的条件下声明周期精确的结果(基本上你有pin进程CPU并防止上下文切换,这似乎你已经在做了)。perf计数器可以给你比rdstc更好的结果。

最后,请注意rdtsc正在测量挂钟时间,这与几乎所有使用DVFS的现代内核上的CPU周期有着根本的不同。随着CPU变慢,您的明显测量成本将会增加,反之亦然。这也给指令本身增加了一些减速,它必须出去读取与CPU时钟不同的时钟域相关的计数器。

也就是说,它绑定了我的计算、内存访问等——而不是IO、用户输入、外部设备等。

匿名用户

加载程序已将指令放置在您在左侧看到的地址中。我不知道缓存是否适用于物理地址或逻辑地址,但这无关紧要,因为物理地址和逻辑地址之间映射的颗粒度相当粗糙,(至少4k如果我没有弄错的话,)无论如何,它肯定是缓存线大小的倍数。因此,您可能在地址680处有一个缓存线边界,然后在地址6C0处有下一个缓存线边界,因此您最有可能在缓存线方面做得很好。

如果你的代码被一个中断抢占了,那么你的一个读数可能会偏离数百个,可能是数千个周期,而不是像你所见的那样偏离几十个周期。所以这也不是。

除了你已经确定的因素之外,还有更多的因素可以影响阅读:

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

CPU寄存器分配特别有趣,因为它给出了现代CPU有多复杂的概念,因此预测任何给定指令将花费多少时间是多么困难。你使用的寄存器不是真正的寄存器;它们在某种程度上是“虚拟的”。CPU包含一个通用寄存器的内部库,它将其中一些分配给你的线程,将它们映射到你想认为的“rax”或“rdx”。这其中的复杂性令人难以置信。

归根结底,你会发现CPU时间在基于x86-x64的现代桌面系统中实际上是不确定的。这是意料之中的。

幸运的是,这些系统速度如此之快,以至于它几乎不重要,当它重要时,我们不使用桌面系统,我们使用嵌入式系统。

对于那些对可预测的指令执行时间有学术需求的人来说,有仿真器,根据这本书,它将每条模拟指令所花费的时钟周期数相加。这些都是绝对确定的。

匿名用户

简单地解释一下:RDTSC不能可靠地用于测量两条指令之间的时间。它可以用来测量更长的时间段(例如,计算内存缓冲区校验和的子程序所花费的时间)。

在较旧的处理器上,时间戳计数器随着每个内部处理器时钟周期而递增,但在较新的处理器上,由于Core,时间戳计数器以恒定速率递增,而不管内部时钟周期如何。

对于较长的时间段,计数器增加的恒定速率与内部时钟周期相匹配(如果处理器不改变频率),但是对于较小的时间段,这只是发生在两个指令之间,在计数器增加的恒定速率和处理器时钟周期之间可能存在不和谐。

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