c-在这种情况下，矢量化是否有利可图

Question

我将内核分解为几个循环，以便在之后对每个循环进行矢量化。其中一个循环看起来像：

int *array1; //Its size is "size+1";
int *array2; //Its size is "size+1";
//All positions of array1 and array2 are set to 0 here;
int *sArray1 = array1+1; //Shift one position so I start writing on pos 1
int *sArray2 = array2+1; //Shift one position so I start writing on pos 1
int bb = 0;
for(int i=0; i<size; i++){
   if(A[i] + bb > B[i]){
      bb = 1;
      sArray1[i] = S;
      sArray2[i] = 1;
   }
   else
      bb = 0;
}

请注意循环携带的依赖关系，在bb中-每个比较都取决于bb的值，该值在上一次迭代中进行了修改。

我的想法：

• 我对某些情况完全有把握。例如，当A[i]已经大于B[i]时，我不需要知道bb从上一次迭代中携带了什么值
• 当A[i]等于B[i]时，我需要知道bb从上一次迭代中携带了什么值。然而，我也需要解释当这种情况发生在两个连续的位置；当我开始构思这些案例时，这些案例似乎变得过于复杂，矢量化没有效果

从本质上讲，我想知道这是否可以以有效的方式进行矢量化，或者在不进行任何矢量化的情况下运行它是否更好。

Answer 1

您可能不想在单个元素上进行迭代，而是在块上进行循环（其中块由生成相同bb的所有元素定义）。

可以对块边界的搜索进行矢量化（可能是手动使用编译器特定的SIMD intrinics）。对于bb＝1的单个块要采取的操作也可以被矢量化。循环转换如下：

size_t i_chunk_start = 0, i_chunk_end;
int bb_chunk = A[0] > B[0] ? 1 : 0;
while (i_chunk_start < isize) {
  if(bb_chunk) {
    /* find end of current chunk */
    for (i_chunk_end = i_chunk_start + 1; i_chunk_end < isize; ++i_chunk_end) {
      if(A[i_chunk_end] < B[i_chunk_end]) {
        break;
      }
    }
    /* process current chunk */
    for(size_t i = i_chunk_start; i < i_chunk_end; ++i) {
      sArray1[i] = S;
      sArray2[i] = 1;
    }
    bb_chunk = 0;
  } else {
    /* find end of current chunk */
    for (i_chunk_end = i_chunk_start + 1; i_chunk_end < isize; ++i_chunk_end) {
      if(A[i_chunk_end] > B[i_chunk_end]) {
        break;
      }
    }
    bb_chunk = 1;
  }
  /* prepare for next chunk */
  i_chunk_start = i_chunk_end;
 }

现在，每个内部循环（全部用于循环）都可能被矢量化。

这种方式的矢量化是否优于非矢量化取决于块平均是否具有足够的长度。你只能通过基准测试来发现。

Answer 2

循环体的效果取决于两个条件：

• A[i] > B[i]
• A[i] + 1 > B[i]

它们的计算可以很容易地向量化。假设int有32个比特，并且矢量化指令一次处理4个int值，则每个矢量化迭代有8个比特（每个条件有4个比特）。

您可以通过_mm_movemask_epi8从SSE寄存器中获取这些位。它在字节上工作而在ints上不工作，这有点不方便，但您可以通过适当的shuffle来处理它。

然后，使用8位作为LUT（256个条目）的地址，LUT存储4位掩码。这些掩码可以用于使用_mm_maskmoveu_si128有条件地将元素存储到目的地。

我不确定这样一个复杂的程序是否值得——它只需要在速度上提高x4就需要花费很多时间。也许通过单独检查决策位来构建掩码更好。但是，在任何情况下，矢量化比较和存储似乎都是值得的。