Ich möchte zwei Little-Endian 256-Bit-Werte mit A64 Neon Anweisungen (Asm) effizient vergleichen.A64 Neon SIMD - 256-Bit-Vergleich
Gleichheit (=)
Für Gleichheit, ich habe bereits eine Lösung:
bool eq256(const UInt256 *lhs, const UInt256 *rhs) {
bool result;
Zunächst werden die beiden Werte in SIMD-Register laden.
__asm__("ld1.2d { v0, v1 }, %1 \n\t"
"ld1.2d { v2, v3 }, %2 \n\t"
Vergleichen Sie jedes 64-Bit-Glied der Werte miteinander. Dies führt zu -1 (alle gesetzten Bits) für diese Glieder, die gleich sind, und zu 0 (alle Bits löschen), wenn sich ein Bit unterscheidet.
"cmeq.2d v0, v0, v2 \n\t"
"cmeq.2d v1, v1, v3 \n\t"
reduzieren das Ergebnis von 2 Vektoren zu 1-Vektor, nur den einen zu halten, die „0 (alle Bits clear)“ enthält, wenn es irgendeine.
Reduzieren Sie das Ergebnis von 1 Vektor auf 1 Byte und behalten Sie nur ein Byte mit Nullen bei, falls vorhanden.
"uminv.16b b0, v0 \n\t"
In ARM-Register wechseln, dann mit 0xFF vergleichen. Dies ist das Ergebnis.
"umov %w0, v0.b[0] \n\t"
"cmp %w0, 0xFF \n\t"
"cset %w0, eq "
: "=r" (result)
: "m" (*lhs->value), "m" (*rhs->value)
: "v0", "v1", "v2", "v3", "cc");
return result;
}
Fragen
Ist dies effizienter als die vier Vergleiche mit einfachen alten ARM-Register zu tun?
- z.B. Gibt es eine Quelle, die Timings für die verschiedenen Operationen angibt? Ich mache das auf iPhone 5s.
Gibt es eine Möglichkeit, dies noch weiter zu optimieren? Ich denke, dass ich viele Zyklen verschwende, nur um den gesamten Vektor auf einen einzigen skalaren booleschen Wert zu reduzieren.
Weniger als Vergleich (<)
Lasst uns die beiden Ints als Tupel von 64-Bit-Glieder darstellen (Little-Endian):
- lhs = (l0 , l1, l2, l3)
- rhs = (r0, r1, r2, r3)
Dann lhs < rhs wenn diese der Wert true:
(l3 < r3) & 1 & 1 & 1 |
(l3 = r3) & (l2 < r2) & 1 & 1 |
(l3 = r3) & (l2 = r2) & (l1 < r1) & 1 |
(l3 = r3) & (l2 = r2) & (l1 = r1) & (l0 < r0)
SIMD-Befehle nun verwendet werden, können mehrere Operanden zu einem Zeitpunkt, zu bewerten.Angenommen, (l1, l2), (l3, l4), (r1, r2), (r3, r4) ist die Art, wie die zwei 256-Bit-Zahlen gespeichert werden, können wir leicht alle erforderlichen Werte (nützliche Werte in fett):
- cmlo.2d =>(l1 < r1), (l2 < r2)
- cmlo.2d =>(l3 < r3), (l4 < r4)
- cmeq.2d => (l1 = r1), (l2 = r2)
- cmeq.2d =>(l3 = r3), (l4 = r4)
Fragen
- Mit diesen Werten in vier SIMD-Register, frage ich mich jetzt Was ist die beste Strategie, um die & und | Operatoren, und dann reduziert es auf einen einzigen Boolean.
aktualisieren
ich zusammen nur gestanzt, um eine funktionierende Implementierung für "kleiner als".
Grundsätzlich ersetzte ich die 1s oben mit einer doppelten Bedingung, weil A & A == A & 1.
Dann lege ich die drei 2x2 Quadrate in meiner Matrix, und bitweise UND ihnen. Jetzt reduziere ich mit bitweisen ORs - zuerst von zwei Vektoren zu einem Vektor, dann zu einem Byte, dann zum ARM-Register kopieren und auf 0xFF testen. Gleiches Muster wie oben für Gleichheit.
Die obige Frage ist immer noch gültig. Ich bin mir nicht sicher, ob der Code noch optimal ist und frage mich, ob ich ein allgemeines SIMD-Muster verpasst habe, um solche Sachen effizienter zu machen. Auch: Lohnt es sich NEON für solche Fälle, wenn die Eingangsoperanden aus dem Speicher kommen?
bool lt256(const UInt256 *lhs, const UInt256 *rhs) {
bool result;
__asm__(// (l3 < r3) & (l3 < r3) |
// (l3 = r3) & (l2 < r2) |
// (l3 = r3) & (l2 = r2) & (l1 < r1) & (l1 < r1) |
// (l3 = r3) & (l2 = r2) & (l1 = r1) & (l0 < r0)
"ld1.2d { v0, v1 }, %1 \n\t"
"ld1.2d { v2, v3 }, %2 \n\t"
// v0: [ l3 = r3 ] [ l2 = r2 ]
// v1: [ l0 < r0 ] [ l1 < r1 ]
// v2: [ l0 = r0 ] [ l1 = r1 ]
// v3: [ l2 < r2 ] [ l3 < r3 ]
// v4: [ l2 = r2 ] [ l3 = r3 ]
"cmeq.2d v4, v1, v3 \n\t"
"cmlo.2d v3, v1, v3 \n\t"
"cmlo.2d v1, v0, v2 \n\t"
"cmeq.2d v2, v0, v2 \n\t"
"ext.16b v0, v4, v4, 8 \n\t"
// v2: [ l1 < r1 ] [ l1 = r1 ]
// v1: [ l1 < r1 ] [ l0 < r0 ]
"trn2.2d v2, v1, v2 \n\t"
"ext.16b v1, v1, v1, 8 \n\t"
// v1: [ l1 < r1 & l1 < r1 ] [ l1 = r1 & l0 < r0 ]
"and.16b v1, v2, v1 \n\t"
// v2: [ l3 < r3 ] [ l3 = r3 ]
// v3: [ l3 < r3 ] [ l2 < r2 ]
"ext.16b v2, v3, v0, 8 \n\t"
"ext.16b v3, v3, v3, 8 \n\t"
// v3: [ l3 < r3 & l3 < r3 ] [ l3 = r3 & l2 < r2 ]
"and.16b v3, v2, v3 \n\t"
// v2: [ l3 = r3 ] [ l3 = r3 ]
// v4: [ l2 = r2 ] [ l2 = r2 ]
"ext.16b v2, v4, v0, 8 \n\t"
"ext.16b v4, v0, v4, 8 \n\t"
// v2: [ l3 = r3 & l2 = r2 ] [ l3 = r3 & l2 = r2 ]
"and.16b v2, v2, v4 \n\t"
// v1: [ l3 = r3 & l2 = r2 & l1 < r1 & l1 < r1 ]
// [ lr = r3 & l2 = r2 & l1 = r1 & l0 < r0 ]
"and.16b v1, v2, v1 \n\t"
// v1: [ l3 < r3 & l3 < r3 |
// l3 = r3 & l2 = r2 & l1 < r1 & l1 < r1 ]
// [ l3 = r3 & l2 < r2 |
// lr = r3 & l2 = r2 & l1 = r1 & l0 < r0 ]
"orr.16b v1, v3, v1 \n\t"
// b1: [ l3 < r3 & l3 < r3 |
// l3 = r3 & l2 = r2 & l1 < r1 & l1 < r1 |
// l3 = r3 & l2 < r2 |
// lr = r3 & l2 = r2 & l1 = r1 & l0 < r0 ]
"umaxv.16b b1, v1 \n\t"
"umov %w0, v1.b[0] \n\t"
"cmp %w0, 0xFF \n\t"
"cset %w0, eq"
: "=r" (result)
: "m" (*lhs->value), "m" (*rhs->value)
: "v0", "v1", "v2", "v3", "v4", "cc");
return result;
}
Wie ist 'UInt256' an anderer Stelle verwendet werden, dh die Werte eher in SIMD sein Register, Allzweck- Register oder Speicher vorher? Ich würde mir vorstellen, dass 'cmp' und 3' ccmp's weniger Overhead haben als ein Haufen SIMD-Register-Jonglieren, aber ein paar GP-Register zu verschütten und die Werte zu laden, kann das Gleichgewicht auf die andere Seite bringen. Ich vermute, dass die Frage der Gesamteffizienz am besten durch das Benchmarking beantwortet wird, da es sich dabei um den Rest des Codes handelt (Registerdruck, Cache-Nutzung usw.). – Notlikethat
Sie befinden sich bereits im Speicher und sind geladen mit " ld1 ". – Etan