旭穹の陋室

吞吐量计算

针对延迟的优化通常与针对吞吐量的优化大不相同：

• 当优化数据结构查询算法、小型一次性算法或分支算法时，你需要查询所用指令的延迟，在脑海中构建计算的执行图，然后尝试重新组织它，使关键路径更短。
• 在优化热循环（hot loops）和大型数据集算法时，你需要查询所用指令的吞吐量，计算每次迭代每个指令的使用次数，确定其中哪一个是瓶颈，然后尝试重组循环，以减少其使用频率。

最后一条建议仅适用于数据并行(data-parallel)循环，其中每次迭代都完全独立于前一次迭代。当连续迭代之间存在某种相互依赖性时，由于下一次迭代正在等待上一次迭代完成，因此可能存在由数据冒险导致的流水线停滞。

作为一个简单的例子，考虑对数组求和：

int s = 0;

for (int i = 0; i < n; i++)
    s += a[i];

让我们暂时假设编译器不会对这个循环进行矢量化，不存在内存带宽问题，并且循环是展开的，这样我们就不会因需要维护循环变量而支付任何额外的成本。在这种情况下，计算变得非常简单：

int s = 0;
s += a[0];
s += a[1];
s += a[2];
s += a[3];
// ...

我们能以多快的速度计算呢？每个元素正好需要一个周期，因为我们每次迭代都需要一个周期来add一个值到s。内存读取的延迟并不关键，因为CPU可以预取内存。

但速度可以比这更快。在我的CPU（ZEN 2）上，add的吞吐量为2[1]^{[1]}[1]，这意味着我们可以在每个时钟周期中执行两条add指令。但是上述代码做不到：当s被用来累加第iii个元素时，至少一个周期内它不能用于累加第i+1i+1i+1个元素。

解决方案是使用两个累加器，将奇数和偶数元素分别相加：

int s0 = 0, s1 = 0;
s0 += a[0];
s1 += a[1];
s0 += a[2];
s1 += a[3];
// ...
int s = s0 + s1;

现在，我们的超标量CPU可以同时执行这两个“线程”，我们的计算不再有任何限制吞吐量的关键路径。

如果一条指令的延迟为xxx，吞吐量为yyy，那么您将需要使用x⋅yx\cdot yx⋅y个累加器来使计算饱和。这也意味着您需要x⋅yx\cdot yx⋅y个逻辑寄存器来保持其值，这是CPU设计的重要考虑因素，即限制高延迟指令的最大可用执行单元数量。

此技术主要用于SIMD，而不用于标量代码。您可以归纳上面的代码，来获得并比编译器更快地求和运算或其他reduction运算。

一般来说，在优化循环时，通常只有一个或几个执行端口（execution ports）要充分利用，然后围绕它们设计其余的循环。由于不同的指令可能使用不同的端口集，因此并不总是能搞清楚哪一个会被过度使用。在这种情况下，机器代码分析器非常有助于发现小型汇编循环的瓶颈。

[1] 寄存器-寄存器add指令的吞吐量是4，但由于我们是从内存中读取其第二个操作数，因此它受到访存指令mov吞吐量的限制，mov的吞吐量在Zen 2上为2。