对于必须按顺序发生的操作，处理器的延迟界限和吞吐量界限

Question

我的教科书（计算机系统：程序员的观点）指出，当一系列操作必须严格按顺序执行时，会遇到延迟界限，而吞吐量界限则表征处理器功能单元的原始计算能力。

教科书的问题5.5和5.6介绍了多项式计算的这两种可能的循环结构

double result = a[0];
double xpwr = x;
for (int i = 1; i <= degree; i++) {
    result += a[i] * xpwr;
    xpwr = x * xpwr;
}

和

double result = a[degree];
double xpwr = x;
for (int i = degree - 1; i >= 0; i--) {
    result = a[i] + x * result;
}

假设在微体系结构上使用以下执行单元执行循环：

• 一个浮点加法器。它的延迟为3个周期，并且是完全流水线的
• 两个浮点乘法器。每个周期的延迟为5个周期，并且都是完全流水线的
• 四个整数ALU，每个有一个周期的延迟

针对该问题给出的浮点乘法和加法的延迟界限分别为5.0和3.0。根据应答键，第一个循环的总循环延迟为每个元素5.0个周期，第二个循环为每个元素8.0个周期。我不明白为什么第一个循环不是8.0。

似乎在将a[i]加到这个乘积中产生下一个结果值之前，a[i]必须乘以xpwr。谁能给我解释一下吗？

Answer 1

对于5.5，有3条平行线：

1. xpwr=x*xpwr；具有5个周期延迟。发生在迭代#i
2. a[i]*xpwr；具有5个周期延迟，但不在循环承载依赖项的关键路径上。发生在迭代#i中。
3. 结果（2）；具有3个周期延迟。在迭代#i 1中发生，但对于iter#i结果

基于@peter的澄清

1. 要理解“回路承载”dep：意味着电流回路（i）依赖于其他回路（比如，i-1）：所以我们可以看到xpwr=x*xpwr as<代码>xpwr（i）=x*xpwr（i-1） 。因此，形成一条路径（但如果是关键路径，则尚未知道）

Answer 2

术语：可以说循环是“受限于延迟”，但在分析瓶颈时，我不会说“受限于延迟”或“受限”。我听上去不对。您正在测量（或通过静态性能分析计算）的是关键路径的延迟或长度，或循环承载的依赖链的长度。（关键路径是最长的延迟链，如果超过无序exec可以隐藏的时间，则是导致CPU暂停的关键路径。）

关键的一点是无序执行只关心真正的依赖关系，否则允许操作并行执行。CPU可以在每个周期启动新的乘法和加法。（根据延迟数字，假设它是Intel Sandybridge或Haswell，或类似的产品。即，假设FPU是完全流水线的。）

第一个循环中的两个循环携带的依赖关系链是xpwr*=x和result=stuff，每个都从自己的前一个迭代读取，但彼此之间的耦合方式不会增加延迟。它们可以重叠。

expWR有3个输入：

• 上一次迭代的结果

因此，您有两个依赖链，一个从另一个读取。加法dep链的每一步延迟较低，因此它只会等待乘法dep链。

xpwr从xpwr链“分叉”，在读取其输入后独立于它。该表达式的每次计算都独立于之前的计算。它取决于后面的xpwr，因此每个xpwr的开始仅受准备好该值的xpwr依赖链的限制。

无序执行可以大大提前执行负载和整数循环开销（准备好负载地址）。

mulsd（x86-64乘法标量双精度）用于xpwr更新，addsd用于结果更新。a[i]*xpwr 乘法没有显示，因为它是每个迭代的独立工作。它稍后会将加法倾斜一个固定的量，但我们假设有足够的FP吞吐量来完成这一操作，而不会对关键路径产生资源冲突。

mulsd   addsd         # first iteration result += stuff
 |   \    |           # first iteration xpwr   *= x can start at the same time
 v    \   v
mulsd   addsd
 |   \    |
 v    \   v
mulsd   addsd
 |   \    |
 v    \   v
mulsd   addsd

（最后xpwrmulsd结果未使用，编译器可以剥离最后的迭代并对其进行优化。）

结果=a[i]x*结果；是较少的数学运算，但我们确实有一个8个循环的循环携带关键路径。下一个mulsd在addsd也完成之前无法启动。这对长链（高度多项式）不利，尽管乱序执行通常可以隐藏小度的延迟，例如5或6个系数。

当您有FMA可用时，这才真正闪耀：每次迭代都变成一个融合乘法添加。在真正的Haswell CPU上，FMA与FP乘法具有相同的5周期延迟，因此循环每5个周期运行一次迭代，在尾部获得最终结果的额外延迟更少。

在为具有FMA的机器进行优化时，现实世界中的高性能代码通常会将此策略用于短多项式，以便为许多不同的输入计算相同多项式的高吞吐量。（因此，指令级并行性是跨多项式的单独求值，而不是通过花费更多的操作在一个多项式中创建任何值。）

拥有两个具有这些延迟的FP乘法器与Haswell的SSE2/AVX数学匹配，尽管在实际的Haswell中，FP加法器与乘法器位于同一端口上，因此不能在一个周期内启动所有3个操作。FP执行单元也与4个整数ALU共享端口，但Sandybridge/Haswell的前端只有4个UOP宽，所以通常不会成为瓶颈。

查看大卫·坎特（DavidKanter）在哈斯韦尔（Haswell）的深入研究，并提供精美的图表https://agner.org/optimize/，以及x86标记wiki中的其他性能资源）

在Haswell之后的下一代Broadwell上，FP mul延迟提高到3个周期。仍然是2/时钟吞吐量，FP add/sub仍然是3c和FMA 5c。因此，即使与霍纳方法的FMA实现相比，具有更多操作的循环也会更快。

在Skylake上，所有FP操作都具有相同的4周期延迟，所有操作都在两个FMA单元上运行，FP add/sub的吞吐量为2/时钟。最近，Alder Lake重新引入了较低延迟的FP加法（对于mul/fma为3个周期，而对于4个周期，但仍然保持2个/时钟的吞吐量），因为现实世界中的代码通常会对数组进行天真的求和，而严格的FP语义不允许编译器将其优化为多个累加器。所以在最近的x86上，如果您仍然有一个multiply-dep链，而不仅仅是add，那么避免FMA并没有什么好处。

还相关：

>

在预测现代超标量处理器上的操作延迟时需要考虑哪些因素，我如何手动计算它们？更一般的分析需要考虑其他可能的瓶颈：前端uop吞吐量和后端执行单元的争用。Dep链，尤其是循环承载的链，是第三大可能的瓶颈（除了缓存未命中和分支未命中等停顿）。

每个汇编指令需要多少CPU周期？-这些概念的另一个基本介绍

为了增加依赖链的长度，理解lford对具有两个长依赖链的循环的影响-当它们太长时，乱序exec重叠dep链的能力是有限的。

为什么mulss在Haswell上只需要3个周期，这与Agner的指令表不同？（使用多个累加器展开FP回路）-FP dep链尽可能与展开并行，例如点积。

在这种情况下，对于高次多项式，您可以执行类似的操作，例如并行生成x^2n和x^2n。正如艾格纳·福格（Agner Fog）的向量类库中用于短多项式的埃斯特林方案。我发现，当短多项式是跨循环迭代的独立工作的一部分时（例如，作为日志（arr[I]）的一部分），直霍纳法则的吞吐量更好，因为无序执行能够隐藏与其他工作交织的5或6个FMA链的延迟。