Gibt es einen Leistungsgewinn (ohne Mikrooptimierung) durch Codierung?
float f1 = 200f / 2
im Vergleich zu
float f2 = 200f * 0.5
Ein Professor von mir hat mir vor einigen Jahren erzählt, dass Gleitkommadivisionen langsamer sind als Gleitkommamultiplikationen, ohne das Warum zu erläutern.
Gilt diese Aussage für die moderne PC-Architektur?
Update1
Berücksichtigen Sie in Bezug auf einen Kommentar auch diesen Fall:
float f1;
float f2 = 2
float f3 = 3;
for( i =0 ; i < 1e8; i++)
{
f1 = (i * f2 + i / f3) * 0.5; //or divide by 2.0f, respectively
}
Update 2 Zitat aus den Kommentaren:
[Ich möchte] wissen, welche algorithmischen / architektonischen Anforderungen dazu führen, dass die Division in der Hardware erheblich komplizierter ist als die Multiplikation
c++
floating-point
micro-optimization
sum1stolemyname
quelle
quelle
200f / 2
in100f
.Antworten:
Ja, viele CPUs können eine Multiplikation in 1 oder 2 Taktzyklen durchführen, aber die Division dauert immer länger (obwohl die FP-Division manchmal schneller ist als die Integer-Division).
Wenn Sie sich diese Antwort ansehen , werden Sie sehen, dass die Teilung 24 Zyklen überschreiten kann.
Warum dauert die Division so viel länger als die Multiplikation? Wenn Sie sich an die Grundschule erinnern, können Sie sich daran erinnern, dass die Multiplikation im Wesentlichen mit vielen gleichzeitigen Ergänzungen durchgeführt werden kann. Die Division erfordert eine iterative Subtraktion, die nicht gleichzeitig durchgeführt werden kann, daher dauert es länger. Tatsächlich beschleunigen einige FP-Einheiten die Division, indem sie eine wechselseitige Approximation durchführen und damit multiplizieren. Es ist nicht ganz so genau, aber etwas schneller.
quelle
x ^ y
Multiplizieren mitx ^ -y
gleich der Division. FP-Nummern werden jedoch als gespeichertx * 2^y
. Multiplizieren mitx * 2^-y
ist nur Multiplikation.Seien Sie sehr vorsichtig mit der Teilung und vermeiden Sie sie, wenn möglich. Heben Sie beispielsweise
float inverse = 1.0f / divisor;
aus einer Schleife heraus und multiplizieren Sie mitinverse
innerhalb der Schleife. (Wenn der Rundungsfehler ininverse
akzeptabel ist)Normalerweise ist
1.0/x
es nicht genau alsfloat
oder darstellbardouble
. Es wird genau sein , wennx
eine Potenz von 2 ist dieser Compiler optimieren läßt ,x / 2.0f
umx * 0.5f
im Ergebnis ohne Änderung.Damit der Compiler diese Optimierung auch dann für Sie durchführen kann, wenn das Ergebnis nicht genau ist (oder mit einem Laufzeitvariablen-Divisor), benötigen Sie Optionen wie
gcc -O3 -ffast-math
. Insbesondere-freciprocal-math
(aktiviert durch-funsafe-math-optimizations
aktiviert durch-ffast-math
) lässt der Compiler ersetzenx / y
mit ,x * (1/y)
wenn das ist nützlich. Andere Compiler haben ähnliche Optionen, und ICC kann standardmäßig eine "unsichere" Optimierung aktivieren (ich denke, das tut es, aber ich vergesse es).-ffast-math
Es ist oft wichtig, die automatische Vektorisierung von FP-Schleifen zu ermöglichen, insbesondere von Reduktionen (z. B. Summieren eines Arrays zu einer skalaren Summe), da die FP-Mathematik nicht assoziativ ist. Warum optimiert GCC nicht a * a * a * a * a * a bis (a * a * a) * (a * a * a)?Beachten Sie, dass C ++ Compiler kann falten
+
und*
in eine FMA in einigen Fällen (wenn man für ein Ziel kompilieren , dass dies unterstützt, wie-march=haswell
), aber sie können nicht das tun mit/
.Die Division hat eine schlechtere Latenz als die Multiplikation oder Addition (oder FMA ) um den Faktor 2 bis 4 auf modernen x86-CPUs und einen schlechteren Durchsatz um den Faktor 6 bis 40 1 (für eine enge Schleife, die nur Division statt nur Multiplikation ausführt).
Die Divide / sqrt-Einheit ist aus Gründen, die in der Antwort von @ NathanWhitehead erläutert wurden, nicht vollständig per Pipeline . Die schlechtesten Verhältnisse gelten für 256b-Vektoren, da die Teilungseinheit (im Gegensatz zu anderen Ausführungseinheiten) normalerweise nicht die volle Breite aufweist, sodass breite Vektoren in zwei Hälften ausgeführt werden müssen. Eine nicht vollständig Pipeline-Ausführungseinheit ist so ungewöhnlich, dass Intel-CPUs über einen
arith.divider_active
Hardware-Leistungsindikator verfügen, mit dem Sie Code finden können, der Engpässe beim Teilerdurchsatz anstelle der üblichen Engpässe beim Front-End- oder Ausführungsport aufweist. (Oder häufiger, Speicherengpässe oder lange Latenzketten, die die Parallelität auf Befehlsebene einschränken, führen dazu, dass der Befehlsdurchsatz weniger als ~ 4 pro Takt beträgt.)FP-Division und sqrt auf Intel- und AMD-CPUs (außer KNL) werden jedoch als ein einziges UOP implementiert, sodass sie nicht unbedingt einen großen Durchsatz auf den umgebenden Code haben . Der beste Fall für eine Division ist, wenn die Ausführung außerhalb der Reihenfolge die Latenz verbergen kann und wenn es viele Multiplikationen und Adds (oder andere Arbeiten) gibt, die parallel zur Division erfolgen können.
(Die Ganzzahldivision wird unter Intel als mehrere Uops mikrocodiert, sodass sie immer mehr Einfluss auf den umgebenden Code hat, wenn sich die Ganzzahl multipliziert. Die Hochleistungs-Ganzzahldivision ist weniger gefragt, sodass die Hardwareunterstützung nicht so ausgefallen ist. Verwandte Themen
idiv
: Mikrocodierte Anweisungen wie can Ausrichtungsempfindliche Front-End-Engpässe verursachen .)So wird das zum Beispiel wirklich schlecht sein:
for () a[i] = b[i] / scale; // division throughput bottleneck // Instead, use this: float inv = 1.0 / scale; for () a[i] = b[i] * inv; // multiply (or store) throughput bottleneck
Alles, was Sie in der Schleife tun, ist Laden / Teilen / Speichern, und sie sind unabhängig, sodass der Durchsatz zählt, nicht die Latenz.
Eine Reduzierung wie
accumulator /= b[i]
würde einen Engpass bei der Division oder Multiplikation der Latenz anstelle des Durchsatzes bedeuten. Mit mehreren Akkumulatoren, die Sie am Ende teilen oder multiplizieren, können Sie die Latenz verbergen und den Durchsatz trotzdem sättigen. Beachten Sie, dasssum += a[i] / b[i]
Engpässe bei deradd
Latenz oder beimdiv
Durchsatz auftreten, jedoch nicht bei derdiv
Latenz, da sich die Division nicht auf dem kritischen Pfad befindet (der von Schleifen übertragenen Abhängigkeitskette).Aber in so etwas ( Annäherung an eine Funktion wie
log(x)
mit einem Verhältnis von zwei Polynomen ) kann die Teilung ziemlich billig sein :for () { // (not shown: extracting the exponent / mantissa) float p = polynomial(b[i], 1.23, -4.56, ...); // FMA chain for a polynomial float q = polynomial(b[i], 3.21, -6.54, ...); a[i] = p/q; }
Für
log()
über den Bereich der Mantisse ein Verhältnis zweier Polynome der Ordnung N hat viel weniger Fehler als ein einzelnes Polynom mit 2N Koeffizienten und 2 parallel Auswertung gibt Ihnen eine Befehlsebene Parallelismus innerhalb eines einzelnen Schleifenkörper statt eines massiv langen dep chain, was die Ausführung von Out-of-Order-Vorgängen erheblich erleichtert.In diesem Fall besteht kein Engpass bei der Teilungslatenz, da bei einer Ausführung außerhalb der Reihenfolge mehrere Iterationen der Schleife über die Arrays im Flug beibehalten werden können.
Wir Engpass nicht auf divide Durchsatz solange unsere Polynome groß genug sind , dass wir eine Kluft nur für jeweils 10 FMA Anweisungen oder so. (Und in einem realen
log()
Anwendungsfall gibt es eine Menge Arbeit, bei der Exponent / Mantisse extrahiert und die Dinge wieder zusammengefügt werden, sodass zwischen den Teilungen noch mehr Arbeit zu erledigen ist.)Wenn Sie teilen müssen, ist es normalerweise am besten, einfach zu teilen, anstatt
rcpps
x86 verfügt über eine ungefähre reziproke Anweisung (
rcpps
), die nur 12 Bit Genauigkeit liefert. (AVX512F hat 14 Bit und AVX512ER hat 28 Bit.)Sie können dies verwenden, um
x / y = x * approx_recip(y)
auf eine tatsächliche Divide-Anweisung zu verzichten. (rcpps
itsef ist ziemlich schnell; normalerweise etwas langsamer als die Multiplikation. Es verwendet eine Tabellensuche von einer Tabelle innerhalb der CPU. Die Teilerhardware verwendet möglicherweise dieselbe Tabelle als Ausgangspunkt.)Für die meisten Zwecke
x * rcpps(y)
ist es zu ungenau, und eine Newton-Raphson-Iteration zur Verdoppelung der Genauigkeit ist erforderlich. Aber das kostet Sie 2 Multiplikationen und 2 FMAs und hat eine Latenz, die ungefähr so hoch ist wie eine tatsächliche Divisionsanweisung. Wenn alles tust du Teilung ist, dann kann es ein Durchsatz Sieg sein. (Aber Sie sollten diese Art von Schleife zunächst vermeiden, wenn Sie können, indem Sie die Division möglicherweise als Teil einer anderen Schleife ausführen, die andere Arbeiten ausführt.)Wenn Sie jedoch die Teilung als Teil einer komplexeren Funktion verwenden,
rcpps
beschleunigt das Teilen mit einerdivps
Anweisung durch das Selbst + das zusätzliche Mul + FMA normalerweise schneller , außer bei CPUs mit sehr geringemdivps
Durchsatz.(Zum Beispiel Knight's Landing, siehe unten. KNL unterstützt AVX512ER , sodass
float
dasVRCP28PS
Ergebnis für Vektoren bereits genau genug ist, um nur ohne Newton-Raphson-Iteration zu multiplizieren. Diefloat
Mantissengröße beträgt nur 24 Bit.)Spezifische Zahlen aus den Tabellen von Agner Fog:
Im Gegensatz zu jeder anderen ALU-Operation ist die Teilungslatenz / der Durchsatz von einigen CPUs datenabhängig. Dies liegt wiederum daran, dass es so langsam und nicht vollständig per Pipeline ist. Die Planung außerhalb der Reihenfolge ist bei festen Latenzen einfacher, da Rückschreibkonflikte vermieden werden (wenn derselbe Ausführungsport versucht, zwei Ergebnisse im selben Zyklus zu erzielen, z. B. durch Ausführen eines Befehls mit drei Zyklen und anschließend von zwei Operationen mit einem Zyklus). .
Im Allgemeinen sind die schnellsten Fälle, wenn der Divisor eine "runde" Zahl wie
2.0
oder ist0.5
(dh die base2-float
Darstellung hat viele nachgestellte Nullen in der Mantisse).float
Latenz (Zyklen) / Durchsatz (Zyklen pro Befehl, die genau das mit unabhängigen Eingaben hintereinander ausführen):scalar & 128b vector 256b AVX vector divss | mulss divps xmm | mulps vdivps ymm | vmulps ymm Nehalem 7-14 / 7-14 | 5 / 1 (No AVX) Sandybridge 10-14 / 10-14 | 5 / 1 21-29 / 20-28 (3 uops) | 5 / 1 Haswell 10-13 / 7 | 5 / 0.5 18-21 / 14 (3 uops) | 5 / 0.5 Skylake 11 / 3 | 4 / 0.5 11 / 5 (1 uop) | 4 / 0.5 Piledriver 9-24 / 5-10 | 5-6 / 0.5 9-24 / 9-20 (2 uops) | 5-6 / 1 (2 uops) Ryzen 10 / 3 | 3 / 0.5 10 / 6 (2 uops) | 3 / 1 (2 uops) Low-power CPUs: Jaguar(scalar) 14 / 14 | 2 / 1 Jaguar 19 / 19 | 2 / 1 38 / 38 (2 uops) | 2 / 2 (2 uops) Silvermont(scalar) 19 / 17 | 4 / 1 Silvermont 39 / 39 (6 uops) | 5 / 2 (No AVX) KNL(scalar) 27 / 17 (3 uops) | 6 / 0.5 KNL 32 / 20 (18uops) | 6 / 0.5 32 / 32 (18 uops) | 6 / 0.5 (AVX and AVX512)
double
Latenz (Zyklen) / Durchsatz (Zyklen pro Befehl):scalar & 128b vector 256b AVX vector divsd | mulsd divpd xmm | mulpd vdivpd ymm | vmulpd ymm Nehalem 7-22 / 7-22 | 5 / 1 (No AVX) Sandybridge 10-22 / 10-22 | 5 / 1 21-45 / 20-44 (3 uops) | 5 / 1 Haswell 10-20 / 8-14 | 5 / 0.5 19-35 / 16-28 (3 uops) | 5 / 0.5 Skylake 13-14 / 4 | 4 / 0.5 13-14 / 8 (1 uop) | 4 / 0.5 Piledriver 9-27 / 5-10 | 5-6 / 1 9-27 / 9-18 (2 uops) | 5-6 / 1 (2 uops) Ryzen 8-13 / 4-5 | 4 / 0.5 8-13 / 8-9 (2 uops) | 4 / 1 (2 uops) Low power CPUs: Jaguar 19 / 19 | 4 / 2 38 / 38 (2 uops) | 4 / 2 (2 uops) Silvermont(scalar) 34 / 32 | 5 / 2 Silvermont 69 / 69 (6 uops) | 5 / 2 (No AVX) KNL(scalar) 42 / 42 (3 uops) | 6 / 0.5 (Yes, Agner really lists scalar as slower than packed, but fewer uops) KNL 32 / 20 (18uops) | 6 / 0.5 32 / 32 (18 uops) | 6 / 0.5 (AVX and AVX512)
Ivybridge und Broadwell sind auch unterschiedlich, aber ich wollte den Tisch klein halten. (Core2 (vor Nehalem) hat eine bessere Teilerleistung, aber seine maximalen Taktraten waren niedriger.)
Atom, Silvermont und sogar Knight's Landing (Xeon Phi basierend auf Silvermont) weisen eine außergewöhnlich niedrige Teilungsleistung auf , und selbst ein 128b-Vektor ist langsamer als der Skalar. Die Jaguar-CPU mit geringem Stromverbrauch von AMD (in einigen Konsolen verwendet) ist ähnlich. Ein Hochleistungsteiler nimmt viel Werkzeugfläche ein. Xeon Phi hat eine geringe Leistung pro Kern und das Packen vieler Kerne auf einem Chip führt zu strengeren Einschränkungen des Chipbereichs als bei Skylake-AVX512. Es scheint, dass AVX512ER
rcp28ps
/ daspd
ist, was Sie auf KNL "verwenden" sollen.(Siehe dieses InstLatx64-Ergebnis für Skylake-AVX512, auch bekannt als Skylake-X. Zahlen für
vdivps zmm
: 18c / 10c, also die Hälfte des Durchsatzes vonymm
.)Lange Latenzketten werden zu einem Problem, wenn sie in einer Schleife ausgeführt werden oder wenn sie so lang sind, dass sie verhindern, dass die Ausführung außerhalb der Reihenfolge Parallelität zu anderen unabhängigen Arbeiten findet.
Fußnote 1: Wie ich diese Div vs. Mul-Leistungsverhältnisse zusammengestellt habe:
Das FP-Divide-Verhältnis gegenüber mehreren Leistungsverhältnissen ist sogar noch schlechter als bei CPUs mit geringem Stromverbrauch wie Silvermont und Jaguar und sogar bei Xeon Phi (KNL, wo Sie AVX512ER verwenden sollten).
Tatsächliche Divisions- / Multiplikationsdurchsatzverhältnisse für Skalar (nicht vektorisiert)
double
: 8 bei Ryzen und Skylake mit ihren verbesserten Teilern, aber 16-28 bei Haswell (datenabhängig und wahrscheinlicher gegen Ende des 28. Zyklus, sofern Ihre Teiler nicht rund sind Zahlen). Diese modernen CPUs haben sehr leistungsstarke Teiler, aber ihr 2-pro-Takt-Multiplikationsdurchsatz ist überwältigend. (Dies gilt umso mehr, wenn Ihr Code mit 256b AVX-Vektoren automatisch vektorisiert werden kann.) Beachten Sie auch, dass mit den richtigen Compileroptionen diese Multiplikationsdurchsätze auch für FMA gelten.Zahlen aus http://agner.org/optimize/ Befehlstabellen für Intel Haswell / Skylake und AMD Ryzen, für SSE-Skalar (ohne x87
fmul
/fdiv
) und für 256b AVX SIMD-Vektoren vonfloat
oderdouble
. Siehe auch diex86 Tag Wiki.quelle
Division ist von Natur aus eine viel langsamere Operation als Multiplikation.
Und dies kann tatsächlich etwas sein, das der Compiler in vielen Fällen aufgrund von Gleitkomma-Ungenauigkeiten nicht optimieren kann (und möglicherweise auch nicht möchte). Diese beiden Aussagen:
double d1 = 7 / 10.; double d2 = 7 * 0.1;
sind nicht semantisch identisch -
0.1
können nicht genau als a dargestellt werdendouble
, so dass am Ende ein etwas anderer Wert verwendet wird - das Ersetzen der Division durch Multiplikation würde in diesem Fall ein anderes Ergebnis ergeben!quelle
Ja. Jede mir bekannte FPU führt Multiplikationen viel schneller durch als Divisionen.
Moderne PCs sind jedoch sehr schnell. Sie enthalten auch Pipelining-Strukturen, die den Unterschied unter vielen Umständen vernachlässigbar machen können. Um das Ganze abzurunden, führt jeder anständige Compiler die Divisionsoperation aus, die Sie zur Kompilierungszeit mit aktivierten Optimierungen angezeigt haben. Für Ihr aktualisiertes Beispiel würde jeder anständige Compiler diese Transformation selbst durchführen.
Im Allgemeinen sollten Sie sich also darum kümmern, Ihren Code lesbar zu machen , und den Compiler sich darum kümmern, ihn schnell zu machen. Nur wenn Sie ein Problem mit der gemessenen Geschwindigkeit in dieser Zeile haben, sollten Sie sich Sorgen machen, Ihren Code aus Gründen der Geschwindigkeit zu pervertieren. Compiler wissen genau, was schneller ist als was auf ihren CPUs, und sind im Allgemeinen viel bessere Optimierer, als Sie jemals hoffen können.
quelle
-ffast-math
Option für diesen Zweck, aber es bricht viele Dinge und kann im Allgemeinen nicht verwendet werden.Überlegen Sie, was für die Multiplikation von zwei n-Bit-Zahlen erforderlich ist. Mit der einfachsten Methode nehmen Sie eine Zahl x und verschieben sie wiederholt und fügen sie bedingt einem Akkumulator hinzu (basierend auf einem Bit in der anderen Zahl y). Nach n Ergänzungen sind Sie fertig. Ihr Ergebnis passt in 2n Bits.
Für die Division beginnen Sie mit x von 2n Bits und y von n Bits, Sie möchten x / y berechnen. Die einfachste Methode ist die lange Teilung, jedoch binär. In jeder Phase führen Sie einen Vergleich und eine Subtraktion durch, um ein weiteres Bit des Quotienten zu erhalten. Dies dauert n Schritte.
Einige Unterschiede: Jeder Schritt der Multiplikation muss nur 1 Bit betrachten; Jede Stufe der Teilung muss während des Vergleichs n Bits betrachten. Jede Stufe der Multiplikation ist unabhängig von allen anderen Stufen (unabhängig von der Reihenfolge, in der Sie die Teilprodukte hinzufügen). Für die Teilung hängt jeder Schritt vom vorherigen Schritt ab. Dies ist eine große Sache in der Hardware. Wenn Dinge unabhängig voneinander erledigt werden können, können sie innerhalb eines Taktzyklus zur gleichen Zeit geschehen.
quelle
vdivpd ymm
) mit doppelter Genauigkeit hat einen 16-mal schlechteren Durchsatz als Multiplikation (vmulpd ymm
) und ist in früheren CPUs mit weniger leistungsfähiger Divisionshardware schlechter. agner.org/optimizeNewton Rhapson löst die ganzzahlige Teilung in O (M (n)) -Komplexität durch lineare Algebra-Apploximation. Schneller als die sonst O (n * n) Komplexität.
Im Code Die Methode enthält 10mults 9adds 2bitwiseshifts.
Dies erklärt, warum eine Division ungefähr 12x so viele CPU-Ticks aufweist wie eine Multiplikation.
quelle
Die Antwort hängt von der Plattform ab, für die Sie programmieren.
Zum Beispiel sollte eine Multiplikation auf einem Array unter x86 viel schneller sein als eine Division, da der Compiler den Assembler-Code erstellen sollte, der SIMD-Anweisungen verwendet. Da die SIMD-Anweisungen keine Division enthalten, würden Sie durch Multiplikation und Division große Verbesserungen feststellen.
quelle
divps
ist Teil des ursprünglichen SSE1, das in PentiumIII eingeführt wurde. Es gibt keinen Befehl zur SIMD- Ganzzahldivision , aber die SIMD-FP-Division existiert tatsächlich. Die Teilungseinheit hat manchmal einen noch schlechteren Durchsatz / eine schlechtere Latenz für breite Vektoren (insbesondere 256b AVX) als für skalare oder 128b-Vektoren. Sogar Intel Skylake (mit einer deutlich schnelleren FP-Division als Haswell / Broadwell) hatdivps xmm
(4 gepackte Floats): 11c Latenz, eine pro 3c Durchsatz.divps ymm
(8 gepackte Floats): 11c Latenz, eine pro 5c Durchsatz. (oder für gepackte Doppel: eins pro 4c oder eins pro 8c) Perf-Links finden Sie im x86- Tag-Wiki.