12

C では、2 つの unsigned int 間の絶対差を計算するブランチレス手法はありますか? たとえば、変数 a と b が与えられた場合、a=3、b=5、または b=3、a=5 の場合は値 2 が必要です。理想的には、SSE レジスターを使用して計算をベクトル化できるようにしたいと考えています。

4

8 に答える 8

8

方法はいくつかありますが、一つだけ挙げておきます。

SSE4

  • PMINUDとを使用しPMAXUDて、レジスタ #1 の大きい値とレジスタ #2 の小さい値を区切ります。
  • それらを引きます。

MMX/SSE2

  • 次の命令は符号付き整数の比較のみを受け入れるため、2 つの値の符号ビットを反転します。
  • PCMPGTD. この結果をマスクとして使用します。
  • (a-b)との両方の結果を計算します。(b-a)
  • POR ( PAND ( mask, a-b ), PANDN ( mask, b-a ) )絶対差の正しい値を選択するために使用します。
于 2010-08-01T05:24:40.663 に答える
5

tommesani.comによると、この問題の解決策の 1 つは、飽和符号なし減算を 2 回使用することです。

飽和減算は 0 を下回らないため、次のように計算します。 r1 = (ab).saturating r2 = (ba).saturating

a が b より大きい場合、r1 には答えが含まれ、r2 は 0 になり、b>a の場合はその逆になります。2 つの部分的な結果を一緒に OR すると、目的の結果が得られます。

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

SSE2:

フェルノストの第2機能と同程度の速さのようです。GCC は、1 サイクル速くなるようにスケジュールすることもあれば、少し遅くなるようにスケジュールすることもあります。

__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:

以前よりもわずかに速くなりました。ループの外側の宣言方法によって、さまざまなバリエーションがあります。(たとえば、makeaとb volatilemake は物事をより速くします! スケジューリングに対するランダムな影響のようです。) しかし、これは一貫して 1 サイクルほど最速です。

__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 (thx 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);

これにより、署名された比較操作を使用する場合よりも操作が1つ少なくなり、レジスターの圧力が少なくなります。

以前と同じ量のレジスタープレッシャー、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

条件式はすべて非常に単純であるため、マシンとコンパイラによっては、以下の 1 つ以上がブランチレス コードになる可能性があります。

すべての sse 回答を確認したわけではありませんが、以下のいくつかはベクトル コードで表されている可能性があります。確かに、以下のすべてはベクトル化可能です (最初に unsigned 比較がある場合、または最初に 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

これを試してください（SSEを求めているという事実から判断すると、2番目の補数を想定しています）：

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 に答える