如何根据条件（屋顶线模型）有效地向量化多项式计算

Question

我想对长度在 50 到 3000 之间的向量应用小次 (2-5) 的多项式，并尽可能高效地执行此操作。例子：比如我们可以取函数：(1+x^2)^3，当x>3，0当x<=3。对于双元素向量，这样的函数将执行 100k 次。每个向量的大小可以是 50 到 3000 之间的任何值。

一个想法是使用 Eigen： Eigen::ArrayXd v; 然后简单地应用一个仿函数： v.unaryExpr([&](双 x) {return x>3 ? std::pow((1+x*x), 3.00) : 0.00;});

尝试使用 GCC 9 和 GCC 10，我发现这个循环没有被向量化。我手动对其进行矢量化，结果发现增益比我预期的小得多 (1.5 倍)。我还用逻辑 AND 指令替换了条件，基本上执行两个分支并在 x<=3 时将结果清零。我认为收益主要来自于没有分支预测错误。

一些注意事项 有多种因素在起作用。首先，我的代码中有 RAW 依赖项（使用内部函数）。我不确定这如何影响计算。我用 AVX2 编写了我的代码，所以我期望获得 4 倍的增益。我认为这起到了作用，但我不能确定，因为 CPU 有乱序处理。另一个问题是我不确定我尝试编写的循环的性能是否受内存带宽的限制。

问题我如何确定内存带宽或管道危害是否正在影响此循环的实现？我在哪里可以学习更好地矢量化此循环的技术？在 Eigenr MSVC 或 Linux 中是否有好的工具？我使用的是 AMD CPU 而不是 Intel。

Answer 1

您可以使用 -fno-trapping-math 修复 GCC 遗漏的优化，这实际上应该是默认设置，因为 -ftrapping-math 甚至不能完全工作。它 auto-vectorizes 使用该选项就好了：https://godbolt.org/z/zfKjjq.

#include <stdlib.h>

void foo(double *arr, size_t n) {
    for (size_t i=0 ; i<n ; i++){
        double &tmp = arr[i];
        double sqrp1 = 1.0 + tmp*tmp;
        tmp = tmp>3 ? sqrp1*sqrp1*sqrp1 : 0;
    }
}

它避免了三元组一侧的乘法，因为它们可能引发 C++ 抽象机不会引发的 FP 异常。

你希望用三元之外的立方体编写它应该让 GCC auto-vectorize，因为 none 的 FP 数学运算在源代码中是有条件的。但它实际上并没有帮助：https://godbolt.org/z/c7Ms9G GCC's default -ftrapping-math still decides to branch on the input to avoid all the FP computation, potentially not raising an overflow (to infinity) exception that the C++ abstract machine would have raised. Or invalid if the input was NaN. This is the kind of thing I meant about -ftrapping-math not working. (related: )

Clang也没有问题：https://godbolt.org/z/KvM9fh 当 FMA 可用时，我建议使用 clang -O3 -march=native -ffp-contract=fast 跨语句获取 FMA。

（在这种情况下， -ffp-contract=on 足以在那个表达式中收缩 1.0 + tmp*tmp，但如果您需要避免这种情况，例如 Kahan 求和，则不能跨语句。clang 默认值显然是-ffp-contract=off, 给出单独的 mulpd 和 addpd)

当然，您会希望避免 std::pow 具有较小的整数指数。编译器可能不会将其优化为仅 2 次乘法，而是调用完整的 pow 函数。

如何根据条件（屋顶线模型）有效地向量化多项式计算

How to efficiently vectorize polynomial computation with condition (roofline model)

eigen

intrinsics

avx2

auto-vectorization

memory-bandwidth