Kompaktes AVX2-Register, sodass ausgewählte Ganzzahlen entsprechend der Maske zusammenhängend sind [Duplikat]

Question

Auf diese Frage gibt es hier bereits Antworten:

AVX2: Was ist der effizienteste Weg, Links basierend auf einer Maske zu packen? (4 Antworten)

Geschlossen Vor 3 Jahren.

In der Frage Optimierung der Array-Komprimierung, In der obersten Antwort heißt es:

SSE/AVX-Register mit den neuesten Befehlssätzen ermöglichen einen besseren Ansatz.Wir können das Ergebnis von PMOVMSKB direkt verwenden und es in das Steuerregister für etwas wie PSHUFB umwandeln.

Ist das mit Haswell (AVX2) möglich?Oder ist eine der Varianten von AVX512 erforderlich?

Ich habe einen AVX2-Vektor, der int32s enthält, und einen entsprechenden Vektor des Ergebnisses eines Vergleichs.Ich möchte es irgendwie mischen, sodass die Elemente mit dem entsprechenden MSB-Satz in der Maske (vergleiche true) am unteren Ende des Vektors zusammenhängen.

Das Beste, was ich sehen kann, ist, eine Bitmaske mit _mm256_movemask_ps/vmovmskps (keine *d-Variante?) zu erhalten und diese dann in einer 256 AVX2-Vektor-Lookup-Tabelle zu verwenden, um eine Shuffle-Maske für den spurübergreifenden _mm256_permutevar8x32_epi32/vpermd zu erhalten

Answer 1

Als Erstes muss eine schnelle Skalarfunktion gefunden werden.Hier ist eine Version, die keinen Zweig verwendet.

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

Das beste Ergebnis mit SIMD hängt wahrscheinlich von der Verteilung der Nullen ab.Ob es spärlich oder dicht ist.Der folgende Code sollte für Verteilungen mit geringer oder dichter Verteilung gut funktionieren.Zum Beispiel lange Folgen von Nullen und Nicht-Nullen.Wenn die Verteilung gleichmäßiger ist, weiß ich nicht, ob dieser Code einen Nutzen hat.Aber es wird trotzdem das richtige Ergebnis liefern.

Hier ist eine AVX2-Version, die ich getestet habe.

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

Hier ist die SSE2-Version, die ich getestet habe.

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

Hier ist ein vollständiger Test

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