Gleitkommadivision gegen Gleitkommamultiplikation

76

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

sum1stolemyname
quelle
3
Der wirkliche Weg, um die Antwort zu finden, besteht darin, beides zu versuchen und die Zeit zu messen.
Scharfzahn
15
Die meisten Compiler optimieren einen wörtlichen konstanten Ausdruck wie diesen, sodass dies keinen Unterschied macht.
Paul R
2
@sharptooth: Ja, mich selbst auszuprobieren würde das Problem für meine Entwicklungsmaschine lösen, aber ich dachte, wenn jemand aus der SO-Menge bereits die Antwort für den allgemeinen Fall hat, würde er gerne teilen;)
sum1stolemyname
7
@Gabe, ich glaube , was Paulus meinte , ist , dass es drehen würde 200f / 2in 100f.
Mikerobi
10
@Paul: Eine solche Optimierung ist für Potenzen von 2 möglich, aber im Allgemeinen nicht. Abgesehen von Zweierpotenzen hat keine Gleitkommazahl einen Kehrwert, mit dem Sie anstelle der Division multiplizieren können.
R .. GitHub STOP HELPING ICE

Antworten:

84

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.

Gabe
quelle
1
Ich denke, das OP möchte wissen, welche algorithmischen / architektonischen Anforderungen dazu führen, dass die Division in der Hardware weitaus komplizierter ist als die Multiplikation.
Chrisaycock
2
Soweit ich mich erinnere, hat sich der Cray-1 nicht um eine Teilungsanweisung gekümmert, er hatte eine wechselseitige Anweisung und erwartete, dass Sie sich danach vermehren. Genau aus diesem Grund.
Mark Ransom
1
Markierung: In der Tat wird der 4-Stufen-Divisionsalgorithmus auf Seite 3-28 der CRAY-1-Hardwarereferenz beschrieben: reziproke Approximation, reziproke Iteration, Zähler * Approximation, Quotient * Korrekturfaktor mit halber Genauigkeit.
Gabe
2
@aaronman: Wenn FP-Nummern als gespeichert würden, wäre das x ^ yMultiplizieren mit x ^ -ygleich der Division. FP-Nummern werden jedoch als gespeichert x * 2^y. Multiplizieren mit x * 2^-yist nur Multiplikation.
Gabe
4
Was ist "Grundschule"?
Pharap
31

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 mit inverseinnerhalb der Schleife. (Wenn der Rundungsfehler in inverseakzeptabel ist)

Normalerweise ist 1.0/xes nicht genau als floatoder darstellbar double. Es wird genau sein , wenn xeine Potenz von 2 ist dieser Compiler optimieren läßt , x / 2.0fum x * 0.5fim 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-optimizationsaktiviert durch -ffast-math) lässt der Compiler ersetzen x / ymit , 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-mathEs 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_activeHardware-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 Themenidiv : 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, dass sum += a[i] / b[i]Engpässe bei der addLatenz oder beim divDurchsatz auftreten, jedoch nicht bei der divLatenz, 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. ( rcppsitsef 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, rcppsbeschleunigt das Teilen mit einer divpsAnweisung durch das Selbst + das zusätzliche Mul + FMA normalerweise schneller , außer bei CPUs mit sehr geringem divpsDurchsatz.

(Zum Beispiel Knight's Landing, siehe unten. KNL unterstützt AVX512ER , sodass floatdas VRCP28PSErgebnis für Vektoren bereits genau genug ist, um nur ohne Newton-Raphson-Iteration zu multiplizieren. Die floatMantissengröß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.0oder ist 0.5(dh die base2- floatDarstellung 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/ das pdist, 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 von ymm.)


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 von floatoder double. Siehe auch die Tag Wiki.

Peter Cordes
quelle
20

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.1können nicht genau als a dargestellt werden double, 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!

Michael Borgwardt
quelle
3
Mit g ++ geben 200.f / 10 und 200.f * 0.1 genau den gleichen Code aus.
Johan Kotlinski
10
@ Kotlinski: Das macht G ++ falsch, nicht meine Aussage. Ich nehme an, man könnte argumentieren, dass man, wenn der Unterschied wichtig ist, überhaupt keine Floats verwenden sollte, aber es ist definitiv etwas, was ich nur auf den höheren Optimierungsstufen tun würde, wenn ich ein Compilerautor wäre.
Michael Borgwardt
3
@ Michael: Nach welchem ​​Standard falsch?
Johan Kotlinski
9
Wenn Sie es auf faire Weise versuchen (was es dem Compiler nicht ermöglicht, zu optimieren oder zu ersetzen), werden Sie feststellen, dass 7/10 und 7 * 0.1 mit doppelter Genauigkeit nicht das gleiche Ergebnis liefern. Die Multiplikation gibt die falsche Antwort, es gibt eine Zahl, die größer als die Division ist. Beim Gleitkomma geht es um Präzision. Wenn auch nur ein Bit ausgeschaltet ist, ist dies falsch. Gleiches gilt für 7/5! = 7 / 0,2, aber nehmen Sie eine Zahl, die Sie für 7/4 und 7 * 0,25 darstellen können, um das gleiche Ergebnis zu erzielen. IEEE unterstützt mehrere Rundungsmodi, sodass Sie einige dieser Probleme lösen können (wenn Sie die Antwort im Voraus kennen).
old_timer
6
In diesem Fall sind Multiplizieren und Dividieren übrigens gleich schnell - sie werden in Kompilierungszeit berechnet.
Johan Kotlinski
10

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.

TED
quelle
4
Es reicht nicht aus, den Code lesbar zu machen. Manchmal gibt es Anforderungen, um etwas zu optimieren, und das würde den Code im Allgemeinen schwer verständlich machen. Ein guter Entwickler würde zuerst gute Komponententests schreiben und dann den Code optimieren. Lesbarkeit ist schön, aber nicht immer erreichbares Ziel.
BЈовић
@VJo - Entweder hast du meinen vorletzten Satz verpasst oder du stimmst meinen Prioritäten nicht zu. Wenn es das letztere ist, sind wir leider dazu verdammt, nicht zuzustimmen.
TED
14
Compiler können dies nicht für Sie optimieren. Sie dürfen nicht, da die Ergebnisse unterschiedlich und nicht konform wären (gemäß IEEE-754). gcc bietet eine -ffast-mathOption für diesen Zweck, aber es bricht viele Dinge und kann im Allgemeinen nicht verwendet werden.
R .. GitHub STOP HELPING ICE
2
Ich nehme an, ein bisschen nekrotisch, aber die Teilung ist normalerweise nicht per Pipeline. So kann es die Leistung wirklich stark beeinträchtigen. Wenn überhaupt, macht Pipelining den Unterschied in der Leistung von Multiplikationen und Divisionen noch größer, weil eines von Pipelining, das andere jedoch nicht.
Harold
11
C - Compiler dürfen diese um 2,0 und Multiplikation , da sowohl die Division durch 0,5 optimieren exakt sind , wenn binäre Arithmetik, so das Ergebnis ist das gleiche. Siehe Abschnitt F.8.2 der Norm ISO C99, in dem genau dieser Fall als zulässige Transformation bei Verwendung von IEEE-754-Bindungen dargestellt ist.
Njuffa
8

Ü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.

Nathan Whitehead
quelle
Neuere Intel-CPUs (seit Broadwell) verwenden einen Radix-1024-Teiler , um die Teilung in weniger Schritten durchzuführen. Im Gegensatz zu so ziemlich allem anderen ist die Teilungseinheit nicht vollständig über eine Pipeline (da, wie Sie sagen, mangelnde Unabhängigkeit / Parallelität eine große Sache bei der Hardware ist). zB Skylake gepackte Division ( 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/optimize
Peter Cordes
2

Newton 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.

ollj
quelle
1

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.

BЈовић
quelle
Aber auch andere Antworten sind gut. Eine Division ist im Allgemeinen langsamer oder gleich der Multiplikation, hängt jedoch von der Plattform ab.
BЈовић
1
Mittlerweile gibt es Divisionsanweisungen für SSE
Andre Holzner
divpsist 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) hat divps 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.
Peter Cordes