低效的内存访问模式和不规则跨度访问

Question

我正在尝试优化这个函数：

bool interpolate(const Mat &im, float ofsx, float ofsy, float a11, float a12, float a21, float a22, Mat &res)
{         
   bool ret = false;
   // input size (-1 for the safe bilinear interpolation)
   const int width = im.cols-1;
   const int height = im.rows-1;
   // output size
   const int halfWidth  = res.cols >> 1;
   const int halfHeight = res.rows >> 1;
   float *out = res.ptr<float>(0);
   const float *imptr  = im.ptr<float>(0);
   for (int j=-halfHeight; j<=halfHeight; ++j)
   {
      const float rx = ofsx + j * a12;
      const float ry = ofsy + j * a22;
      #pragma omp simd
      for(int i=-halfWidth; i<=halfWidth; ++i, out++)
      {
         float wx = rx + i * a11;
         float wy = ry + i * a21;
         const int x = (int) floor(wx);
         const int y = (int) floor(wy);
         if (x >= 0 && y >= 0 && x < width && y < height)
         {
            // compute weights
            wx -= x; wy -= y;
            int rowOffset = y*im.cols;
            int rowOffset1 = (y+1)*im.cols;
            // bilinear interpolation
            *out =
                (1.0f - wy) *
                ((1.0f - wx) * 
                imptr[rowOffset+x] +
                wx * 
                imptr[rowOffset+x+1]) +
                (       wy) *
                ((1.0f - wx) * 
                imptr[rowOffset1+x] + 
                wx *
                imptr[rowOffset1+x+1]);
         } else {
            *out = 0;
            ret =  true; // touching boundary of the input            
         }
      }
   }
   return ret;
}

我正在使用Intel Advisor进行优化，即使内部的for已经矢量化，Intel Advisor仍会检测到低效的内存访问模式：

• 60%的单位/零步幅访问
• 40%的不规则/随机步幅访问

特别地，在以下三条指令中有4个gather（不规则）访问：

据我理解，gather访问的问题在于所访问的元素是a[b]类型的，其中b是不可预测的。这似乎是imptr[rowOffset+x]的情况，其中rowOffset和x都是不可预测的。

同时，我看到了这个Vertical Invariant，这应该发生（再次阐述，从我的理解），当通过恒定偏移量访问元素时。但实际上，我不知道这个恒定偏移量在哪里。

所以我有3个问题：

1. 我对gather访问的问题理解正确吗？
2. 垂直不变访问呢？我对这一点不太确定。
3. 最后，我该如何改进/解决这里的内存访问问题？

使用以下标志编译：icpc 2017 update 3。

INTEL_OPT=-O3 -ipo -simd -xCORE-AVX2 -parallel -qopenmp -fargument-noalias -ansi-alias -no-prec-div -fp-model fast=2 -fma -align -finline-functions
INTEL_PROFILE=-g -qopt-report=5 -Bdynamic -shared-intel -debug inline-debug-info -qopenmp-link dynamic -parallel-source-info=2 -ldl

- cplusplusuberalles

---

我唯一能推荐的是确保你的im矩阵是32或64字节对齐，以确保你没有额外的缓存未命中 - 以确保imptr [rowOffset + x]始终在同一个缓存行上，无论x的值如何（在矩阵的范围内）。 - xaxxon

@xaxxon，感谢您的建议。正如您所看到的，我是simd的新手，所以我有几个关于这个主题的问题要问您：32/64字节对齐是与架构相关的，对吗？那么它是否会从AVX2和AVX-512架构中发生变化？我使用AVX2进行调试和矢量化评估，而使用AVX-512（KNL机器）进行性能评估。 - cplusplusuberalles

啊，是的，臭名昭著的“按回车键开始新行注释”的注释 :) 你不能只是按回车键，你必须执行以下步骤： - xaxxon

@xaxxon 我笑得很开心 - cplusplusuberalles

你需要确保你的数据结构不跨越缓存行。这取决于架构，但64字节似乎是现代CPU上一个相当普遍的大小。任何时候进行这种级别的调整都是系统相关的。https://software.intel.com/en-us/articles/intel-xeon-phi-core-micro-architecture - xaxxon

Grazie@xaxxon，感谢您的澄清。您能否看一下这个问题？http://stackoverflow.com/questions/43718018/how-do-i-align-cvmat-for-avx-512-avx2-architectures - cplusplusuberalles

Answer 1

将您的代码矢量化（SIMD化）并不会自动使您的访问模式变得更好（或更差）。为了最大化矢量化代码的性能，您必须尝试在代码中拥有“单位跨度”（也称连续、线性、跨度-1）内存访问模式。或者至少是“可预测”的规则跨度-N，其中N理想情况下应该是相对较低的值。

如果没有引入这样的规律性——您保持您的内存LOAD/STORE操作部分顺序（非并行）在指令级别上。因此，每次您想要进行“并行”加法/乘法等操作时，您都必须进行“非并行”原始数据元素的“收集”。

在您的情况下，似乎存在规则跨度-N（逻辑上）——这可以从代码片段和Advisor MAP输出（右侧面板）中看出。 “垂直不变”——意味着您有时会在迭代之间访问相同的内存位置。“单位跨度”意味着在其他情况下，您具有逻辑上连续的内存访问。

然而，代码结构很复杂：您在循环体中有if语句，有复杂的条件和浮点——>整数（简单，但仍然）转换。

因此编译器必须使用最通用和最低效的方法（收集）“以防万一”，结果你的物理、实际内存访问模式（来自编译器代码生成）是不规则的“GATHER”，但逻辑上你的访问模式是规则的（不变或单元跨度）。

解决方案可能不是很容易，但我会尝试以下几点：

1. 如果算法允许，请考虑排除if语句。有时可以通过将循环拆分为几个循环来实现这一点。

2. 尝试摆脱半浮点归纳变量，floor等。尝试使它们成为整数并使用“正统”形式（对于（i）array [super-simple-expression（i）] = something）。

3. 尝试使用pragma simd的线性子句告知编译器实际上存在单元跨度。

- zam