我正在处理一个使用2D前缀sum的问题，也称为Summed-Area表s。 对于2D阵列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
计算有两个角的子矩阵（上，左）和（bot，右）的和可以在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系列
编辑2:忘了提到linesize，R，...已经是常量
您的编译器可以为您生成AVX/AVX2/AVX-512指令，但您需要:
-march=Skylake。 没有这一点，就无法生成AVX指令。restrict或__restrict添加到您的指针输入中，以告诉编译器它们不重叠。 这适用于S和Sqr，以及mean和var（这两个对具有相同的类型，因此编译器假定它们可能重叠，但您知道它们并不重叠）。alignas()或std::assume_aligned()（在C++20之前作为GCC属性可用）。 关键是您需要编译器知道S，Sqr，mean和var与目标体系结构上可用的最大SIMD向量大小对齐，这样它就不必生成那么多的修正代码。constexpr，如Linesize.最重要的是，配置文件可以在进行更改时比较性能，并查看生成的代码（例如g++-s)，看看它是否符合您的要求。
我认为由于求和的依赖性，使用SIMD不能有效地执行这种类型的求和。
相反，您可以以不同的方式进行计算，这可以通过SIMD进行简单的优化:
你可以对求和和平方进行同样的操作。
唯一的问题是您需要额外的内存，而这种类型的计算需要更多的内存访问。 额外的内存可能是次要的事情，但通过以缓存友好的方式存储临时数据（行的总和），可能可以改善更多的内存访问。 你可能需要尝试一下这个。