Registro AVX2 compatto in modo che gli interi selezionati siano contigui in base alla maschera [duplicato]

Question

Questa domanda ha già una risposta qui:

AVX2 qual è il modo più efficace per fare le valigie a sinistra in base a una maschera? (4 risposte)

Chiuso 3 anni fa.

Nella domanda Ottimizzazione della compattazione degli array, la risposta principale afferma:

I registri SSE/AVX con i set di istruzioni più recenti consentono un approccio migliore.Possiamo utilizzare direttamente il risultato di PMOVMSKB, trasformandolo nel registro di controllo per qualcosa come PSHUFB.

Questo è possibile con Haswell (AVX2)?Oppure richiede una delle versioni di AVX512?

Ho un vettore AVX2 contenente int32 e un vettore corrispondente del risultato di un confronto.Voglio mescolarlo in qualche modo in modo che gli elementi con il corrispondente msb impostato nella maschera (confronta vero) siano contigui nella fascia bassa del vettore.

Il meglio che riesco a vedere è ottenere una maschera di bit con _mm256_movemask_ps/vmovmskps (nessuna variante *d?) e quindi usarla in una tabella di ricerca vettoriale AVX2 256 per ottenere una maschera casuale per la corsia incrociata _mm256_permutevar8x32_epi32/vpermd

Answer 1

La prima cosa da fare è trovare una funzione scalare veloce.Ecco una versione che non utilizza un ramo.

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;
}

Il miglior risultato con SIMD probabilmente dipende dalla distribuzione degli zeri.Se è scarso o denso.Il seguente codice dovrebbe funzionare bene per distribuzioni sparse o dense.Ad esempio lunghe serie di zeri e diversi da zero.Se la distribuzione fosse più uniforme non so se questo codice porterà qualche vantaggio.Ma darà comunque il risultato corretto.

Ecco una versione AVX2 che ho testato.

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;
}

Ecco la versione SSE2 che ho testato.

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;
}

Ecco un test completo

#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");
}