8

SIMD 組み込み関数を使用してストリーム圧縮 (配列を取得し、空の要素を取り除く) を作成しようとしています。ループの各反復では、一度に 8 つの要素が処理されます (SIMD 幅)。

SSE 組み込み関数を使用すると、_mm_shuffle_epi8() を使用してこれをかなり効率的に実行できます。これは、16 エントリのテーブル ルックアップ (並列コンピューティング用語で収集) を実行します。シャッフル インデックスは事前に計算され、ビット マスクで検索されます。

for (i = 0; i < n; i += 8)
{
  v8n_Data = _mm_load_si128(&data[i]);
  mask = _mm_movemask_epi8(&is_valid[i]) & 0xff;     // is_valid is byte array
  v8n_Compacted = _mm_shuffle_epi8(v16n_ShuffleIndices[mask]);
  _mm_storeu_si128(&compacted[count], v8n_Compacted);

  count += bitCount[mask];
}

私の問題は、Altivec SIMD にもこれを実装したいということです (理由は聞かないでください - 見当違いのビジネス上の決定です)。Altivec には、重要な要素である _mm_movemask_epi8() に相当するものはありません。だから、私はどちらかへの方法を見つける必要があります

  1. エミュレート _mm_movemask_epi8() - コストがかかるようで、いくつかのシフトと OR

  2. シャッフル インデックスを効率的に直接生成する -

つまり、インデックス i は、圧縮されていないデータの i 番目の有効な要素のインデックスになります。

element_valid:   0 0 1 0 1 0 0 1 0
gather_indices:  x x x x x x 6 4 1
scatter_indices: 3 3 2 2 1 1 1 0 0

これをシリアルに行うのは簡単ですが、パラレル (SIMD) にする必要があります。プレフィックスサムを使用してスキャッター インデックスを生成するのは簡単に思えますが、AltiVec も SSE もスキャッター命令を持たないため、代わりにインデックスを収集する必要があります。収集インデックスは分散インデックスの逆関数ですが、どのように並行して取得できますか? GPU プログラミングの黎明期には、スキャッターをギャザーに変換するのが一般的な手法だったことは知っていますが、説明されているこれら 2 つの方法はどれも実用的ではないようです。

圧縮が要素の順序を維持することを主張しないと、より効率的な実装が可能になるでしょうか? 私はそれをあきらめることができます。

4

1 に答える 1

5

エミュレートする_mm_movemask_epi8必要があり、8 バイト要素から 8 ビットのスカラー マスクが必要な場合は、AltiVec を使用して次のように実行できます。

#include <stdio.h>

int main(void)
{
    const vector unsigned char vShift = { 0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0 };
                                            // constant shift vector

    vector unsigned char isValid = { 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
                                            // sample input

    vector unsigned char v1 = vec_sl(isValid, vShift);
                                            // shift input values
    vector unsigned int v2 = vec_sum4s(v1, (vector unsigned int)(0));
    vector signed int v3 = vec_sum2s((vector signed int)v2, (vector signed int)(0));
                                            // sum shifted values
    vector signed int v4 = vec_splat(v3, 1);
    unsigned int mask __attribute__ ((aligned(16)));
    vec_ste((vector unsigned int)v4, 0, &mask);
                                            // store sum in scalar

    printf("v1 = %vu\n", v1);
    printf("v2 = %#vlx\n", v2);
    printf("v3 = %#vlx\n", v3);
    printf("v4 = %#vlx\n", v4);
    printf("mask = %#x\n", mask);

    return 0;
}

これは、SSE の 1 に対して、5 つの AltiVec 命令です。を失って 4 まで下げることができるかもしれませんvec_splat。

于 2011-06-07T21:22:48.657 に答える