問題
x86SIMD命令を使用して、整数のセットのレジスタ内重複排除に計算上実行可能なアプローチはありますか？
例
4タプルレジスタR1={3、9、2、9}があり、レジスタR2 = {3、9、2、NULL}を取得したいとします。
制限
安定性。入力順序の保持は重要ではありません。
出力。ただし、削除された値/ NULLは、レジスタの最初または最後、あるいはその両方にある必要があります。
ある特定の出力フォーマットを生成することがわかっている場合、それは明らかにボーナスです。事実上0（ゼロ）を意味するNULLを想定してください。
一般性。重複がないことを許容できる必要があり、この場合、入力レジスタと同等の出力を生成します。
命令セット。次のいずれかまたはすべてのソリューションを探しています。SSE2-SSSE3; SSE4.x; AVX-AVX2
提案されたソリューションは、常にすべての一意の要素を最初の発生順に出力の下部に配置します。上位部分はゼロになります。LUTを変更することで、配置戦略を簡単に変更できます。要素を上位に配置するか、順序を逆にします。
static __m128i *const lookup_hash = (__m128i*) &lookup_hash_chars[0][0];
static inline __m128i deduplicate4_ssse3(__m128i abcd) {
__m128i bcda = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(0, 3, 2, 1));
__m128i cdab = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(1, 0, 3, 2));
uint32_t mask1 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, bcda));
uint32_t mask2 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, cdab));
uint32_t maskFull = (mask2 << 16U) + mask1;
//Note: minimal perfect hash function here
uint32_t lutIndex = (maskFull * 0X0044CCCEU) >> 26U;
__m128i shuf = lookup_hash[lutIndex];
return _mm_shuffle_epi8(abcd, shuf);
}
完全なコード（テストあり）はこちらから入手できます。
また、5つのコンパレータのネットワークをソートし、続いて連続する要素をシリアル比較することにより、単純なスカラーソリューションを実装しました。私は2つのプロセッサでMSVC2013を使用していました：Core 2 E4700（Allendale、2.6 Ghz）とCore i7-3770（Ivy Bridge、3.4 Ghz）。2^29回の呼び出しのタイミングは次のとおりです。
// Allendale
SSE: time = 3.340 // ~16.2 cycles (per call)
Scalar: time = 17.218 // ~83.4 cycles (per call)
// Ivy Bridge
SSE: time = 1.203 // ~ 7.6 cycles (per call)
Scalar: time = 11.673 // ~73.9 cycles (per call)
結果は2種類の要素で構成されている必要があることに注意してください。
ただし、必要なシャッフルマスクは、実行時に非常に複雑な方法で決定されます。すべてのSSE命令は、1つを除いて、即時（つまりコンパイル時定数）のシャッフルマスクのみを処理できます。SSSE3に_mm_shuffle_epi8固有のものです。シャッフルマスクをすばやく取得するために、すべてのマスクはルックアップテーブルに格納され、いくつかのビットマスクまたはハッシュによってインデックスが付けられます。
特定の入力ベクトルのシャッフリングマスクを取得するには、その中の等しい要素に関する十分な情報を収集する必要があります。重複排除の方法を決定するには、要素のどのペアが等しいかを知るだけで十分であることに注意してください。それらをさらに並べ替える場合は、さまざまな要素が互いにどのように比較されるかを知る必要があります。これにより、情報量が増加し、続いてテーブルが検索されます。そのため、ここでは並べ替えずに重複排除を示します。
したがって、XMMレジスタには4つの32ビット要素があります。合計6組で構成されています。一度に比較できる要素は4つだけなので、少なくとも2つの比較が必要です。実際、2つのXMM比較を行うのは簡単なので、要素の各ペアは少なくとも1回は比較されます。その後、比較の16ビットビットマスクを使用して抽出し_mm_movemask_epi8、それらを単一の32ビット整数に連結できます。各4ビットブロックには確かに同じビットが含まれ、最後の2つの4ビットブロックは必要ないことに注意してください（これらは過度の比較に対応します）。
理想的には、このビットマスクから、コンパイル時の既知の位置にある正確に6ビットを抽出する必要があります。_pext_u32これは、BMI2命令セットからの組み込みで簡単に実現できます。その結果、6ビットを含む範囲[0..63]の整数があり、各ビットは、対応する要素のペアが等しいかどうかを示します。次に、事前に計算された64エントリのルックアップテーブルからシャッフルマスクをロードし、を使用して入力ベクトルをシャッフルします_mm_shuffle_epi8。
残念ながら、BMI命令は非常に新しく（Haswell以降）、私にはありません=）それを取り除くために、64個の有効なビットマスクすべてに対して非常に単純で高速な完全なハッシュ関数を作成することができます（思い出してください）そのビットマスクは32ビットです）。クラス内のハッシュ関数の場合、f(x) = (a * x) >> (32-b)通常、2倍または3倍のメモリオーバーヘッドで、かなり小さい完全なハッシュを作成することが可能です。このケースは特殊であるため、最小の完全なハッシュ関数を作成して、ルックアップテーブルに最小の64エントリ（つまり、サイズ= 1 KB）を含めることができます。
同じアルゴリズムは、8つの要素（たとえば、XMMレジスタの16ビット整数）では実行できません。これは、要素のペアが28あるため、ルックアップテーブルに少なくとも2^28のエントリが含まれている必要があることを意味します。
YMMレジスタの64ビット要素にこのアプローチを使用することも問題があります。_mm256_shuffle_epi8組み込みは、2つの別々の128ビットシャッフルを実行するだけなので、役に立ちません（レーン間でシャッフルすることはありません）。_mm256_permutevar8x32_epi32組み込みは32ビットブロックの任意のシャッフルを実行しますが、ゼロを挿入することはできません。これを使用するには、LUTに多数の一意の要素も格納する必要があります。次に、レジスタの上位部分に手動でゼロを入力する必要があります。
ビット抽出や完全なハッシュ関数にBMI2を使用する必要はなく、_mm_movemask_ps32ビットマスクを抽出するために使用するだけでよいことに気付きました。このアプローチでは、INTとFPの計算が混在しているため、レイテンシの問題が発生する可能性がありますが、実際にはより高速に機能します。
static __m128i *const lookup_direct_offset = lookup_direct - 0xC0U;
static inline __m128i deduplicate4_ssse3_direct(__m128i abcd) {
__m128i bcda = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(0, 3, 2, 1));
__m128i cdcd = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(3, 2, 3, 2));
uint32_t mask1 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpeq_epi32(abcd, bcda)));
uint32_t mask2 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpeq_epi32(abcd, cdcd)));
uint32_t maskFull = 16U * mask2 + mask1;
//Note: use index directly
uint32_t lutIndex = maskFull;
__m128i shuf = lookup_direct_offset[lutIndex];
return _mm_shuffle_epi8(abcd, shuf);
}
完全なコードも更新されます。これにより、パフォーマンスがわずかに向上します。
// Ivy Bridge
new: Time = 1.038 (782827520) // ~ 6.6 cycles (per call)
old: Time = 1.169 (782827520) // ~ 7.4 cycles (per call)
素朴な解決策
Max（）操作に基づく粗い擬似コード。コメントは、最初の反復のデータを追跡します。
A = RIN //{3, 9, 2, 9}
For i = 0 .. 3:
B = Rotate(A, 1) //{9, 2, 9, 3}
C = Rotate(A, 2) //{2, 9, 3, 9}
D = Rotate(A, 3) //{9, 3, 9, 2}
RMAX = Max(A,B) //{9, 9, 9, 9}
RMAX = Max(RMAX, C) //{9, 9, 9, 9}
RMAX = Max(RMAX, D) //{9, 9, 9, 9}
ROUT[i] = RMAX[0] //ROUT = {9, null, null, null}
TMP = A
MASK = Equality(RMAX, TMP) //MASK = {0, 1, 0, 1}
MASK = Invert(MASK) //MASK = {1, 0, 1, 0}
Clear(A)
A = MoveMasked(TMP, MASK) //A = {3, null, 2, null}
いくつかの考え：
A = RIN //{3, 9, 2, 9}
B = Rotate(A, 1) //{9, 2, 9, 3}
C = Rotate(A, 2) //{2, 9, 3, 9}
D = Rotate(A, 3) //{9, 3, 9, 2}
maskA = cmpeq(A,B) //{0, 0, 0, 0}
maskB = cmpeq(A,C) //{0, -1, 0, -1}
maskC = cmpeq(A,D) //{0, 0, 0, 0}
indexA = horSum( { 1,2,4,8 } * maskA ) // 0
indexB = horSum( { 1,2,4,8 } * maskB ) // 10
indexC = horSum( { 1,2,4,8 } * maskC ) // 0
// The problem is this function here
// Of the 4096 possible indexABC only a subset will occur
// Based on an enumeration of all possible indexes a pattern
// for an lookup table could possibly be found
shuffleConst = lookupShuffle( indexA, indexB, indexC )
shuffle(A, shuffleConst)