12

在 C 中是否有一种无分支技术来计算两个无符号整数之间的绝对差？例如，给定变量 a 和 b，我希望值 2 用于 a=3、b=5 或 b=3、a=5 的情况。理想情况下，我还希望能够使用 SSE 寄存器对计算进行矢量化。

4

8 回答 8

8

有几种方法可以做到，我只提一种：

SSE4

  • 使用PMINUD和PMAXUD分隔寄存器#1 中的较大值和寄存器#2 中的较小值。
  • 减去它们。

MMX/SSE2

  • 翻转两个值的符号位，因为下一条指令只接受有符号整数比较。
  • PCMPGTD. 将此结果用作掩码。
  • 计算两者的(a-b)结果(b-a)
  • 用于POR ( PAND ( mask, a-b ), PANDN ( mask, b-a ) )选择绝对差的正确值。
于 2010-08-01T05:24:40.663 回答
5

来自tommesani.com，解决此问题的一种方法是使用两次饱和无符号减法。

由于饱和减法永远不会低于 0，因此您计算： r1 = (ab).saturating r2 = (ba).saturating

如果 a 大于 b，则 r1 将包含答案，而 r2 将为 0，反之亦然 b>a。将两个部分结果进行或运算将产生所需的结果。

根据VTUNE 用户手册，PSUBUSB/PSUBUSW 可用于 128 位寄存器，因此您应该能够通过这种方式获得大量并行化。

于 2011-07-21T18:06:08.827 回答
4 
max(i,j) - min(i,j)
(i>j)*(i-j) + (j>i)*(j-i)

您当然可以使用 SSE 寄存器，但编译器可能会为您执行此操作

于 2010-08-01T05:22:42.680 回答
3

上交所2：

似乎与 Phernost 的第二个函数的速度差不多。有时 GCC 将其安排得更快，有时会慢一些。

__m128i big = _mm_set_epi32( INT_MIN, INT_MIN, INT_MIN, INT_MIN );

a = _mm_add_epi32( a, big ); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32( b, big ); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32( a, b ); // get signed difference
__m128i mask = _mm_cmpgt_epi32( b, a ); // mask: need to negate difference?
mask = _mm_andnot_si128( big, mask ); // mask = 0x7ffff... if negating
diff = _mm_xor_si128( diff, mask ); // 1's complement except MSB
diff = _mm_sub_epi32( diff, mask ); // add 1 and restore MSB

SSSE3：

比以前稍微快一点。有很多变化取决于如何声明循环之外的东西。（例如，a使b volatile事情变得更快！这似乎是对调度的随机影响。）但这始终是最快的一个周期左右。

__m128i big = _mm_set_epi32( INT_MIN, INT_MIN, INT_MIN, INT_MIN );

a = _mm_add_epi32( a, big ); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32( b, big ); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32( b, a ); // get reverse signed difference
__m128i mask = _mm_cmpgt_epi32( b, a ); // mask: need to negate difference?
mask = _mm_xor_si128( mask, big ); // mask cannot be 0 for PSIGND insn
diff = _mm_sign_epi32( diff, mask ); // negate diff if needed

SSE4（谢谢 rwong）：

不能测试这个。

__m128i diff = _mm_sub_epi32( _mm_max_epu32( a, b ), _mm_min_epu32( a, b ) );
于 2010-08-20T00:06:48.877 回答
1

计算差值并返回绝对值

__m128i diff = _mm_sub_epi32(a, b);  
__m128i mask = _mm_xor_si128(diff, a);
mask = _mm_xor_si128(mask, b);
mask = _mm_srai_epi32(mask, 31);
diff = _mm_xor_si128(diff, mask);  
mask = _mm_srli_epi32(mask, 31);  
diff = _mm_add_epi32(diff, mask);

与使用有符号比较操作相比，这需要更少的操作，并产生更少的寄存器压力。

与以前相同的寄存器压力、2 个更多的操作、更好的依赖链分支和合并、用于 uops 解码的指令配对以及单独的单元利用率。虽然这需要加载，但可能超出缓存。在这个之后我没有想法了。

__m128i mask, diff;
diff = _mm_set1_epi32(-1<<31); // dependency branch after
a = _mm_add_epi32(a, diff); // arithmetic sign flip
b = _mm_xor_si128(b, diff); // bitwise sign flip parallel with 'add' unit
diff = _mm_xor_si128(a, b); // reduce uops, instruction already decoded
mask = _mm_cmpgt_epi32(b, a); // parallel with xor
mask = _mm_and_si128(mask, diff); // dependency merge, branch after
a = _mm_xor_si128(a, mask); // if 2 'bit' units in CPU, parallel with next
b = _mm_xor_si128(b, mask); // reduce uops, instruction already decoded
diff = _mm_sub_epi32(a, b); // result

在 Core2Duo 上为每个版本计时 200 万次迭代后，差异是无法估量的。所以选择更容易理解的。

于 2010-08-19T18:14:12.363 回答
1

以下一项或多项可能会导致无分支代码，具体取决于机器和编译器，因为条件表达式都非常简单。

我还没有通过所有的 sse 答案，但可能以下一些在矢量代码中表示；当然，以下所有内容都是可矢量化的（如果您以无符号比较开头，或者通过首先切换 msb 来伪造它。）。我认为对这个问题有一些实用的标量答案会很有帮助。

unsigned udiff( unsigned a, unsigned b )
{
      unsigned result = a-b;   // ok if a<b;
      if(a <b ) result = -result; 
      return result;
}
unsigned udiff( unsigned a, unsigned b )
{
      unsigned n =(a<b)? (unsigned)-1 : 0u;
      unsigned result = a-b;
      return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}


unsigned udiff( unsigned a, unsigned b )
{
      unsigned axb = a^b;
      if( a < b )  axb = 0;
      return (axb^b) - (axb^a);  // a-b, or b-a
}

这将适用于 x86_64（或任何 64 位临时工基本上是免费的）

unsigned udiff( unsigned a, unsigned b )
{
      unsigned n= (unsigned)( 
         (long long)((unsigned long long)a - (unsigned long long)b)>>32 
                      ); // same n as 2nd example
      unsigned result = a-b;
      return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}
于 2014-03-21T16:56:08.097 回答
0

试试这个（假设第 2 个补码，根据您要求 SSE 的事实来判断，这是可以的）：

int d = a-b;
int ad = ((d >> 30) | 1) * d;

解释：符号位（第 31 位）向下传播到第 1 位。的| 1 部分确保乘数为 1 或 -1。现代 CPU 上的乘法运算速度很快。

于 2010-08-01T05:25:56.643 回答
-1

嗯……很简单……

int diff = abs( a - b );

易于矢量化（使用 SSE3 作为）：

__m128i sseDiff = _mm_abs_epi32( _mm_sub_epi32( a, b ) );

a 和 b 是无符号整数。考虑 a=0 和 b=0xffffffff。正确的绝对差是 0xffffffff，但您的解决方案将给出 1。

于 2010-09-11T14:48:33.893 回答