c-饱和基质-AVX或SSE4.2

Question

我正在提高程序（C）的性能，但我无法获得更好的执行时间来改善最"昂贵"的循环。

如果无符号长整型数组的每个元素大于零，我必须从该元素中减去1。

循环是：

unsigned long int * WorkerDataTime;
...
for (WorkerID=0;WorkerID<WorkersON;++WorkerID){
    if(WorkerDataTime[WorkerID] > 0) WorkerDataTime[WorkerID]-=1;
}

我试试这个：

for (WorkerID=0;WorkerID<WorkersON;++WorkerID){
    int rest = WorkerDataTime[WorkerID] > 0;
    WorkerDataTime[WorkerID] = WorkerDataTime[WorkerID] - rest;
}

但执行时间相似。

问题：是否有任何内部指令（SSE4.2、AVX…）可以直接执行此操作（我使用的是gcc 4.8.2）

我知道使用char或short元素是可能的。（_mm_subs_epi8和_mm_sub_epi16），并且我不能使用AVX2。

谢谢。

Answer 1

使用SSE4可以使用三条指令。这是一个处理整个数组的代码，递减所有不为零的无符号整数：

void clampedDecrement_SSE (__m128i * data, size_t count)
{
  // processes 2 elements each, no checks for alignment done.
  // count must be multiple of 2.
  size_t i;
  count /= 2;
  __m128i zero = _mm_set1_epi32(0);
  __m128i ones = _mm_set1_epi32(~0);
  for (i=0; i<count; i++)
  {
    __m128i values, mask;
    // load 2 64 bit integers:
    values = _mm_load_si128 (data);
    // compare against zero. Gives either 0 or ~0 (on match)
    mask   = _mm_cmpeq_epi64 (values, zero);
    // negate above mask. Yields -1 for all non zero elements, 0 otherwise:
    mask   = _mm_xor_si128(mask, ones);
    // now just add the mask for saturated unsigned decrement operation:
    values = _mm_add_epi64(values, mask);
    // and store the result back to memory:
   _mm_store_si128(data,values);
   data++;
  }
}

有了AVX2，我们可以改进这一点，一次处理4个元素：

void clampedDecrement (__m256i * data, size_t count)
{
  // processes 4 elements each, no checks for alignment done.
  // count must be multiple of 4.
  size_t i;
  count /= 4;
  // we need some constants:
  __m256i zero = _mm256_set1_epi32(0);
  __m256i ones = _mm256_set1_epi32(~0);
  for (i=0; i<count; i++)
  {
    __m256i values, mask;
    // load 4 64 bit integers:
    values = _mm256_load_si256 (data);
    // compare against zero. Gives either 0 or ~0 (on match)
    mask   = _mm256_cmpeq_epi64 (values, zero);
    // negate above mask. Yields -1 for all non zero elements, 0 otherwise:
    mask   = _mm256_xor_si256(mask, ones);
    // now just add the mask for saturated unsigned decrement operation:
    values = _mm256_add_epi64(values, mask);
    // and store the result back to memory:
   _mm256_store_si256(data,values);
   data++;
  }
}

编辑：添加SSE代码版本。

Answer 2

除非您的CPU有XOP，否则没有有效的方法来比较无符号64位整数。

我从Agner Fog的矢量类库中撕下了以下内容。这显示了如何比较无符号64位整数。

static inline Vec2qb operator > (Vec2uq const & a, Vec2uq const & b) {
#ifdef __XOP__  // AMD XOP instruction set
    return Vec2q(_mm_comgt_epu64(a,b));
#else  // SSE2 instruction set
    __m128i sign32  = _mm_set1_epi32(0x80000000);          // sign bit of each dword
    __m128i aflip   = _mm_xor_si128(a,sign32);             // a with sign bits flipped
    __m128i bflip   = _mm_xor_si128(b,sign32);             // b with sign bits flipped
    __m128i equal   = _mm_cmpeq_epi32(a,b);                // a == b, dwords
    __m128i bigger  = _mm_cmpgt_epi32(aflip,bflip);        // a > b, dwords
    __m128i biggerl = _mm_shuffle_epi32(bigger,0xA0);      // a > b, low dwords copied to high dwords
    __m128i eqbig   = _mm_and_si128(equal,biggerl);        // high part equal and low part bigger
    __m128i hibig   = _mm_or_si128(bigger,eqbig);          // high part bigger or high part equal and low part bigger
    __m128i big     = _mm_shuffle_epi32(hibig,0xF5);       // result copied to low part
    return  Vec2qb(Vec2q(big));
#endif
}

因此，如果您的CPU支持XOP，那么您应该尝试使用-mxop进行编译，并查看循环是否已向量化。

编辑：如果GCC没有像你想要的那样矢量化，并且你的CPU有XOP，你可以做

for (WorkerID=0; WorkerID<WorkersON-1; workerID+=2){
    __m128i v = _mm_loadu_si128((__m128i*)&WorkerDataTime[workerID]);
    __m128i cmp = _mm_comgt_epu64(v, _mm_setzero_si128());
    v = _mm_add_epi64(v,cmp);
    _mm_storeu_si128((__m128i*)&WorkerDataTime[workerID], v);
}
for (;WorkerID<WorkersON;++WorkerID){
    if(WorkerDataTime[WorkerID] > 0) WorkerDataTime[WorkerID]-=1;
}

使用-mxop编译并包含#include <x86intrin.h>。

编辑：正如Nils-Pipenbrinck所指出的，如果你没有XOP，你可以使用_mm_xor_si128:再执行一条指令

for (WorkerID=0; WorkerID<WorkersON-1; WorkerID+=2){
    __m128i v = _mm_loadu_si128((__m128i*)&WorkerDataTime[workerID]);
    __m128i mask = _mm_cmpeq_epi64(v,_mm_setzero_si128());
    mask = _mm_xor_si128(mask, _mm_set1_epi32(~0));
    v= _mm_add_epi64(v,mask);
    _mm_storeu_si128((__m128i*)&WorkerDataTime[workerID], v);
}
for (;WorkerID<WorkersON;++WorkerID){
    if(WorkerDataTime[WorkerID] > 0) WorkerDataTime[WorkerID]-=1;
}

编辑：根据Stephen Canon的评论，我了解到有一种更有效的方法可以使用SSE4.2:中的pcmpgtq指令来比较一般的64位无符号整数

__m128i a,b;
__m128i sign64 = _mm_set1_epi64x(0x8000000000000000L);
__m128i aflip = _mm_xor_si128(a, sign64);
__m128i bflip = _mm_xor_si128(b, sign64);
__m128i cmp = _mm_cmpgt_epi64(aflip,bflip);