SIMD-Anweisungen für Gleitkomma-Gleichheitsvergleich (mit NaN == NaN)

Auch wenn AVX VCMPPS verfügbar ist (mit einer erheblich erweiterten Auswahl an Prädikaten), ist es weniger effizient als der IEEE-Vergleich. Sie müssen mindestens zwei Vergleiche durchführen und die Ergebnisse kombinieren. Es ist aber nicht so schlimm.

• verschiedene NaN-Kodierungen sind nicht gleich: effektiv 2 extra insns (2 UPs addierend). Ohne AVX: Ein extra movaps darüber hinaus.

• verschiedene NaN-Kodierungen sind gleich: effektiv 4 extra insns (4 ups addierend). Ohne AVX: Zwei zusätzliche movaps insn

Ein IEEE-Vergleich-und-Zweig ist 3 UPs: cmpeqps / movmskps / Test-und-Zweig. Intel und AMD verschmelzen den Test-and-Branch zu einem einzigen UOP / M-OP.

Mit AVX512: bitweise-NaN ist wahrscheinlich nur eine zusätzliche Anweisung, da normaler Vektorvergleich und Verzweigung wahrscheinlich vcmpEQ_OQps / ktest same,same / jcc verwendet, also ist die Kombination von zwei verschiedenen Maskenregs frei (ändern Sie einfach die Argumente zu %Code%). Die einzigen Kosten sind die zusätzlichen ktest .

AVX512 any-NaN sind nur zwei zusätzliche Anweisungen (2x vpcmpeqd k2, xmm0,xmm1 , wobei die zweite das Ergebnis der ersten als Zeromaske verwendet. Siehe unten). Wiederum, dann VFPCLASSPS mit zwei verschiedenen Argumenten, um Flag zu setzen.

Meine beste Idee bisher: ktest

Wenn wir auf die Berücksichtigung verschiedener NaN-Kodierungen verzichten:

• Bitweise gleich fängt zwei identische NaNs ein.
• IEEE gleicht den ieee_equal || bitwise_equal case ab.

Es gibt keine Fälle, in denen beide Vergleiche einen falschen positiven Wert ergeben (da +0 == -0 falsch ist, wenn einer der Operanden NaN ist: wir wollen nur gleich, nicht gleich oder ungeordnet. AVX ieee_equal bietet beide Optionen, nur SSE bietet eine einfache gleiche Operation.)

Wir wollen wissen, wann alle Elemente gleich sind, also sollten wir mit umgekehrten Vergleichen beginnen. Es ist einfacher, nach mindestens einem Nicht-Null-Element zu suchen, als nach allen Elementen zu suchen, die nicht Null sind. (dh horizontales AND ist hart, horizontales ODER ist einfach ( vcmpps / pmovmskb , oder test ). Das Gegenteil von einem Vergleich ist frei ( ptest anstelle von jnz ). Dies ist die Derselbe Trick, den Paul R benutzt hat.

Bei doppelter Genauigkeit funktionieren jz und ...PS gleich.

Wenn der ungleiche Code fortfährt, um herauszufinden, welches Element nicht gleich ist, gibt ein Bit-Scan auf dem pcmpeqQ Ergebnis Ihnen die Position der ersten Differenz.

Mit SSE4.1 movmskps können Sie PTEST / andnps / test-and-branch durch:

Ich erwarte, dass dies das erste Mal ist, dass die meisten Leute jemals das movmskps Ergebnis von CF als nützlich für irgendetwas gesehen haben. :)

Es sind immer noch drei Ups auf Intel- und AMD-CPUs ((2ptest + 1jcc) vs (pandn + movmsk + fusioned-test & amp; branch)), aber weniger Anweisungen. It ist effizienter, wenn Sie PTEST oder setcc anstelle von cmovcc verwenden, da diese nicht mit jcc verschmelzen können.

Das macht insgesamt 6 Ups (5 mit AVX) für einen reflexiven Vergleich und Zweig, vs. 3 Ups für einen IEEE-Vergleich-und-Zweig . ( test / cmpeqps / Test-und-Zweig.)

movmskps hat eine sehr hohe Latenzzeit bei CPUs der AMD Bulldozer-Familie ( 14c auf Steamroller ). Sie haben einen Cluster von Vektorausführungseinheiten, die von zwei Integer-Kernen gemeinsam genutzt werden. (Dies ist ihre Alternative zum Hyperthreading.) Dies erhöht die Zeit, bis ein Verzweigungsfehlschlag erkannt werden kann, oder die Latenz einer Datenabhängigkeitskette ( PTEST / cmovcc ).

PTEST setzt setcc , wenn ZF : gesetzt, wenn keine Elemente sowohl 0==(xmm0 AND xmm2) als auch IEEE (neq oder ungeordnet) waren. h. ZF ist nicht gesetzt, wenn irgendein Element bitwise_equal war, während es auch bitwise_equal war. Dies kann nur passieren, wenn ein Paar Elemente bitweise-gleich !ieee_equal s enthält (kann aber passieren, wenn andere Elemente ungleich sind).

Es gibt keine Bedingung, die NaN und irgendetwas über CF=1 testet. ZF Tests ja . Es ist unwahrscheinlich, dass Sie nur dies trotzdem testen möchten. Es ist also gut, ein CF=0 and ZF=1 im Zweig jnz zu setzen. (Und wenn Sie nur jc AND equal_reflexive testen wollten, könnte ein anderes Setup wahrscheinlich Flags entsprechend setzen).

Betrachtet alle NaNs gleich, auch wenn sie nicht bitweise gleich sind:

Dies ist die gleiche Idee wie die Antwort von Paul R., aber mit einem Bugfix (kombiniere NaN-Check mit IEEE-Check mit AND anstatt OR.)

Also brauchen wir in diesem Fall nicht at_least_one_nan 's PTEST resultat. Das machen wir bei CF , weil es keine Inverse hat (so wie PCMPEQD cmpunordps hat).

9 Fused-Domain-Ups für Intel-SnB-Familien-CPUs. (7 mit AVX: Verwenden Sie nicht-destruktive 3-Operanden-Anweisungen, um die cmpordps zu vermeiden.) Jedoch können CPUs der Pre-Skylake-SnB-Familie nur movaps auf p1 laufen lassen, also diese Engpässe auf der FP-add-Einheit bei Durchsatz ist ein Problem. Skylake führt cmpps auf p0 / p1.

cmpps hat eine kürzere Kodierung als andps , und Intel-CPUs von Nehalem bis Broadwell können nur auf port5 laufen. Dies kann wünschenswert sein, um zu verhindern, dass ein p0 oder p1 Zyklus von dem umgebenden FP Code gestohlen wird.Sonst ist pand wahrscheinlich eine bessere Wahl. Bei der AMD BD-Familie wird pandn trotzdem in der ivec-Domäne ausgeführt, so dass Sie die Umgehungsverzögerung zwischen int- und FP-Vektoren nicht vermeiden (die Sie andernfalls verwalten könnten, wenn Sie andnps anstelle von movmskps verwenden, in dieser Version, die nur ptest , nicht cmpps ) verwendet. Beachten Sie auch, dass die Reihenfolge der Befehle für die menschliche Lesbarkeit gewählt wurde. Wenn Sie den FP-Vergleich (A, B) früher als% pcmpeqd verwenden, kann dies der CPU dabei helfen, einen Zyklus früher zu beginnen.

Wenn ein Operand wiederverwendet wird, sollte es möglich sein, sein eigenes NaN-Ergebnis wiederzuverwenden. Der neue Operand benötigt immer noch seine Selbst-NaN-Prüfung und einen Vergleich mit dem wiederverwendeten Operanden. Daher speichern wir nur ein ANDPS / movaps .

Wenn sich die Vektoren im Speicher befinden, muss mindestens einer von ihnen mit einem separaten Ladevorgang geladen werden. Der andere kann einfach zweimal aus dem Speicher referenziert werden. Das saugt, wenn es nicht ausgerichtet ist oder der Adressierungsmodus kann nicht Micro-Fuse , könnte aber nützlich sein. Wenn einer der Operanden zu cmpps ein Vektor ist, von dem bekannt ist, dass er keine NaNs aufweist (z. B. ein Register mit Nullen), findet vcmpps NaNs in vcmpunord_qps xmm2, xmm15, [rsi] .

Wenn wir [rsi] nicht verwenden wollen, können wir das gleiche Ergebnis erhalten, indem wir die entgegengesetzten Vergleiche verwenden, aber sie mit dem entgegengesetzten logischen Operator (AND vs. OR) kombinieren.

Andere Ideen: unvollendet, nicht lebensfähig, kaputt oder schlechter als oben

Das Nur-Eins-Ergebnis eines echten Vergleichs ist eine Codierung von PTEST . ( Probieren Sie es aus . Vielleicht können wir vermeiden, NaN oder POR zu verwenden, um Ergebnisse von% zu kombinieren co_de% auf jedem Operanden getrennt?

PAND dreht nur das Endergebnis für jeden Fall, mit dem "Odd-Man-Out" immer noch in der ersten Zeile.

Wir können nur das gewünschte Ergebnis erhalten (wahr, wenn A und B beide NaN sind), wenn beide Eingaben invertiert sind (NaN - & gt; Nicht-NaN und umgekehrt). Dies bedeutet, dass wir diese Idee für cmpps als Ersatz für cmpordps xmm2, xmm1 verwenden könnten, nachdem wir cmpordps für A und B gemacht haben. Das ist nicht sinnvoll: Auch wenn wir AVX, aber nicht AVX2 haben, können wir pand verwenden. und cmpordps self,self (und vandps seit vandnps ist nur AVX2). Bitwise Booleans sind nur Single-Cycle-Latenzzeiten und binden nicht die Ausführungspunkte des Vektor-FP-Add, die bereits einen Engpass für diesen Code darstellen.

vmovmskps

Ich habe eine Weile mit dem Handbuch grokking seine Operation verbracht.

Es kann ein Zielelement ändern, wenn ein Quellenelement NaN ist, aber das kann nicht von irgendetwas über das Zielelement abhängig sein.

Ich hatte gehofft, ich könnte mir einen Weg nach vptest einfallen lassen und dann das Ergebnis mit jedem Quelloperanden korrigieren (um die booleschen Anweisungen zu erhalten, die die Ergebnisse von 3 VFIXUPIMMPS -Anweisungen kombinieren). Ich bin mir jetzt ziemlich sicher, dass das unmöglich ist, weil das Wissen, dass ein Operand NaN ist, alleine nicht ausreicht, um das vcmpneqps Ergebnis zu ändern.

Ich denke, die einzige Möglichkeit, vcmpps zu verwenden, besteht darin, NaNs in jedem Quelloperanden separat zu erkennen, wie IEEE_equal(A,B) , aber schlechter. Oder als wirklich blöder Ersatz für vfixupimmps , Erkennung von entweder 0 oder All-Einsen (NaN) in den Maskenresultaten früherer Vergleiche.

AVX512 Maskenregister

Die Verwendung von AVX512-Maskenregistern könnte helfen, die Ergebnisse von Vergleichen zu kombinieren. Die meisten AVX512-Vergleichsbefehle setzen das Ergebnis in ein Maskenregister anstelle eines Maskenvektors in einem Vektorregister, so dass wir haben, die Dinge auf diese Weise zu tun, wenn wir in 512b-Blöcken arbeiten wollen.

vcmpunord_qps schreibt in ein Maskenregister, optional maskiert durch ein anderes Maskenregister. Indem nur die QNaN- und SNaN-Bits von imm8 gesetzt werden, können wir eine Maske erhalten, wo NaNs in einem Vektor sind. Indem wir alle anderen Bits setzen, können wir die Umkehrung erhalten.

Indem wir die Maske von A als eine Nullmaske für andps auf B verwenden, können wir die beiden NaN-Positionen mit nur 2 Befehlen anstelle des üblichen cmp / cmp / combine finden. Deshalb speichern wir eine Anweisung VFPCLASSPS k2 {k1}, xmm2, imm8 oder vfpclassps . Übrigens frage ich mich, warum es keine Operation OR-NOT gibt. Wahrscheinlich kommt es sogar seltener als AND-NOT, oder sie wollten einfach nicht or im Befehlssatz.

Weder Yasm noch Nasm können dies zusammenstellen, also bin ich mir nicht einmal sicher, ob ich die Syntax korrekt habe!

Wir könnten dasselbe Maskenregister sowohl als Zeromask als auch als Ziel für die 2. andn insn wiederverwenden, aber ich habe verschiedene Register verwendet, falls ich sie in einem Kommentar unterscheiden wollte. Dieser Code benötigt mindestens zwei Maskenregister, aber keine zusätzlichen Vektorregister. Wir könnten auch porn anstelle von vfpclassps als Ziel für k0 verwenden, da wir es nicht als Prädikat, sondern nur als dest und src verwenden müssen. ( k3 ist das Register, das nicht als Prädikat verwendet werden kann, da dieses Kodierungsmittel stattdessen "keine Maskierung" bedeutet.)

Ich bin nicht sicher, ob eine einzelne Maske mit dem vcmpps Ergebnis für jedes Element erstellen könnte, ohne eine k0 Anweisung, um zwei Masken zu einem bestimmten Zeitpunkt zu kombinieren (zB reflexive_equal ) von k... ). Masken funktionieren nur als Nullmasken, nicht als Einmasken, die ein Ergebnis auf Eins erzwingen können. Daher funktioniert die Kombination der kandnw -Ergebnisse nur als UND. Also denke ich, dass wir bei 1-Means-NaN feststecken, was der falsche Sinn ist, es als Zeromask mit ktestw zu benutzen. Doing vfpclassps zuerst, und dann mit dem Maskenregister als Ziel und Prädikat für vcmpps , hilft auch nicht. Merge-Masking anstelle von Zero-Masking würde den Zweck erfüllen, ist aber nicht verfügbar, wenn in ein Maskenregister geschrieben wird.

Wenn vcmpps am Ende 2 uops wie vfpclassps ist und nicht Makro-fusionieren kann, dann ist ktest / test-and-branch wahrscheinlich billiger als ptest / jcc. Hoffentlich wird es nur ein UOP sein, da Maskenregister eher ganzzahlige Register sind und von Anfang an so ausgelegt werden können, dass sie sich den Flags "nah" annähern. kmov eax, k2 wurde nur in SSE4.1 hinzugefügt, nach vielen Generationen von Designs ohne Interaktion zwischen Vektoren und ktest k1,k2 .

ptest richtet dich jedoch auf popcnt, bsf oder bsr ein. ( EFLAGS / kmov fusioniert nicht, also werden Sie in einer Suchschleife wahrscheinlich immer noch / jcc und nur bsf testen wollen, wenn eine Nicht-Null gefunden wird. Das zusätzliche Byte zum Kodieren von tzcnt doesn Ich kaufe dir nichts, außer du machst etwas Zweigloses, weil bsf immer noch ZF auf einen Null-Eingang setzt, obwohl das Ziel-Register nicht definiert ist. jcc gibt bsf , obwohl es auch nützlich sein kann, wenn Sie wissen, dass die Eingabe nicht Null ist.)

Wir können auch lzcnt verwenden und unsere Ergebnisse anders kombinieren:

Dies funktioniert nur, wenn die Größe von 32 - bsr genau der Anzahl der Elemente in unseren Vektoren entspricht. z.B. Ein 256-b-Vektor von doppeltpräzisen Elementen hat nur 4 Elemente, aber vcmpEQps setzt immer noch CF entsprechend den niedrigen 8 Bits der Eingabemaskenregister.

Nur Integer-Ops verwenden

Anders als NaN ist +/- 0 der einzige Zeitpunkt, an dem sich IEEE_equal von bitwise_equal unterscheidet. (Es sei denn, ich verpasse etwas. Überprüfen Sie diese Annahme vor der Verwendung!)% Co_de% und kortest haben alle ihre Bits null, außer dass kortestb das Vorzeichen-Bit gesetzt hat (das MSB).

Wenn wir verschiedene NaN-Kodierungen ignorieren, ist bitwise_equal das Ergebnis, das wir wollen, außer im Fall von +/- 0. +0 wird überall 0 sein, mit Ausnahme des Vorzeichenbits, wenn A und B +/- 0 sind. Eine Linksverschiebung um Eins macht alles - Null oder Nicht-Null - abhängig davon, ob wir die Bitweise überschreiben müssen oder nicht -gleicher Test.

Dies verwendet eine weitere Anweisung als -0 , weil wir die Funktionalität, die wir benötigen, mit -0 / A OR B emulieren. (oder cmpneqps um eins, aber das ist ein Byte länger. Es läuft auf einem anderen Port als por , aber Sie müssen die Port-Verteilung des umgebenden Codes berücksichtigen, um dies in die Entscheidung einzubeziehen.)

Dieser Algorithmus könnte auf verschiedenen SIMD-Architekturen nützlich sein, die nicht die gleichen Vektor-FP-Tests zum Nachweis von NaN bereitstellen.

Die Latenz ist um einen oder zwei Zyklen niedriger als die paddD -Version.

Wir nutzen hier wirklich pslld aus: Verwenden Sie ANDN zwischen zwei verschiedenen Operanden und verwenden Sie den Vergleich der gesamten Sache mit Null. Wir können es nicht durch pcmpeq ersetzen, weil wir alle Bits überprüfen müssen, nicht nur das Vorzeichen-Bit jedes Elements.

Ich habe das nicht wirklich getestet, es könnte also falsch sein, selbst wenn meine Schlussfolgerung, dass +/- 0 das einzige Mal ist, dass IEEE_equal sich von bitwise_equal unterscheidet (anders als NaNs).

Die Behandlung nicht-bitweise identischer NaNs mit Integer-Ops ist es wahrscheinlich nicht wert. Die Codierung ist so ähnlich wie +/- Inf, dass mir keine einfachen Überprüfungen einfallen, die das nicht tun würden nimm mehrere Anweisungen. In Inf sind alle Exponenten-Bits und eine Mantisse mit allen Nullwerten gesetzt. In NaN sind alle Exponentenbits gesetzt, mit einer Mantisse ungleich null, die man als Mantisse bezeichnet (also gibt es 23 Nutzlastbits). Das MSB der Mantisse wird als cmpneqps -Flag interpretiert, um Signalisierung / stille NaNs zu unterscheiden. Siehe auch Intel Handbuch vol1, Tabelle 4-3 ( PTEST ).

Wenn nicht -Inf die Top-9-Bit-Set-Codierung verwendet, könnten wir nach NaN mit einem vorzeichenlosen Vergleich für pandn / movmskps suchen. ( is_quiet ist Single-Precision + Inf). Beachten Sie jedoch, dass Floating-Point Number and NaN Encodings / A > 0x7f800000 signierte ganze Zahlen sind. AVX512F 0x7f800000 ist ein vorzeichenloser Vergleich (dest = ein Maskenregister).

Die Idee des OP: pcmpgtd

Der Vorschlag des OP für pcmpgtq kann nicht funktionieren, und auch keine Variation davon. Sie können den Unterschied zwischen einem NaN und zwei NaNs nicht nur aus zwei Vergleichen mit umgekehrten Operanden unterscheiden. Sogar das Mischen von Prädikaten kann nicht helfen: Kein VPCMPUD Prädikat unterscheidet einen Operanden, der NaN ist, von beiden Operanden, der NaN ist , oder hängt davon ab, ob es der erste oder der zweite Operand ist, der NaN ist.Daher ist es für eine Kombination von ihnen unmöglich, diese Informationen zu haben.

Paul Rs Lösung, einen Vektor mit sich selbst zu vergleichen, lässt uns erkennen, wo es NaNs gibt und "manuell" handhaben. Keine Kombination der Ergebnisse von !(a<b) && !(b<a) zwischen den beiden Operanden ist ausreichend, aber die Verwendung anderer Operanden als !(a<b) && !(b<a) und VCMPPS hilft. (Entweder ein bekannter-Nicht-NaN-Vektor oder derselbe Operand zweimal).

Ohne Inversion findet der bitweise NaN-Code, wenn mindestens ein Element gleich ist. (Es gibt keine Umkehrung für VCMPPS , daher können wir keine anderen logischen Operatoren verwenden und erhalten dennoch einen Test für all-equal):

A ist auf diese Weise nicht nützlich, da die Kombination mit OR das einzig Nützliche ist.

Hier ist eine mögliche Lösung - sie ist jedoch nicht sehr effizient und erfordert 6 Anweisungen:

Beachten Sie, dass die gesamte obige Logik invertiert ist, wodurch der Code ein wenig schwer zu folgen ist ( OR s sind effektiv AND s und umgekehrt ).