異なる値で4つの整数をシフトSIMD

Question

SSEでは、パックされた整数を可変量シフトする方法は提供されていません（AVX以上の命令を使用できます）。あなたは一様なシフトしか行うことができません。私がベクトルの各整数に対して達成しようとしている結果はこれです。

i[0] = i[0] & 0b111111; 
i[1] = (i[1]>>6) & 0b111111; 
i[2] = (i[2]>>12) & 0b111111; 
i[3] = (i[3]>>18) & 0b111111; 

本質的に、各整数の6ビットの異なるグループを分離しようとしています。

だから最適な解決策は何ですか？

私が考えたこと： 可変の右シフトと、可変の左シフトと一様な右シフトをシミュレートすることができます。私はパックされた整数にそれぞれ異なる量を掛けることを考えました（したがって、左シフトをシミュレートします）。それで結果があれば、一様な右シフトをして答えを得ることができます。これは、乗算に使用する特定の演算子の問題は、待ち時間が残念であり（残念ながら10サイクルあります）、結果を待たなければならないと考えられます。この特定の結果が次の結果に依存するためです。指示。全体的に私が思う方法は、解凍し、スカラー命令を使ってシフトし、その後ベクトルを再パックするブルートフォースの方法より少し速いと思います。これは約20サイクルかかると思います。

Answer 1

この部分はどのような種類の依存関係チェーンですか？アンロールとインターリーブができるので、2つのベクトルが一度に飛行していますか？並行する2つの長いデポチェインは、1つの長いデプレッションチェーンよりもはるかに優れています。長い間、順序のずれたウィンドウは次のループの繰り返しで次のデターチェーンを見ることができません。

---

それは（どこでa variable-shiftを使用することができます）ハスウェル以降のCPU上で使用するために、あなたの関数の別のAVX2版を作る価値がある可能性があります。これを行うと、最も効率的なCPUでは、関数はpmulld（mullo_epi32）しか使用しません。

pmulldは、Haswellでもスループットと融合領域のuopカウントに理想的です。 SnB/IvBでは、ベクトル整数乗算ユニットの単一のuopですが、関数全体は2uops/6サイクルのレイテンシ/ 1cスループットあたり1つのみです。 （シフト/ブレンドで管理した場合よりも悪いので、スループット/コードサイズがまったく問題ない場合はpmulldを使用したいだけです）。

// See the godbolt link below for a version of this with more comments 
// SnB/IvB: 6c latency, 2 fused-domain uops. 
__m128i isolate_successive_6bits_mul (__m128i input) 
{ 
    // We can avoid the AND if we shift the elements all the way to the left to knock off the high garbage bits. 
    // 32 - 6 - 18 = 8 extra bits to left shift 
    __m128i mul_constant = _mm_set_epi32(1<<(0+8), 1<<(6+8), 1<<(12+8), 1<<(18+8)); 
    __m128i left_vshift = _mm_mullo_epi32(input, mul_constant); 
    __m128i rightshifted = _mm_srli_epi32(left_vshift, (18+8)); 
    return rightshifted; 
} 

ブレンドと

---

スマートな方法：

Shiftキーとブレンドので、各要素は、右総シフトカウントで終わります。

すべてを1つのベクトルに結合した後、下位6ビットをANDマスクします。

インテルのCPUでのブルートフォース方式（下記参照）と同じレイテンシ（より少ないスループットのため） port5を結ぶ2つの即時ブレンドだけがいいです。 （AVX2 vpblenddは、任意のポートで実行することができますが、その後、我々はちょうどvpsrlvdを使用すると思います。）

// seems to be optimal for Intel CPUs. 
__m128i isolate_successive_6bits (__m128i input) 
{ // input = [ D  C  B  A ] 
    // output = [ D>>18 C>>12 B>>6 A ] & set1(0b111111) 
    __m128i right12 = _mm_srli_epi32(input, 12); 
    __m128i merged = _mm_blend_epi16(input, right12, 0xF0); // copy upper half, like `movhps` (but don't use that because of extra bypass delay) 
    // merged = [ D>>12 C>>12 B>>0 A>>0 ] 
    __m128i right6 = _mm_srli_epi32(merged, 6); 
    merged = _mm_blend_epi16(merged, right6, 0b11001100); // blend in the odd elements 
    // merged = [ D>>(12+6) C>>12 B>>(0+6) A>>0 ]   
    return _mm_and_si128(merged, _mm_set1_epi32(0b111111)); // keep only the low 6 bits 
} 

私はboth versions on the Godbolt compiler explorerを置きます。

このバージョンはgcc 5でコンパイルされたわずか5 uopsです。3 -O3 -march=ivybridge：

# input in xmm0, result in xmm0 
isolate_successive_6bits: 
    vpsrld   xmm1, xmm0, 12    # starts on cycle 0, result ready for the start of cycle 1 
    vpblendw  xmm0, xmm0, xmm1, 240   # cycle 1 
    vpsrld   xmm1, xmm0, 6     # cycle 2 
    vpblendw  xmm0, xmm0, xmm1, 204   # cycle 3 
    vpand   xmm0, xmm0, XMMWORD PTR .LC0[rip] # cycle 4, result ready on cycle 5 
    ret 

すべての命令は、以前に依存しているので、図5cの待ち時間があります。 SnB/IvB/HSW/BDW CPUは1つのシフトポートしか持たないので、より多くのブルートフォースバージョン（異なるシフトカウントで3つのシフトを行う）で利用可能な並列性を利用することはできません。 Skylakeはできますが、その後の2つのブレンドサイクルが改善を食い止めます。

---

「ブルートフォース」道：

3人の交代三つの異なるシフトカウントを行い、それぞれの目的の要素を持っているものに4つのベクトルを結合するために、3つの即時ブレンド（pblendw）を使用します。代わりに木の線形依存チェーンとの合併を行う

// same latency as the previous version on Skylake 
// slower on previous Intel SnB-family CPUs. 
isolate_successive_6bits_parallel: 
    vpsrld   xmm1, xmm0, 6   # cycle 0. SKL: c0 
    vpsrld   xmm2, xmm0, 12   # cycle 1 (resource conflict on pre-Skylake). SKL: c0 
    vpblendw  xmm1, xmm0, xmm1, 12  # cycle 2 (input dep). SKL: c1 
    vpsrld   xmm3, xmm0, 18   # cycle 2. SKL: c1 
    vpblendw  xmm0, xmm2, xmm3, 192 # cycle 3 (input dep). SKL: c2 
    vpblendw  xmm0, xmm1, xmm0, 240 # cycle 4 (input dep). SKL: c3 
    vpand   xmm0, xmm0, XMMWORD PTR .LC0[rip] # cycle 5 (input dep). SKL: c4. 
    ret 

は、最後のシフト結果の準備ができた後、マージが早く終了することができます意味：

isolate_successive_6bits_parallel2: 
    vpsrld   xmm1, xmm0, 6   # c0. SKL:c0 
    vpsrld   xmm2, xmm0, 12   # c1. SKL:c0 
    vpblendw  xmm1, xmm0, xmm1, 12 # c2. SKL:c1 
    vpblendw  xmm1, xmm1, xmm2, 48 # c3. SKL:c2 
    vpsrld   xmm0, xmm0, 18   # c2. SKL:c1 
    vpblendw  xmm0, xmm1, xmm0, 192 # c4. SKL:c3 (dep on xmm1) 
    vpand   xmm0, xmm0, XMMWORD PTR .LC0[rip] # c5. SKL:c4 
    ret 

いや、うーん、助けにはなりません。 BDWへのSnB、またはSKLに対するレイテンシの増加はありません。シフトされていない入力は1つの要素に必要なものなので、最初のマージは1つのシフトの後に起こります。要素0にゼロ以外のシフトカウントが必要だった場合、この方法ではpre-SKLに利点があり、SKLでは不利になる可能性があります。