Problem
Gibt es rechnerisch machbare Ansätze zur intraregistralen Deduplizierung einer Menge von ganzen Zahlen mit x86 SIMD-Anweisungen?
Beispiel
Wir haben ein 4-Tupel-Register R1 = {3, 9, 2, 9} und möchten das Register R2 = {3, 9, 2, NULL} erhalten.
Einschränkungen
Stabilität . Die Erhaltung der Reihenfolge der Eingabe ist nicht von Bedeutung.
Ausgabe Alle entfernten Werte / NULL müssen jedoch am Anfang und / oder am Ende des Registers stehen:
Es ist offensichtlich ein Bonus, wenn es bekannt ist, ein bestimmtes Ausgabeformat zu produzieren. Bitte nehmen Sie NULL an, um effektiv 0 (Null) zu bedeuten.
Allgemeingültigkeit . Muss in der Lage sein, die Abwesenheit von Duplikaten zu tolerieren, und in diesem Fall eine Ausgabe erzeugen, die äquivalent zu dem Eingangsregister ist.
Befehlssätze . Ich suche nach Lösungen für einige oder alle von: SSE2-SSSE3; SSE4.x; AVX-AVX2
Naive Lösung
Roher Pseudocode basierend auf der Operation Max (). Kommentare verfolgen die Daten für die erste Iteration.
%Vor%Einige Gedanken:
%Vor%Die vorgeschlagene Lösung setzt immer alle eindeutigen Elemente in den unteren Teil der Ausgabe, geordnet nach ersten Vorkommen. Der höhere Teil wird auf Null gesetzt. Es ist einfach, die Platzierungsstrategie durch Ändern der LUT zu ändern: Elemente in einen höheren Teil stellen oder ihre Reihenfolge umkehren.
%Vor%Der vollständige Code (mit Tests) ist hier verfügbar.
Ich habe auch eine einfache skalare Lösung implementiert, indem ich ein Netzwerk von fünf Komparatoren sortiert habe, gefolgt von einem seriellen Vergleich aufeinanderfolgender Elemente. Ich benutzte MSVC2013 auf zwei Prozessoren: Core 2 E4700 (Allendale, 2.6 Ghz) und Core i7-3770 (Ivy Bridge, 3.4 Ghz). Hier sind die Zeitangaben in Sekunden für 2 ^ 29 Anrufe:
%Vor%Beachten Sie, dass das Ergebnis aus zwei Arten von Elementen bestehen muss:
Die erforderliche Shuffling-Maske wird jedoch zur Laufzeit und auf sehr komplexe Weise bestimmt. Alle SSE-Befehle können nur mit unmittelbaren (d. H. Kompilierzeitkonstanten) Mischmasken umgehen, mit Ausnahme von einem. Es ist _mm_shuffle_epi8 intrinsic von SSSE3. Um eine Mischmaske schnell zu erhalten, werden alle Masken in einer Nachschlagetabelle gespeichert, die durch einige Bitmasken oder Hashes indiziert wird.
Um eine Verschiebemaske für einen gegebenen Eingabevektor zu erhalten, ist es notwendig, genügend Information über gleiche Elemente darin zu sammeln. Beachten Sie, dass es völlig ausreichend ist zu wissen, welche Paare von Elementen gleich sind, um zu bestimmen, wie sie dedupliziert werden. Wenn wir sie zusätzlich sortieren wollen, müssen wir auch wissen, wie die verschiedenen Elemente miteinander verglichen werden, was die Menge der Informationen erhöht, und anschließend die Nachschlagetabelle. Aus diesem Grund zeige ich hier die Deduplizierung ohne .
Also haben wir vier 32-Bit-Elemente in einem XMM-Register. Sie komponieren insgesamt sechs Paare. Da wir nur vier Elemente gleichzeitig vergleichen können, benötigen wir mindestens zwei Vergleiche. Tatsächlich ist es einfach, zwei XMM-Vergleiche durchzuführen, so dass jedes Elementpaar mindestens einmal verglichen wird. Danach können wir 16-Bit-Bitmasken von Vergleichen extrahieren, indem wir _mm_movemask_epi8 verwenden und sie zu einer einzigen 32-Bit-Ganzzahl verketten. Beachten Sie, dass jeder 4-Bit-Block sicher die gleichen Bits enthält und dass die letzten beiden 4-Bit-Blöcke nicht notwendig sind (sie entsprechen exzessiven Vergleichen).
Im Idealfall müssen wir aus dieser Bitmaske genau 6 Bits extrahieren, die sich in bekannten Kompilierungszeiten befinden. Es kann leicht mit _pext_u32 intrinsic vom BMI2-Befehlssatz erreicht werden. Als Ergebnis haben wir eine Ganzzahl im Bereich [0..63] mit 6 Bits, jedes Bit zeigt an, ob das entsprechende Elementpaar gleich ist. Dann laden wir eine Shuffling-Maske aus der vorausberechneten Nachschlagetabelle mit 64 Einträgen und mischen unseren Eingabevektor mit _mm_shuffle_epi8 .
Leider sind BMI-Anweisungen ziemlich neu (Haswell und später), und ich habe sie nicht =) Um es loszuwerden, können wir versuchen, ein sehr einfaches und schnelles perfekte Hash-Funktion für alle 64 gültigen Bitmasken (erinnern Sie sich, dass Bitmasken 32-Bit sind). Für Hash-Funktionen in der Klasse f(x) = (a * x) >> (32-b) ist es normalerweise möglich, einen ziemlich kleinen perfekten Hash zu erstellen, mit 2x oder 3x Speicheraufwand. Da unser Fall speziell ist, ist es möglich, eine minimale perfekte Hash-Funktion zu konstruieren, so dass die Nachschlagetabelle minimal 64 Einträge aufweist (d. H. Größe = 1 KB).
Derselbe Algorithmus ist für 8 Elemente (z. B. 16-Bit-Ganzzahlen im XMM-Register) nicht durchführbar, da es 28 Elementpaare gibt, was bedeutet, dass die Nachschlagetabelle mindestens 2 ^ 28 Einträge enthalten muss.
Die Verwendung dieses Ansatzes für 64-Bit-Elemente in einem YMM-Register ist ebenfalls problematisch. _mm256_shuffle_epi8 intrinsic hilft nicht, da es einfach zwei separate 128-Bit-Shuffle-Operationen durchführt (niemals über die Lanes hinweg mischt). _mm256_permutevar8x32_epi32 intrinsic führt ein beliebiges Shuffling von 32-Bit-Blöcken durch, kann jedoch keine Nullen einfügen. Um es zu verwenden, müssen Sie auch die Anzahl der eindeutigen Elemente in der LUT speichern. Dann müssen Sie manuell Nullen in den höheren Teil Ihres Registers setzen.
Ich habe festgestellt, dass die Verwendung von BMI2 für die Bit-Extraktion oder die perfekte Hash-Funktion nicht notwendig ist. Wir können einfach _mm_movemask_ps verwenden, um 32-Bit-Masken zu extrahieren. Dieser Ansatz kann unter geringen Latenzproblemen leiden, da wir INT- und FP-Berechnungen mischen, aber in der Praxis schneller funktioniert.
Der vollständige Code wurde ebenfalls aktualisiert. Dies führt zu einer geringfügigen Leistungsverbesserung:
%Vor%