时间戳

首页 > 解决方案 > 如何使用内部函数 C++ 将 3 个加法和 1 个乘法转换为矢量化 SIMD

c++ - 如何使用内部函数 C++ 将 3 个加法和 1 个乘法转换为矢量化 SIMD

问题描述

我正在使用 2D 前缀总和（也称为 Summed-Area Table ）解决问题S。对于二维数组I（灰度图像/矩阵/等），其定义为：

S[x][y] = S[x-1][y] + S[x][y-1] - S[x-1][y-1] + I[x][y]
Sqr[x][y] = Sqr[x-1][y] + Sqr[x][y-1] - Sqr[x-1][y-1] + I[x][y]^2

计算具有两个角的子矩阵的总和，(top,left)可以(bot,right)在 O(1) 中完成：

sum = S[bot][right] - S[bot][left-1] - S[top-1][right] + S[top-1][left-1]

我的问题之一是计算所有可能的子矩阵总和，其大小为常数(bot-top == right-left == R)，然后用于计算它们的均值/方差。我已经将它矢量化为下面的形式。

lineSize是一次要处理的元素数。我选择lineSize = 16是因为 Intel CPU AVX 指令可以同时处理 8 个双精度。它可以是 8/16/32/...

#define cell(i, j, w) ((i)*(w) + (j))
const int lineSize = 16; 
const int R = 3; // any integer
const int submatArea = (R+1)*(R+1);
const double submatAreaInv = double(1) / submatArea;
void subMatrixVarMulti(int64* S, int64* Sqr, int top, int left, int bot, int right, int w, int h, int diff, double submatAreaInv, double mean[lineSize], double var[lineSize])
{
  const int indexCache = cell(top, left, w),
        indexTopLeft = cell(top - 1, left - 1, w),
        indexTopRight = cell(top - 1, right, w),
        indexBotLeft = cell(bot, left - 1, w),
        indexBotRight = cell(bot, right, w);
  
  for (int i = 0; i < lineSize; i++) {
    mean[i] = (S[indexBotRight+i] - S[indexBotLeft+i] - S[indexTopRight+i] + S[indexTopLeft+i]) * submatAreaInv;
    var[i] = (Sqr[indexBotRight + i] - Sqr[indexBotLeft + i] - Sqr[indexTopRight + i] + Sqr[indexTopLeft + i]) * submatAreaInv
         - mean[i] * mean[i];
}

如何优化上述循环以获得尽可能高的速度？可读性并不重要。我听说可以使用AVX2 和内在函数来完成，但我不知道如何。

编辑：CPU是i7-7700HQ，kabylake = skylake family

编辑2：忘了提到lineSize, R, ...已经是 const

标签： c++simdintrinsicsavxavx2

解决方案

您的编译器可以为您生成 AVX/AVX2/AVX-512 指令，但您需要：

  1. 编译时选择最新的可用架构。例如，对于 GCC，您可能会说-march=skylake如果您知道您的代码将在 Skylake 及更高版本上运行，但不需要支持较旧的 CPU。没有它，就无法生成 AVX 指令。
  2. 将restrict或添加__restrict到您的指针输入以告诉编译器它们不重叠。这适用于 S 和 Sqr，以及 mean 和 var（这两个对具有相同的类型，因此编译器假定它们可能重叠，但您知道它们不会重叠）。
  3. 确保您的数据“过度对齐”。例如，如果您希望编译器使用 256 位 AVX2 指令，您应该将数组对齐到 256 位。有几种方法可以做到这一点，例如使用对齐方式制作 typedef，或使用alignas()or std::assume_aligned()（在 C++20 之前作为 GCC 属性提供）。关键是您需要编译器知道 S、Sqr、mean 和 var 与您的目标架构上可用的最大 SIMD 向量大小对齐，这样它就不必生成尽可能多的修复代码。
  4. 尽可能使用constexpr，例如 lineSize。

最重要的是，配置文件以在您进行更改时比较性能，并查看生成的代码（例如g++ -S），看看它是否看起来像您想要的那样。

推荐阅读