コンパクトAVX2レジスタなので、選択された整数はマスクに従って連続しています[重複]

StackOverflow https://stackoverflow.com//questions/25074197

  •  26-12-2019
  •  | 
  •  

質問

質問の中で 配列圧縮の最適化, 、トップの答えの状態:

最新の命令セットを持つSSE/AVXレジスタは、より良いアプローチを可能にします。PMOVMSKBの結果を直接使用して、PSHUFBのような制御レジスタに変換することができます。

これはHaswell（AVX2）で可能ですか？またはそれはAVX512の味の1つを必要としますか？

私はint32sを含むAVX2ベクトルと、比較の結果の対応するベクトルを持っています。マスクに設定された対応するmsbを持つ要素（compare true）がベクトルの下端で連続するように、何らかの方法でシャッフルしたいと思います。

私が見ることができる最高のものは、_mm256_movemask_ps/vmovmskpsでビットマスクを取得することです（*dバリアントはありませんか？）そして、それを256AVX2ベクタールックアップテーブルで使用して、クロスレーン_mm256_permutevar8x32_epi32/vpermdのシャッフルマスクを取得します

役に立ちましたか？

解決

最初に行うことは、高速スカラー関数を見つけることです。これはブランチを使用しないバージョンです。

inline int compact(int *x, int *y, const int n) {
    int cnt = 0;
    for(int i=0; i<n; i++) {
        int cut = x[i]!=0;
        y[cnt] = cut*x[i];
        cnt += cut;
    }
    return cnt;
}

SIMDの最良の結果は、おそらくゼロの分布に依存します。まばらまたは密集している場合。次のコードは、疎または密な配布に適しているはずです。たとえば、ゼロと非ゼロの長い実行。配布がもっと均一であれば、このコードに何か利点があるかどうかはわかりません。しかし、とにかく正しい結果が得られます。

これが私がテストしたAVX2バージョンです。

int compact_AVX2(int *x, int *y, int n) {
    int i =0, cnt = 0;
    for(i=0; i<n-8; i+=8) {
        __m256i x4 = _mm256_loadu_si256((__m256i*)&x[i]);
        __m256i cmp = _mm256_cmpeq_epi32(x4, _mm256_setzero_si256());
        int mask = _mm256_movemask_epi8(cmp);
        if(mask == -1) continue; //all zeros
        if(mask) {
            cnt += compact(&x[i],&y[cnt], 8);
        }
        else {
            _mm256_storeu_si256((__m256i*)&y[cnt], x4);
            cnt +=8;
        }       
    }
    cnt += compact(&x[i], &y[cnt], n-i); // cleanup for n not a multiple of 8
    return cnt;
}

これが私がテストしたSSE2バージョンです。

int compact_SSE2(int *x, int *y, int n) {
    int i =0, cnt = 0;
    for(i=0; i<n-4; i+=4) {
        __m128i x4 = _mm_loadu_si128((__m128i*)&x[i]);
        __m128i cmp = _mm_cmpeq_epi32(x4, _mm_setzero_si128());
        int mask = _mm_movemask_epi8(cmp);
        if(mask == 0xffff) continue; //all zeroes
        if(mask) {
            cnt += compact(&x[i],&y[cnt], 4);
        }
        else {
            _mm_storeu_si128((__m128i*)&y[cnt], x4);
            cnt +=4;
        }       
    }
    cnt += compact(&x[i], &y[cnt], n-i); // cleanup for n not a multiple of 4
    return cnt;
}

ここに完全なテストがあります

#include <stdio.h>
#include <stdlib.h>
#if defined (__GNUC__) && ! defined (__INTEL_COMPILER)
#include <x86intrin.h>                
#else
#include <immintrin.h>                
#endif

#define N 50

inline int compact(int *x, int *y, const int n) {
    int cnt = 0;
    for(int i=0; i<n; i++) {
        int cut = x[i]!=0;
        y[cnt] = cut*x[i];
        cnt += cut;
    }
    return cnt;
}

int compact_SSE2(int *x, int *y, int n) {
        int i =0, cnt = 0;
        for(i=0; i<n-4; i+=4) {
            __m128i x4 = _mm_loadu_si128((__m128i*)&x[i]);
            __m128i cmp = _mm_cmpeq_epi32(x4, _mm_setzero_si128());
            int mask = _mm_movemask_epi8(cmp);
            if(mask == 0xffff) continue; //all zeroes
            if(mask) {
                cnt += compact(&x[i],&y[cnt], 4);
            }
            else {
                _mm_storeu_si128((__m128i*)&y[cnt], x4);
                cnt +=4;
            }       
        }
        cnt += compact(&x[i], &y[cnt], n-i); // cleanup for n not a multiple of 4
        return cnt;
    }

int compact_AVX2(int *x, int *y, int n) {
    int i =0, cnt = 0;
    for(i=0; i<n-8; i+=8) {
        __m256i x4 = _mm256_loadu_si256((__m256i*)&x[i]);
        __m256i cmp = _mm256_cmpeq_epi32(x4, _mm256_setzero_si256());
        int mask = _mm256_movemask_epi8(cmp);
        if(mask == -1) continue; //all zeros
        if(mask) {
            cnt += compact(&x[i],&y[cnt], 8);
        }
        else {
            _mm256_storeu_si256((__m256i*)&y[cnt], x4);
            cnt +=8;
        }       
    }
    cnt += compact(&x[i], &y[cnt], n-i); // cleanup for n not a multiple of 8
    return cnt;
}

int main() {
    int x[N], y[N];
    for(int i=0; i<N; i++) x[i] = rand()%10;
    //int cnt = compact_SSE2(x,y,N);
    int cnt = compact_AVX2(x,y,N);
    for(int i=0; i<N; i++) printf("%d ", x[i]); printf("\n");
    for(int i=0; i<cnt; i++) printf("%d ", y[i]); printf("\n");
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top