处理器必须按顺序发生的操作的延迟范围和吞吐量范围
Latency bounds and throughput bounds for processors for operations that must occur in sequence
我的教科书（计算机系统：程序员的观点）指出，当必须严格按顺序执行一系列操作时会遇到延迟限制，而吞吐量限制则表征处理器功能单元的原始计算能力。
教材第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] 必须先乘以 xpwr 才能将 a[i] 与此乘积相加以产生下一个结果值。有人可以给我解释一下吗？
术语：您可以说循环“受延迟限制”，但在分析该瓶颈时我不会说“延迟限制”或“界限”。这对我来说听起来不对劲。您正在测量（或通过静态性能分析计算）的是 关键路径 的延迟或长度，或循环携带的依赖链的长度。 （critical 路径是最长的延迟链，如果它比无序执行程序可以隐藏的时间长，则它是 CPU 拖延的原因。）
重点是乱序执行只关心真正的依赖关系，否则允许操作并行执行。 CPU 可以启动一个每个周期都有新的乘法和新的加法。 （根据延迟数字假设它是 Intel Sandybridge 或 Haswell，或类似的1。即假设 FPU 是完全流水线的。）
第一个循环中的两个循环携带的依赖链是 xpwr *= x 和 result += stuff，每个都从他们自己的前一次迭代中读取，但没有以增加他们的方式相互耦合延迟。它们可以重叠。
result += a[i] * xpwr 有 3 个输入：
result 来自上一次迭代。a[i] 假定您已准备就绪。xpwr 来自 previous 迭代。更重要的是，之前的迭代可以立即开始计算xpwr，而不是等待之前的result.
所以你有 2 个依赖链，一个从另一个读取。加法 dep 链每步的延迟较低，因此它最终只是等待乘法 dep 链。
a[i] * xpwr 从 xpwr dep 链“分叉”，在读取其输入后独立于它。该表达式的每个计算都独立于它的先前计算。它依赖于后来的 xpwr，因此每个 a[i] * xpwr 的开始仅受具有该值的 xpwr 依赖链的限制。
加载和整数循环开销（准备好加载地址）可以通过乱序执行提前执行。
跨迭代的依赖模式图
mulsd (x86-64 multiply Scalar Double) 用于 xpwr 更新，addsd 用于 result 更新。 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
（最后的 xpwr mulsd 结果未使用，编译器可以剥离最终迭代并优化它。）
第二个循环，Horner's method - 使用 FMA 快速，否则 8 个循环
result = a[i] + x * result; 是较少的数学运算，但我们确实有一个 循环携带的 8 个周期的关键路径 。在 addsd 也完成之前，下一个 mulsd 无法开始。这对长链（高次多项式）不利，尽管无序执行通常可以隐藏小度数的延迟，例如 5 或 6 个系数。
当你有 FMA 可用时，这真的很棒：每次迭代变成一个 Fused Multiply-Add。在真正的 Haswell CPUs 上，FMA 与 FP 乘法具有相同的 5 个周期延迟，因此循环每 5 个周期迭代一次，在尾部获得最终结果的额外延迟更少。
现实世界中的高性能代码在针对具有 FMA 的机器进行优化时通常将此策略用于短多项式，以实现针对许多不同输入评估相同多项式的高吞吐量。 （因此指令级并行性是跨越多项式的单独评估，而不是试图通过花费更多操作来创建一个内的任何一个。）
脚注 1：与真实硬件的相似性
有两个具有这些延迟的 FP 乘法器将 Haswell 与 SSE2/AVX 数学相匹配，尽管在实际的 Haswell 中，FP 加法器与乘法器位于同一端口，因此您无法在一个周期内启动所有 3 个操作. FP 执行单元也与 4 个整数 ALU 共享端口，但 Sandybridge/Haswell 的前端只有 4 微指令宽，因此通常不会成为瓶颈。
参见 David Kanter's deep dive on Haswell with nice diagrams, and https://agner.org/optimize/, and other performance resources in the x86 tag wiki)
在 Haswell 之后的下一代 Broadwell 上，FP mul 延迟提高到 3 个周期。仍然是 2/clock 吞吐量，FP add/sub 仍然是 3c 和 FMA 5c。因此，与 Horner 方法的 FMA 实现相比，具有更多操作的循环在那里会更快。
在 Skylake 上，所有 FP 操作都是相同的 4 周期延迟，all running on the two FMA units with 2/clock throughput for FP add/sub as well. More recently, Alder Lake re-introduced lower latency FP addition (3 cycles vs. 4 for mul/fma but still keeping the 2/clock throughput), since real-world code often does stuff like naively summing an array, and strict FP semantics don't let compilers optimize it to 。所以在最近的 x86 上，如果你仍然有乘法 dep 链，而不仅仅是加法，那么避免 FMA 没有任何好处。
还相关：
What considerations go into predicting latency for operations on modern superscalar processors and how can I calculate them by hand?更一般的分析需要考虑其他可能的瓶颈：前端uop吞吐量，后端争用执行单元。 Dep 链，尤其是循环携带的，是第三大可能的瓶颈（缓存未命中和分支未命中等停滞除外。）
How many CPU cycles are needed for each assembly instruction? - 这些概念的另一个基本介绍
- 当 dep 链太长时，无序 exec 重叠 dep 链的能力受到限制。
- FP dep 链在可能的情况下与展开并行，例如点积。
在这种情况下，对于大次数多项式，您可以执行 x2 = x*x / x4 = x2 * x2 之类的操作，并可能并行生成 x^(2n) 和 x^(2n+1)。正如在 Agner Fog 的向量类库中用于短多项式的 Estrin's scheme 中一样。我发现，当短多项式是跨循环迭代的独立工作的一部分时（例如，作为 log(arr[i]) 的一部分），直接霍纳规则的吞吐量更高，因为无序执行能够隐藏链的延迟5 或 6 个 FMA 与其他工作交错。
对于5.5，有3条平行线：
xpwr = x * xpwr; 有 5 个周期延迟。发生在迭代#ia[i] * xpwr; 有 5 个周期延迟，但不在循环携带依赖项的关键路径上。在迭代 #i.result + (2); 有 3 个周期延迟。在迭代 #i+1 中发生，但对于 iter #i 结果
更新
根据@peter 的说明
- 要理解 'loop-carried' dep: 表示当前循环 (i) 依赖于其他循环 (比如 , i-1): 所以我们可以看到
xpwr = x * xpwr; 为 xpwr(i) = x * xpwr(i-1); 。因此形成一条路径（但还不知道它是否是关键路径）
a[i] * xpwr ，可以看作是第 1 步的副产品。所谓的“从第 1 步分叉出来”。这也需要 5 个周期。- 步骤 2 完成后，
result += ... 开始循环 i 。这需要 3 个周期。它取决于步骤 1，因此，步骤 3 也是一个 'loop carried' 依赖项，因此可能是“关键路径”的候选者。
- 由于步骤 3 是 3 循环 < 5 循环，因此步骤 1 成为关键路径。
- 如果第 3 步（假设）需要 10 个周期怎么办。然后据我了解，第 3 步成为关键路径。
附上示意图如下：
我的教科书（计算机系统：程序员的观点）指出，当必须严格按顺序执行一系列操作时会遇到延迟限制，而吞吐量限制则表征处理器功能单元的原始计算能力。
教材第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] 必须先乘以 xpwr 才能将 a[i] 与此乘积相加以产生下一个结果值。有人可以给我解释一下吗？
术语：您可以说循环“受延迟限制”，但在分析该瓶颈时我不会说“延迟限制”或“界限”。这对我来说听起来不对劲。您正在测量（或通过静态性能分析计算）的是 关键路径 的延迟或长度，或循环携带的依赖链的长度。 （critical 路径是最长的延迟链，如果它比无序执行程序可以隐藏的时间长，则它是 CPU 拖延的原因。）
重点是乱序执行只关心真正的依赖关系，否则允许操作并行执行。 CPU 可以启动一个每个周期都有新的乘法和新的加法。 （根据延迟数字假设它是 Intel Sandybridge 或 Haswell，或类似的1。即假设 FPU 是完全流水线的。）
第一个循环中的两个循环携带的依赖链是 xpwr *= x 和 result += stuff，每个都从他们自己的前一次迭代中读取，但没有以增加他们的方式相互耦合延迟。它们可以重叠。
result += a[i] * xpwr 有 3 个输入：
result来自上一次迭代。a[i]假定您已准备就绪。xpwr来自 previous 迭代。更重要的是，之前的迭代可以立即开始计算xpwr，而不是等待之前的result.
所以你有 2 个依赖链，一个从另一个读取。加法 dep 链每步的延迟较低，因此它最终只是等待乘法 dep 链。
a[i] * xpwr 从 xpwr dep 链“分叉”，在读取其输入后独立于它。该表达式的每个计算都独立于它的先前计算。它依赖于后来的 xpwr，因此每个 a[i] * xpwr 的开始仅受具有该值的 xpwr 依赖链的限制。
加载和整数循环开销（准备好加载地址）可以通过乱序执行提前执行。
跨迭代的依赖模式图
mulsd (x86-64 multiply Scalar Double) 用于 xpwr 更新，addsd 用于 result 更新。 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
（最后的 xpwr mulsd 结果未使用，编译器可以剥离最终迭代并优化它。）
第二个循环，Horner's method - 使用 FMA 快速，否则 8 个循环
result = a[i] + x * result; 是较少的数学运算，但我们确实有一个 循环携带的 8 个周期的关键路径 。在 addsd 也完成之前，下一个 mulsd 无法开始。这对长链（高次多项式）不利，尽管无序执行通常可以隐藏小度数的延迟，例如 5 或 6 个系数。
当你有 FMA 可用时，这真的很棒：每次迭代变成一个 Fused Multiply-Add。在真正的 Haswell CPUs 上，FMA 与 FP 乘法具有相同的 5 个周期延迟，因此循环每 5 个周期迭代一次，在尾部获得最终结果的额外延迟更少。
现实世界中的高性能代码在针对具有 FMA 的机器进行优化时通常将此策略用于短多项式，以实现针对许多不同输入评估相同多项式的高吞吐量。 （因此指令级并行性是跨越多项式的单独评估，而不是试图通过花费更多操作来创建一个内的任何一个。）
脚注 1：与真实硬件的相似性
有两个具有这些延迟的 FP 乘法器将 Haswell 与 SSE2/AVX 数学相匹配，尽管在实际的 Haswell 中，FP 加法器与乘法器位于同一端口，因此您无法在一个周期内启动所有 3 个操作. FP 执行单元也与 4 个整数 ALU 共享端口，但 Sandybridge/Haswell 的前端只有 4 微指令宽，因此通常不会成为瓶颈。
参见 David Kanter's deep dive on Haswell with nice diagrams, and https://agner.org/optimize/, and other performance resources in the x86 tag wiki)
在 Haswell 之后的下一代 Broadwell 上，FP mul 延迟提高到 3 个周期。仍然是 2/clock 吞吐量，FP add/sub 仍然是 3c 和 FMA 5c。因此，与 Horner 方法的 FMA 实现相比，具有更多操作的循环在那里会更快。
在 Skylake 上，所有 FP 操作都是相同的 4 周期延迟，all running on the two FMA units with 2/clock throughput for FP add/sub as well. More recently, Alder Lake re-introduced lower latency FP addition (3 cycles vs. 4 for mul/fma but still keeping the 2/clock throughput), since real-world code often does stuff like naively summing an array, and strict FP semantics don't let compilers optimize it to
还相关：
What considerations go into predicting latency for operations on modern superscalar processors and how can I calculate them by hand?更一般的分析需要考虑其他可能的瓶颈：前端uop吞吐量，后端争用执行单元。 Dep 链，尤其是循环携带的，是第三大可能的瓶颈（缓存未命中和分支未命中等停滞除外。）
How many CPU cycles are needed for each assembly instruction? - 这些概念的另一个基本介绍
在这种情况下，对于大次数多项式，您可以执行
x2 = x*x/x4 = x2 * x2之类的操作，并可能并行生成x^(2n)和x^(2n+1)。正如在 Agner Fog 的向量类库中用于短多项式的 Estrin's scheme 中一样。我发现，当短多项式是跨循环迭代的独立工作的一部分时（例如，作为log(arr[i])的一部分），直接霍纳规则的吞吐量更高，因为无序执行能够隐藏链的延迟5 或 6 个 FMA 与其他工作交错。
对于5.5，有3条平行线：
xpwr = x * xpwr;有 5 个周期延迟。发生在迭代#ia[i] * xpwr;有 5 个周期延迟，但不在循环携带依赖项的关键路径上。在迭代 #i. 中发生
result + (2);有 3 个周期延迟。在迭代 #i+1 中发生，但对于 iter #i 结果
更新
根据@peter 的说明
- 要理解 'loop-carried' dep: 表示当前循环 (i) 依赖于其他循环 (比如 , i-1): 所以我们可以看到
xpwr = x * xpwr;为xpwr(i) = x * xpwr(i-1);。因此形成一条路径（但还不知道它是否是关键路径） a[i] * xpwr，可以看作是第 1 步的副产品。所谓的“从第 1 步分叉出来”。这也需要 5 个周期。- 步骤 2 完成后，
result += ...开始循环 i 。这需要 3 个周期。它取决于步骤 1，因此，步骤 3 也是一个 'loop carried' 依赖项，因此可能是“关键路径”的候选者。 - 由于步骤 3 是 3 循环 < 5 循环，因此步骤 1 成为关键路径。
- 如果第 3 步（假设）需要 10 个周期怎么办。然后据我了解，第 3 步成为关键路径。
附上示意图如下：