[x86 Intrinsic] Gegenstück zu movemask

[Schrompf]

Moin,

ich vektorisiere gerade wieder fröhlich. Rockt schon derbe, aber hier und da stolpere ich über Dinge, die mir eigentlich alltäglich erscheinen, aber für die ich nichts in der IntelIntrinsic-Seite finde.

Aktuell: ich möchte 8x uint32 anhand eines Bitmusters setzen: für jedes gesetzte Bit will ich den Wert aus A256, sonst den Wert aus B256. Und da gibt es verschiedene Kandidaten, aber keine kriege ich eingebaut.

_mm256_mask_expand_epi32() nimmt für jedes gesetzte Bit kontinuierlich aus A den Wert, ansonsten kopiert es den Wert aus B. Ich habe mich leider von dem "_mm256" vornedran in die Irre führen lassen, das Ding gibt's erst mit AVX512, und das wird quasi nirgends unterstützt.

_mm256_blend_epi32() und Artverwandte erwarten das Bitmuster als CompileTime-Konstante. Mäh.

_mm256_blendv_ps() bezieht sich zwar auf float32, aber das ist mir ja schnuppe, kann ich mir ja schöncasten. Leider möchte das Ding eine 256Bit-Maske haben, und ich habe eine 64bit-Maske bzw. daraus mit dem titelgebenden _mm_movemask_epi8() eine 8Bit-Maske erzeugt.

Ich bräuchte jetzt also einen Befehl, der das Gegenstück zu movemask ausführt: einzelne Bits auf ganze Byte/Word/Int aufzublasen.
Oder ich biege vorher schon ab und lasse das movemask weg. Dann bräuchte ich einen Befehl, der 8x uint8 auf 8x uint32 aufpustet. Kennt jemand solche Befehle?

Und bitte nicht nur auf Intels Intrinsic-Seite verweisen, ich hab dort schon mein Zelt aufgeschlagen. Man muss dort halt schon den richtigen Begriff auf der Zunge haben, um mit der Suche was Nützliches finden zu können.

[Schrompf]

Habe gerade _mm256_cvtepi8_epi32() gefunden. Damit kann ich ohne Umweg über Einzelbits direkt 8x uint8 das Ergebnis des Einzelvoxel-Vergleichs in in 8x uint32 die anzuwendende Maske für _mm256_blendv_ps() konvertieren.

Logisch, nöch? 256Bit breit ("_mm256") konvertiere ("cvt") aus nem Extended-Register ("e") die untersten zusammengepackten (packed "p") int8 ("i8") in ein Extended-Register (das zweite "e") in zusammengepackte (das zweite "p") int32 ("i32"). Langsam komm ich drauf.

Ein Gegenstück zu movemask() scheint's trotzdem nicht zu geben. Muss man wahrscheinlich mit set1_epiX() und shiftleft emulieren, bis in jedem Einzelelement das richtige Bit ganz oben steht.

[Spiele Programmierer]

Gukst du einfach hier: https://software.intel.com/sites/landin ... nsicsGuide

xD Sorry, ich konnte es mir nicht verkneifen.

Vorweg, du kannst durchaus _mm256_blendv_ps für Integers verwenden, aber nur zur Sicherheit, falls du das noch nicht gehört hast, möchte ich darauf hinweisen, dass beim Wechsel von Float to Int (und zurück) bei den meisten Prozessoren zusätzliche Latenz dazukommt. Als Faustregel kann man so mit ~1 Zykel rechnen. Die genauen Zahlen und welche Befehle betroffen sind variieren so ein bisschen zwischen den Herstellern und Modellen. Dementsprechend würde ich wenn dann den _mm256_blendv_epi8-Befehl als Ersatz vorschlagen, wenn du mit Ganzzahlen arbeiten möchtest und nicht unbedingt am Bit in der niedrigsten Stelle interessiert bist. Manchmal ist Latenz auch egal und es kommt nur auf den Durchsatz an. Dann spielt es natürlich keine Rolle.

Bezüglich deinem konkreten Problem: Ein einzelner Befehl ist mir auch nicht bekannt. In meiner noch in Entwicklung befindlichen SIMD-Bibliothek, die gerade solche Lücken schließen soll, implementiere ich das so:

Code: Alles auswählen

const __m256i Bits = _mm256_setr_epi32(1, 2, 4, 8, 16, 32, 64, 128);
return _mm256_cmpeq_epi32(_mm256_and_si256(_mm256_set1_epi32(a), Bits), Bits);

Dabei ist a natürlich der eingehende Bitselektor, bei dem jedes Bit zu 32 Bit in der Ausgabe korrespondiert. Wenn man mehrere Werte auf einmal braucht, kann man natürlich mit anderen Bits bis zu 4 AVX-Register aus nur einem _mm256_set1_epi32(a) speisen.

Wenn jemand eine bessere Sequenz kennt, bin ich auch daran interessiert!

Hier die Throughput-Analyse laut LLVM-MCA: Intel Haswell, AMD Zen 2.

Bei konkreten Fällen kann die Ladeoperation von Bits auch außerhalb der Schleife gezogen werden und amortisiert sich damit. Das kann auch oft der Compiler automatisch machen.

[Krishty]

Ich verstehe gerade nicht … du hast 8 Voxel, jeder ein Bit (nicht Byte) groß. Oder? Und dann machst du einen „Voxelvergleich“? Auf den acht Bits? Oder zu acht Bytes konvertiert? Oder zu 8×uint? Und auf Basis des Ergebnisses möchtest du aus zwei Vektoren auswählen, in denen jeweils acht 32-Bit-Werte liegen?

Edit: Sorry, jetzt habe ich’s. Ja, da ist mir auch kein Befehl bekannt. Vielleicht gab es da einen Trick mit einer Multiplikation; muss ich mal nachgucken …

[Krishty]

Aaaalso

Hast du Bit Manipulation Instruction Set 2 verfügbar? Müssten Intel/AMD seit ca. 2011 unterstützen. In diesem Fall kannst du _pdep_u64(bitmaske, 0x8080808080808080); benutzen um ein 64-Bit-Integer zu erhalten, das hinter jedem deiner Masken-Bits sieben Nullen eingefügt hat. Das lässt sich dann sehr einfach zu einer „vollen“ Maske konvertieren (Vektorvergleich < 0); oftmals brauchst du’s aber gar nicht (viele AVX-Befehle bedenken nur die Sign Bits).

—

Was ich im Hinterkopf hatte, war: Multiplizierst du eine Zahl mit sich selber *ohne den Übertrag zu betrachten*, entspricht das den Einfügen einer 0 hinter jedem einzelnen Bit. Alter Trick von Z-Order Curves. Es müsste irgendwo eine magische Konstante geben, um das in zwei oder drei Multiplikationen hinzukriegen (statt in mindestens acht Shifts). Dummerweise finde ich gerade nicht mehr die Original-Quelle und bin mit der Mathe überfordert.

Nachtrag: Google sagt, dass der AVX-Befehl für carry-less Multiplication _mm256_clmulepi64_epi128 ist, und es gibt wohl weniger als 20 Ergebnisse dafür im Internet. Viel Spaß ;)

[Schrompf]

Also: erstmal Danke. Die IntelIntrinsics-Seite meint, die Casts wären komplett kostenlos. Würde mich auch wundern, es ist doch nur ne Uminterpretation der Bits in nem YMM-Register. Echte Konvertierungen des Zahlenswerts eines float in den Zahlenwert eines int kosten auf jeden Fall. Und die Idee "Repliziere Zahl auf alle Elemente und maskiere das jeweilige Bit, dann vergleichen" finde ich gut. Das blendv behauptet, es liest nur das oberste Bit jedes uint32-Elements in der Maske. Und das hab ich dann so gemacht:

Code: Alles auswählen

uint32_t leerBits = 0xffu & (some_uint64 >> 8*gewuenschtesByte);
__m256i allesBits = _mm256_set1_epi32( leerBits);
leerMaske = _mm256_sllv_epi32( allesBits, _mm256_setr_epi32( 17, 18, 19, 20, 21, 22, 23, 24));

Repliziert also die 8bit-Maske in alle 8 Elemente eines __m256i und schiebt sie dann so weit rechts, dass in jedem Element ein anderes Bit ganz oben rauskommt. Es scheint zu funktionieren.

@Krishty:
Es gibt hier verschiedene UseCases. Ich habe einen 8³-Voxelblock bestehend aus einem uint64, in dem jedes gesetzte Bit besagt, welcher 2³-Block nicht leer ist, und dann 64x uint64, in dem jedes Byte einen echten Voxel darstellt. Jeder 4³-Block ist dann ein Byte im Besetzt-uint64 und 8x-uint64 mit den Einzelvoxeln. Wenn ich auf der Achterstufe betrachte, prüfe ich den Besetzt-uint64 byteweise, bekomme also eine Bytemaske. Die blase ich jetzt mit _mm256_cvtepi8_epi32 auf 8x uint32 auf. Wenn ich auf der Viererstufe unterwegs bin, nehme ich ein Einzelbyte aus dem Besetzt-uint64 und puste die Einzelbits auf 8x uint32 auf. Wenn ich auf der Zweierstufe bin, nehme ich mit den Einzelvoxel-uint64 und nehme wieder _mm256_cvtepi8_epi32. Das Ergebnis ist in jedem Fall 8xuint32 Subnodes, weil meine SVT-Abklapperung das als gemeinsamen Node-Struktur nimmt.

[Krishty]

Die IntelIntrinsics-Seite meint, die Casts wären komplett kostenlos. Würde mich auch wundern, es ist doch nur ne Uminterpretation der Bits in nem YMM-Register.

Doch, auf einigen AMD-CPUs kostet die Uminterpretierung der Bits, da AMD die Flags für NaN-Status & Co. neben den Registern ablegt, aber für Integer nicht pflegt. Bei einer Uminterpretierung wird das nachgeholt. War jedenfalls um 2010 so.

[Krishty]

So, jetzt habe ich es doch mit der Multiplikation geschafft.

Nehmen wir an, wir haben eine Binärzahl mit acht Stellen: abcdefgh.

Nun multiplizieren wir sie mit einer anderen Binärzahl, z. B. 110.

Das bedeutet:

Code: Alles auswählen

  110 × abcdefgh =
    0 × abcdefgh
+  10 × abcdefgh
+ 100 × abcdefgh

Wir sprechen von Binärzahlen, da bedeutet die Multiplikation mit einer Zweiterpotenz, dass wir die Nullen einfach rechts anhängen:

Code: Alles auswählen

  110 × abcdefgh =
    0 × abcdefgh
+  1 × abcdefgh0
+ 1 × abcdefgh00

Interessant wird es jetzt, wenn sich die Summanden nicht überlappen. Beispiel:

Code: Alles auswählen

  10000000001 × abcdefgh =
            1 × abcdefgh
+ 1 × abcdefgh0000000000
=     abcdefgh00abcdefgh

Wenn man zwei Zahlen addiert, bei denen sich nur Nullen überlappen, gibt es keinen Übertrag. Binär entspricht das einem OR.

Wir können also via Multiplikation die Zahl an jede beliebige Stelle replizieren, so lange keine Überlappungen entstehen. Sonst vermasselt der Übertrag die ganze Rechnung.

Also replizieren wir erstmal die vier geraden Bits in Bytes mit je einem Puffer-Byte dazwischen:

Code: Alles auswählen

0000 0001 0000 0000 0000 0100 0000 0000 0001 0000 0000 0000 0100 0000 0000 0000 × abcdefgh =
abcd efgh 0000 00ab cdef gh00 0000 abcd efgh 0000 00ab cdef gh00 0000 0000 0000
^                   ^                   ^                   ^

Jetzt das gleiche für die vier ungeraden Bits, aber um ein Byte verschoben:

Code: Alles auswählen

0000 0000 0000 0010 0000 0000 0000 1000 0000 0000 0010 0000 0000 0000 1000 0000 × abcdefgh =
0000 000a bcde fgh0 0000 0abc defg h000 000a bcde fgh0 0000 0abc defg h000 0000 
          ^                   ^                   ^                   ^

Der erste Multiplikator hexadezimal: 0x0100'0400'1000'4000
Der zweite Multiplikator hexadezimal: 0x0001'0008'0020'0080

Ein Verschieben aller individuellen Bits an die Spitze der jeweiligen Bytes ist also:
((0x0100'0400'1000'4000 * x) & 0x8000'8000'8000'8000) | ((0x0002'0008'0020'0080 * x) & 0x0080'0080'0080'0080)

Das Ergebnis ist eine 64-Bit-Zahl und kann recht einfach in ein Vektorregister geschoben werden, um es dann von 8 Bits pro Kanal auf 32 pro Kanal aufzupusten.

Multiplikationen sind langsam, aber du hast eine gewisse Chance, dass die CPU die zweite nur einen Takt nach der ersten startet (oder dass der Compiler LEA neben UMUL benutzt, dann sind sie komplett parallel).

Würde mich über einen Geschwindigkeitsvergleich zum Shifting freuen :)

[Spiele Programmierer]

@Kristhy
Der _pdep_u64-Intrinsic erfüllt eine super Funktion, hat allerdings eine fiese Falle. Ich bin auch schonmal reingetappt: Man muss dringend davon Abstand nehmen, wenn man AMD-CPUs unterstützen will. Der Befehl ist dort unbrauchbar langsam. Agner spricht von 6 Zyklen für einen Befehl Durchsatz und einer Latenz von 19 Zyklen. Das ist aber eher noch ein sehr guter Fall, denn die Geschwindigkeit ist von der Eingabe abhängig. Quelle: https://twitter.com/InstLatX64/status/1 ... 1288559617.

Der Trick via clmul zu einer Z-Kurve funktioniert übrigens durch eine Multiplikation mit sich selbst. Es ist eine schöne Eigenschaft der Polynommultiplikation, dass alle Mischterme von verschiedenen Bits zweimal auftreten (ala (1 + x)² = 1 + 2x + x²). Diese Beiträge verschwinden daher in Modulo-2-Arithmetik einfach und man erhält genau die Quadrate der einzelnen Bits. Ich fürchte aber, dass daher für Schrompf insgesamt 3 clmul notwendig wären, um die gepackte Bits zu Bytes zu entpacken. Das ist schon relativ viel.

@Casts
Kristhy hat es ja eben auch schon nochmal gesagt. Ja, Casts sind in dem Sinn nicht kostenlos. Meines Wissens auch nicht bei Intel. Agner schreibt dazu in seinem Manual zu Intel Skylake (Seite 154, "Data bypass delays"): "The execution units are divided into domains as described on page 113, and there is sometimes a delay of one clock cycle when the output of an instruction in the integer domain is used as input for an instruction in the floating point domain." Allerdings schreibt er auch, dass es viele Fälle gibt, bei denen bei diesem Prozessor die Extralatenz vermieden wird. Zum Beispiel auch bei den VBlend-Instruktionen die Schrompf jetzt benutzen wollte. Die Details ändern sich da ständig. Laut Agner sind mit AMD-CPUs die VBlend-Operationen aber nicht ausgenommen.

Wenn man sehr genau liest, ist die Intel-Dokumentation ist auch gar nicht falsch in dem Sinn als das z.B. _mm256_castps_si256(_mm256_castsi256_ps(...)) tatsächlich immer 0-Latenz hat. Man kann also argumentieren, dass der Cast tatsächlich frei ist und nur durch die Verwendung mit dem falschen Typ dann diese Latenz entsteht.

@Schrompf
Dein Weg sieht auch nicht schlecht aus! Schonmal weniger Befehle. Ich glaube aber, dass sllv tendentiell eher nicht so schnell ist wie billige bitweises-Und und es gibt halt diese "Data Bypass Delays" mit älteren Intel-CPUs oder generell AMD-CPUs. Ich würde daher tippen, dass meine Variante speziell mit AMD-CPUs besser abschneidet. Um sicher zu gehen, würde aber auch mal mit LLVM-MCA schauen. Manchmal ist man auch einfach in einem Dilemma, weil verschiedene Varianten mit verschiedenen CPUs die Nase (manchmal deutlich) vorne haben.

Deine Indices sehen für mich übrigens irgendwie um 7 verschoben aus. Hab ich gerade einen Denkfehler oder ist das falsch?

Was mir auf jeden Fall auch noch auffällt ist, dass das bitweise-Und mit 0xff überflüssig ist. Wenn es wirklich performance-kritisch ist, würde ich auch gleich noch gucken, ob man nicht das Ergebnis von _mm256_set1_epi32 recyclen kann. Wenn man 4 Bytes auf einmal verarbeitet, könnte man auch noch das Geschiebe am Anfang sparen.

[Schrompf]

Bemerkenswert, auf welchem Level ihr hier unterwegs seid. Vielen Dank für den Input, das ist echt fett. Ich kann hier aber schlecht ein Shootout veranstalten, weil die Logik nur drei vier mal nacheinander so billig ist, dann muss ein neuer Voxelblock entpackt werden. Und wie gesagt sind die Voxelblöcke bei mir palettiert und bitkomprimiert. Macht aus 512byte so 10 bis 15 Byte, aber ist halt hacketeuer beim Auspacken. Es ist völlig wurscht, wieviele Takte ich hier verschwende, wenn jedes 10. Mal ein paar Mikrosekunden über den Jordan gehen.

[Krishty]

Och, ich beneide dich. Ich habe AVX nie angepackt, weil ich bis 2020 keine CPU hatte, die das unterstützt. Jetzt habe ich zwar eine, aber keine Zeit zum Spielen :(

@Spiele:

Der _pdep_u64-Intrinsic erfüllt eine super Funktion, hat allerdings eine fiese Falle.

oh lol, das ist ja ähnlich krass wie die uralten Bit-Test-Intrinsics, die emuliert werden. Danke für die Warnung!

Ich glaube auch, ich habe wirklich Murks geschrieben, dass ich mir den Vergleich zweier Multiplikationen mit einem einzigen Shift wünsche(!). Ich sollte mich mal wieder fit machen … :D

[Schrompf]

Wenn wir gerade beim "Fit machen" sind: Multiplikationen sind schon seit Jahren nicht mehr "langsam". Ich kann leider keine einzelne Instruction direkt linken, daher erzähle ich es Dir einfach: _mm_mul_ss() (Vektor-Multi 4x float32) hat 3 bis 5 Takte Latenz und einen Durchsatz von zwei Instructions pro Taktzyklus. Fused Multiply Add ist nur minimal langsamer mit 4 bis 6 Takten Latenz und ebenso 0.5 CPI (Cycles Per Instruction). Division ist immer noch amtlich teuer mit ~15 Takten Latenz und 3 bis 20 (!) CPI. Ich sehe gerade, das Punktprodukt ist auch ganz schön teuer. Warum eigentlich? Ist doch genauso eigentlich nur ein Fused Multiply Add.

[Krishty]

Ich sehe gerade, das Punktprodukt ist auch ganz schön teuer. Warum eigentlich? Ist doch genauso eigentlich nur ein Fused Multiply Add.

FMA für Punktprodukt ist schlecht, weil es mit normalisierten Vektoren Ergebnisse außerhalb von [-1, +1] liefern kann.

Der Grund, warum Skalarprodukt langsam ist: Du sollst Structure of Array benutzen statt Array of Structure. Da hast du maximalen Durchsatz, brauchst keine zusätzlichen Transistoren, und andere Programmteile profitieren noch mehr von SIMD. Punktproduktbefehle sind dann per Definition nur für Leute, die zwar SIMD nutzen, denen Leistung aber nicht super wichtig ist, sonst hätten sie ja SOA und kämen mit MUL und ADD aus.

[Spiele Programmierer]

Das Punktprodukt ist auch eine sehr schlechte Idee bei AMD-Prozessoren. (Durchsatz von einem Befehl in 10 bzw. 14 Takten laut AMD)

Ich würde daher von diesem Intrinsic Abstand nehmen.