x86 min/max-asm-Anweisungen?
Gibt es irgendwelche asm-Anweisungen, können speed-up-Berechnung von min/max eines Vektor von Double/Integer für die Core-i7-Architektur?
Update:
Ich hatte nicht erwartet, wie Reich Antworten, danke.
So sehe ich, dass max/min ist möglich ohne Verzweigung.
Ich habe die sub-Frage:
Gibt es eine effiziente Möglichkeit, um den index der größten double in array?
- Was ist die Sprache des Gastlandes? Wenn es c/c++ würde ich nicht Sorge über es zu viel.
- max von rund 300 verdoppelt, ist in die innere Schleife des großen Programms. 85% der Zeit in 10 aus 8'000 Zeilen code. Der Host-Sprache spielt keine Rolle, nur weil der, dass. Aber ja es ist C++
- Verwandte: Was ist die Anweisung, die gibt astfreie FP min-und max-auf x86? hat weitere Details über MINSS / MAXSS / MINSD / MAXSD, einschließlich Ihrer NaN Verhalten.
Du musst angemeldet sein, um einen Kommentar abzugeben.
SSE4 hat
PMAXSD
oderPMAXUD
für 32 bit signed/unsigned Integer, die nützlich sein könnten.SSE2 hat
MAXPD
undMAXSD
vergleichen zwischen und über Paare verdoppelt, so dass Sie Folgen, n/2-1 MAXPDs mit einem MAXSD man die max eines Vektor von n, mit den üblichen interlacing von Lasten und Operationen.Gibt es MIN Entsprechungen der oben genannten.
Für die Doppel-Fall, sind Sie wahrscheinlich nicht gehen, um besser in assembler als eine halbwegs anständige C++ - compiler in den SSE Modus:
wo min_max berechnet, min und max in einem array von 500 verdoppelt 100.000 mal mit einem naiv-Schleife:
In der Antwort auf Teil zwei, der traditionellen Optimierung zu entfernen, die Verzweigung von einem max-Betrieb ist der Vergleich der Werte, Holen Sie die fahne als ein einzelnes bit ( Angabe 0 oder 1 ), subtract ( Angabe 0 oder 0xffff_ffff) und 'und' es mit den xor der beiden möglichen Ergebnisse, so erhält man den Gegenwert von
( a > best ? ( current_index ^ best_index ) : 0 ) ^ best_index )
. Ich bezweifle, dass es ein einfaches SSE Weg, das zu tun, einfach, weil SSE neigt zu betreiben, auf gepackten Werte eher als tagged values; es gibt einige horizontale index-Operationen, so könnten Sie versuchen, das finden der max, dann subtrahieren, dass von allen Elementen des ursprünglichen vectors, dann versammeln sich die Vorzeichen-bit, und die null-eins signiert entsprechen würde, auf den index der max, aber das würde wahrscheinlich nicht eine Verbesserung, es sei denn, Sie wurden mit shorts oder bytes.MAXPD
hat 3 oder 4-Zyklus-Latenz, aber einen Durchsatz von 1 pro Zyklus, so müssen Sie dem compiler zu emittieren asm mit mehreren Vektoren und fasst Sie am Ende des Arrays.) klappern neigt dazu, während auto-Vektorisieren, aber gcc immer noch in der Regel nicht.MAXPS und MINPS von SSE arbeiten beide auf gepackten single-precision-floating-point-zahlen. PMAXSW, PMINSW, PMAXUB und PMINUB arbeiten alle auf gepackten 8-bit-Worte, die entweder signed oder unsigned. Bitte beachten Sie, dass dieser Vergleich der beiden input-SSE-Register oder Adresse Orten-element-Weise und speichert das Ergebnis in ein SSE-register oder eine Speicherstelle.
Den SSE2-Versionen MAXPS und MINPS sollte auf double precision floats.
Welche compiler-und Optimierungs-flags verwenden Sie? gcc 4.0 und besser sollte automatisch Vektorisieren Operationen, wenn das Ziel unterstützt werden, frühere Versionen benötigen möglicherweise eine spezifische Flagge.
wenn Ihr mit Intel IPP Bibliothek, die Vektor - statistische Funktionen zu berechnen, Vektor-min/max (unter anderem)
In der Antwort auf Ihre zweite Frage: auf den meisten Plattformen gibt es Bibliotheken, die bereits die optimierte Implementierungen dieser Vorgang (und die meisten anderen einfachen Vektor-Operationen). Verwenden Sie.
vDSP_maxviD( )
undcblas_idamax( )
im Beschleunigen.Rahmencblas_idamax( )
cblas_idamax( )
in der BLAS-Bibliothek, die möglicherweise oder möglicherweise nicht gut abgestimmt, je nach Ihrer Provenienz; Benutzer, die Wert auf Leistung wird in der Regel eine gute Umsetzung (oder davon überzeugt werden können, um eine zu installieren)Update: ich habe gerade gemerkt, dass man sagte, "array", nicht "Vektor" in Teil 2. Ich lasse das hier trotzdem, falls es nützlich.
re: Teil zwei: finden Sie den index der min/max-element in ein SSE-Vektor:
Tun eine horizontale maximale. Für eine 128b Vektor von 2
double
Elemente, das ist nur eineshufpd
+maxpd
zu verlassen, die Folge ausgestrahlt, um die beiden Elemente.Anderen Fällen, es wird natürlich mehr Schritte. Sehen Am schnellsten horizontal float Vektorsumme auf x86 für Ideen, Austausch
addps
mitmaxps
oderminps
. (Aber beachten Sie, dass 16-bit-Ganzzahl, die eine Besondere ist, weil Sie verwenden können, SSE4phminposuw
. Für max, subtrahieren von 255)Tun verpackt-ein Vergleich zwischen dem Vektor ursprünglichen Vektor und den Vektor, wo jedes element ist die max.
(
pcmpeqq
integer bit-Muster oder die üblichencmpeqpd
würden beide arbeiten für dendouble
Fall).int _mm_movemask_pd (__m128d a)
(movmskpd
) zu bekommen das Vergleichsergebnis als ganze Zahl bitmap.bsf
) es für den (ersten) Spiel:index = _bit_scan_forward(cmpmask)
. cmpmask = 0 unmöglich ist, wenn Sie integer vergleicht (weil mindestens ein element übereinstimmen, selbst wenn Sie NaN).Diese stellen nur 6 Anweisungen (einschließlich einer
movapd
). Yup, genau überprüft die Godbolt compiler explorer und das tut er, mit SSE.Beachten Sie, dass
_mm_max_pd
ist nicht kommutativ, mit NaN-Eingänge. Wenn NaN ist möglich, und Sie kümmern sich nicht darum, Leistung auf Intel-Nehalem, sollten Sie überlegen, mit_mm_cmpeq_epi64
zu vergleichen, bit-Muster. Bypass-Verzögerung von float-vec-int ist ein problem auf Nehalem, obwohl.NaN != NaN IEEE floating point, also die
_mm_cmpeq_pd
Ergebnis Maske könnte alles sein-null in der all-NaN Fall.Andere Sache, die Sie tun können, in der 2-element-Fall immer eine 0 oder 1 ist, ersetzen Sie den bit-scan mit
cmpmask >> 1
. (bsf
ist komisch mit Eingabe = alle null).In der Antwort auf Ihre zweite Frage, kann es sinnvoll sein, Sie zu denken, über die Art und Weise, die Sie sammeln und speichern diese Daten.
Können Sie speichern die Daten in einem B-Baum hält, dass die Daten sortiert zu allen Zeiten, es erfordert nur logarithmischen vergleichen-Operationen.
Dann wissen Sie jederzeit, wo das maximum ist.
http://en.wikipedia.org/wiki/B_tree