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

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] 必须乘以 xpwr 才能将 a[i] 添加到该乘积中以产生结果的下一个值。有人可以向我解释一下吗？

Answer 1

术语：您可以说循环是“延迟限制”，但在分析瓶颈时，我不会说“延迟限制”或“限制”。这对我来说听起来不对。您正在测量（或通过静态性能分析计算）的是关键路径的延迟或长度，或者循环携带的依赖链的长度。（关键路径是最长的延迟链，如果它比乱序 exec 可以隐藏的时间长，则是导致 CPU 停顿的原因。）

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

第一个循环中唯一循环携带的依赖项是xpwr *= x。由于某种原因result，每次迭代都会覆盖而不读取旧值。所以每次迭代都有一些独立的工作，xpwr在那个时候从dep 链“分叉”出来。

大概这是一个错误，他们的意思是+=而不是=，或者你复制错了。这仍然不会延长整体关键路径。

result += a[i] * xpwr 有 3 个输入：

• result 来自上一次迭代。
• a[i] 假定您希望它尽早准备就绪。
• xpwr来自上一次迭代。更重要的是，之前的迭代可以立即开始计算xpwr，而不是等待之前的result.

所以你有 2 个依赖链，一个从另一个读取。加法 dep 链每一步的延迟较低，因此它最终只会等待乘法 dep 链。

跨迭代的依赖模式图

（mulsd 用于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

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