Warum ist die Division so viel komplexer als andere arithmetische Operationen?

39

Ich bin kürzlich auf einen Fall gestoßen, in dem ich eine Ganzzahl-Divisionsoperation auf einem Chip benötigte, dem eine fehlte (ARM Cortex-A8). Während ich zu untersuchen versuchte, warum das so sein muss, fand ich heraus, dass Division im Allgemeinen viel mehr Zyklen benötigt als Addition, Subtraktion oder Multiplikation auf so ziemlich jeder Integer- (oder Fixpunkt-) Architektur. Warum ist das so? Ist es nicht wie alles andere mit einer zweischichtigen UND-ODER-Logik darstellbar?

Phonon
quelle

Antworten:

34

Division ist ein iterativer Algorithmus, bei dem das Ergebnis des Quotienten mit einem euklidischen Maß zum Rest verschoben werden muss, siehe 2 ; wohingegen die Multiplikation auf eine (feste) Reihe von Bitmanipulationstricks reduziert werden kann.

aterrel
quelle
2
Früher waren sowohl Multiplikation als auch Division langsame Operationen. Heutzutage ist die Multiplikation etwas schneller (aber etwas langsamer als die Addition / Subtraktion), aber die Division ist immer noch langsamer als die anderen. Ich glaube, Newton-Raphson wird von den meisten intern immer noch für das Hin- und Herbewegen einer Zahl verwendet.
JM
12
(Off-Topic: "Inverse Operationen sind normalerweise schwierig. Sehen Sie sich nur Integration und Differenzierung an." - Kommt darauf an, ob Sie symbolisch oder numerisch differenzieren. Die Differenzierung ist symbolisch einfach, aber numerisch schwierig. Die Integration ist symbolisch schwierig, aber numerisch schwierig easy.)
JM
1
Okay, ich werde damit fertig werden, indem ich sage, dass Kubatur eine andere Dose Würmer ist. Aber zumindest im eindimensionalen Fall ist Quadratur einfacher als Differenzierung.
JM
1
In jedem Fall kommen Inverse immer paarweise vor. Warum würden Sie eine "Operation" und die andere "Inverse" nennen?
David Ketcheson
2
Weder die Iteration noch die Inverse erschweren es. Die Divisionshärte ergibt sich aus der Tatsache, dass Sie das Ergebnis mit einem euklidischen Maß vom Quotienten zum Rest verschieben müssen. Siehe den Teilungsalgorithmus-Satz .
20

Während alle aktuellen CPUs einen iterativen Ansatz zu verwenden scheinen, wie es der Aterrel nahelegt , wurden einige Arbeiten an nicht-iterativen Ansätzen durchgeführt. Gleitkommadivision und Quadratwurzel mit variabler Präzision sprechen von einer nicht-iterativen Implementierung von Gleitkommadivision und Quadratwurzel in einem FPGA unter Verwendung von Nachschlagetabellen und Taylor-Reihenerweiterung.

Ich vermute, dass die gleichen Techniken es möglich machen, diese Vorgänge auf einen einzigen Zyklus (Durchsatz, wenn nicht Latenz) zu beschränken, aber Sie werden wahrscheinlich riesige Nachschlagetabellen und damit unüberschaubar große Bereiche von Siliziumimmobilien benötigen, um dies zu tun .

Warum sollte es nicht machbar sein?

Beim Entwerfen von CPUs müssen viele Kompromisse eingegangen werden. Funktionalität, Komplexität (Anzahl der Transistoren), Geschwindigkeit und Stromverbrauch hängen zusammen, und die Entscheidungen, die während des Designs getroffen werden, können einen enormen Einfluss auf die Leistung haben.

Ein moderner Prozessor könnte wahrscheinlich eine Hauptgleitkommaeinheit haben, die genügend Transistoren auf dem Silizium reserviert, um eine Gleitkommadivision in einem einzigen Zyklus durchzuführen , aber es ist unwahrscheinlich, dass diese Transistoren effizient eingesetzt werden.

Die Gleitkommamultiplikation hat diesen Übergang von iterativ zu nicht iterativ vor einem Jahrzehnt vollzogen. Heutzutage sind Single Cycle Multiplizieren und sogar Multiplizieren-Akkumulieren selbst in mobilen Prozessoren an der Tagesordnung.

Bevor es zu einer effizienten Verwendung des Transistorbudgets kam, wurde die Multiplikation wie auch die Division häufig durch eine iterative Methode durchgeführt. Damals widmeten dedizierte DSP-Prozessoren möglicherweise den größten Teil ihres Siliziums einer einzelnen MAC- Einheit ( Fast Multiple Accumulate) . Eine Core2duo-CPU hat eine Gleitkomma- Multiplikator-Latenz von 3 (der Wert kommt aus dem Pipeline-3-Zyklus, nachdem er eingegangen ist ), kann jedoch 3 Multiplikatoren gleichzeitig im Flug haben, was zu einem Durchsatz von einem Zyklus führt, während dies bei der SSE2-Einheit der Fall ist Pumpen Sie mehrere FP-Multiplikationen in einem einzigen Zyklus aus.

Anstatt große Bereiche des Siliziums einer Einzelzyklus-Teilungseinheit zuzuweisen, verfügen moderne CPUs über mehrere Einheiten, von denen jede Operationen parallel ausführen kann, die jedoch für ihre eigenen spezifischen Situationen optimiert sind. Wenn Sie SIMD- Anweisungen wie SSE oder die in der CPU integrierten Grafiken der Sandy Bridge oder späterer CPUs berücksichtigen , befinden sich möglicherweise viele solcher Gleitkommadivisionseinheiten in Ihrer CPU.

Wenn eine generische Gleitkommadivision für moderne CPUs wichtiger wäre, wäre es möglicherweise sinnvoll, genügend Siliziumfläche für einen einzelnen Zyklus zu reservieren. Die meisten Chiphersteller haben jedoch offensichtlich beschlossen, dieses Silizium besser zu nutzen, indem sie diese Gates für andere Zwecke verwenden . Somit ist eine Operation langsamer, aber insgesamt (für typische Verwendungsszenarien) ist die CPU schneller und / oder verbraucht weniger Energie.

Mark Booth
quelle
Meines Wissens haben keine Chips eine Single-Cycle-Divisionslatenz für Gleitkommazahlen. In den Anweisungstabellen von Agner Fog für Intel-, AMD- und VIA-CPUs sind beispielsweise DIVPS (SSE-gepackte Gleitkommadivision) als 10-14 Zyklen aufgeführt. Ich kann keine Hardware mit Einzelzyklus-Divisionsanweisungen finden, aber ich wäre bereit, mich zu irren. Soweit ich das beurteilen kann, ist es nicht üblich.
Bill Barth
@ Bill - Danke, du hast recht. Ich bin mir sicher, dass ich schon einmal Divisionsoperationen in DSP-Chips mit einem Zyklus gesehen habe. Ich bin also davon ausgegangen, dass dies den Weg zum Desktop gefunden hätte, genau wie bei der Multiplikation mit einem Zyklus, aber ich kann jetzt keine Referenzen finden. Ich habe meine Antwort aktualisiert und einige relevante Informationen zu nicht-iterativen Methoden hinzugefügt, die dies jedoch in Zukunft ermöglichen könnten. Es ist erstaunlich zu denken, dass die Aufteilung pro Zyklus jetzt nicht effizienter ist als damals, als ich Transputer verwendete.
Mark Booth
1
Ich denke, DSPs tun dies, indem sie den Bereich einschränken, in dem sie genau sind. Dies ist die gleiche Strategie, die für die Suche + Interpolation für die Quadratwurzel verwendet wird.
Matt Knepley
1
Ich bin nicht sicher , was die Latenz einer solchen Teilung wäre, wenn. Bei 4 GHz schränkt ein Hin- und Rücklauf zur Nachschlagetabelle innerhalb von N Zyklen die potenzielle Größe der Tabelle stark ein (zum Beispiel stagnierten die L1-Caches bei jeweils 32 KB). Der Einsatz von 3D würde dazu beitragen, diesen Wert zu erhöhen (dies ist jedoch eine Herausforderung für die Kühlung). Haben Sie eine Idee, welche Latenz für moderne 4GHz / 5GHz-CPUs erreicht werden könnte?
Matthieu M.
1
Informationen zu Divps / Divpd vs. Mulps / Mulpd-Latenz und Durchsatzzahlen finden Sie unter Gleitkommadivision vs. Gleitkommamultiplikation . Ich nahm Daten aus den Anweisungstabellen von Agner Fog und formatierte sie zu einer Zusammenfassung über Bereiche von Div- und Mul-Durchsatz und -Latenz, für Einfach-Doppel- und für verschiedene SIMD-Vektorbreiten. (Intel-Chips haben normalerweise einen SIMD-Teiler, der nur halb so breit ist wie die anderen Vektor-ALUs.)
Peter Cordes,