Warum dauert die Hardware-Division viel länger als die Multiplikation?

Warum dauert die Hardware-Division so viel länger als die Multiplikation auf einem Mikrocontroller? Beispielsweise dauert eine Division auf einem dsPIC 19 Zyklen, während eine Multiplikation nur einen Taktzyklus benötigt.

Ich habe einige Tutorials durchgearbeitet, darunter den Divisionsalgorithmus und den Multiplikationsalgorithmus auf Wikipedia. Hier ist meine Begründung.

Ein Divisionsalgorithmus ist wie eine langsame Divisionsmethode mit Wiederherstellung auf Wikipedia ein rekursiver Algorithmus. Dies bedeutet, dass (Zwischen-)Ergebnisse aus Schritt kals Eingaben für Schritt verwendet werden k+1, was bedeutet, dass diese Algorithmen nicht parallelisiert werden können. Daher dauert es mindestens nZyklen, um die Division abzuschließen, während nein Dividend eine Anzahl von Bits ist. Für 16-Bit-Dividenden entspricht dies mindestens 16 Zyklen.

Ein Multiplikationsalgorithmus muss nicht rekursiv sein, was bedeutet, dass es möglich ist, ihn zu parallelisieren. Es gibt jedoch viele verschiedene Multiplikationsalgorithmen, und ich habe keine Ahnung, welcher von Mikrocontrollern verwendet werden kann. Wie funktioniert die Multiplikation auf einer Hardware/einem Mikrocontroller?

Ich habe einen Dadda-Multiplikator -Algorithmus gefunden, der nur einen Taktzyklus dauern soll, um fertig zu werden. Was ich hier jedoch nicht verstehe ist, dass Daddas Algorithmus in drei Schritten vorgeht, während Ergebnisse aus Schritt 1 in Schritt 2 verwendet werden usw. Demnach würde dies mindestens drei Taktzyklen dauern, bis dies abgeschlossen ist.

Der Algorithmus definiert nicht wirklich die Anzahl der Taktzyklen. Ihre spezifische CPU verfügt möglicherweise über einen Hardware-Multiplikator/Teiler, der unabhängig von der internen Implementierung in einem Zyklus oder 20 Zyklen arbeitet.
OP, können Sie einen Link bereitstellen, der weitere Informationen zu den 19-gegen-1-Zyklen enthält, über die Sie sprechen? Etwas Bestimmtes über Ihren DSP.
Danke für Antworten. Hier ist ein Datenblatt für meinen Mikrocontroller: ww1.microchip.com/downloads/en/DeviceDoc/70005127c.pdf . Siehe Überblick über den Befehlssatz ab Seite 292. Es besagt, dass alle DIV-Befehle 18 Zyklen benötigen, während alle MUL-Befehle nur 1 Zyklus benötigen. Aber das ist nicht nur bei dieser MCU üblich, ich habe das bei vielen anderen MCUs gesehen.
Was dauert länger, wenn Sie mit Papier und Bleistift multiplizieren und dividieren? Wieso den?
@Curd, nun, sie sind ungefähr gleich, nicht wahr? Sind für mich. Ich glaube nicht, dass das so gut illustriert ist, wie Sie sich das vielleicht vorstellen.
@TonyM der Papier-und-Stift-Divisionsalgo, den ich in meinem Kopf habe, wendet in jedem Schritt eine Reihe von Multiplikationen von Teiler-Ziffern-Zeiten × 1-Ziffer und eine Modulo-Operation und eine Subtraktion an, also mit genau diesem Ansatz Division in meinem Kopf, würde ich argumentieren, dass Division mehr Aufwand erfordert als Multiplikation. Ihr Punkt ist immer noch gültig, denn anstatt erschöpfend auszuprobieren, wie oft der Divisor in den Rest passt, gibt es gute Heuristiken
Der andere Faktor sind Wirtschaftlichkeit und Nutzungsmuster. Die meisten Verwendungen rufen viel häufiger multiplizieren als dividieren auf. Eine große Siliziumfläche einer schnelleren Hardware-Teilungsfunktion zuzuweisen, die relativ selten verwendet wird, ist wirtschaftlich nicht tragbar. Es ist besser, einen kleineren und billigeren Chip herzustellen oder die zusätzliche Logik produktiver zu nutzen. Übrigens, als ich mit Minicomputern anfing, war divide nicht immer eine Anweisung. Auf einigen Maschinen war es ein Softwarebibliotheksaufruf, wie Quadratwurzel.
@nigel222 Danke, ich füge das meiner kurzen Zusammenfassung hinzu.
Gibt es oder gab es Maschinen, die das Teilen durch Zehn in der Hardware optimiert haben?
@nigel222 puuh; Ich könnte mir vorstellen, dass einige Taschenrechner-MCUs eine BCD-Umwandlungseinheit / -Anweisung haben, und das würde die Implementierung in Software trivial machen (ignorieren Sie einfach die niedrigste Ziffer).
@MarkoGulin fügt möglicherweise hinzu, dass Sie beim häufigen Ausführen von Divisionen wahrscheinlich Gleitkommazahlen wünschen, die heutzutage auf vielen CPUs verfügbar sind, und deren Division eine andere Art von Problem darstellt (es enthält mindestens eine Festkommadivision). , aber das hat einen begrenzten Eingangsbereich)
In der Vergangenheit haben sogar Mainframes BCD-String-Anweisungen implementiert. In der Finanzprogrammierung wurden die Kosten für die Umwandlung von Binär in Dezimal als zu hoch angesehen. Heutzutage ist fast alles, was sich in der CPU eines Allzweckcomputers registrieren lässt, „kostenlos“, und es ist der Zugriff auf den Arbeitsspeicher, der die Dinge verlangsamt. Zwischen damals und heute optimierte Division durch zehn für Umwandlungen von ganzen Zahlen in Dezimalzahlen? Ich habe mich nur gewundert - noch nie davon gehört.
Bemerkenswert bei der Gleitkommadivision. Der Cray-1 hatte keine, nur eine reziproke Annäherungsanweisung, die dann eine Multiplikation und zwei weitere Anweisungen verwendete, um eine Division mit voller Genauigkeit zu erreichen. Intel-Gleitkommaeinheiten haben auch eine Anweisung zur reziproken Approximation. Ich weiß nicht, wofür es verwendet wird. Außerdem wird x = y / const zur Multiplikation mit dem Kehrwert von const kompiliert. fdiv wird nur zum Teilen durch eine Variable benötigt.
@TonyM: Ich bezweifle, dass beide etwa gleich lange dauern. Natürlich müssen Sie sich die Berechnung mit mehr als nur 1- oder 2-stelligen Zahlen ansehen. Probieren Sie es einfach aus: Multiplizieren Sie zwei zufällige 6-stellige Zahlen, um ein 12-stelliges Ergebnis zu erhalten, und dividieren Sie eine zufällige 12-stellige Zahl durch eine zufällige 6-stellige Zahl, um ein 6-stelliges Ergebnis zu erhalten, und sehen Sie, wie lange es dauert.

Antworten (6)

Ein Teiler bildet viel weniger elegant auf typische Hardware ab. Nehmen Sie Lattice ICE40 FPGAs als Beispiel.

Vergleichen wir zwei Fälle: diesen 8x8-Bit-zu-16-Bit-Multiplikator:

module multiply (clk, a, b, result);
   input clk;
   input [7:0]a;
   input [7:0]b;
   output [15:0]result;
   always @(posedge clk)
     result = a * b;
endmodule // multiply

und dieser Teiler, der 8- und 8-Bit-Operanden auf 8-Bit-Ergebnis reduziert:

module divide(clk, a, b, result);
   input clk;
   input [7:0] a;
   input [7:0] b;
   output [7:0] result;
   always @(posedge clk)
     result = a / b;
endmodule // divide

(Ja, ich weiß, die Uhr macht nichts )

Eine Übersicht über den generierten Schaltplan bei der Abbildung des Multiplikators auf ein ICE40-FPGA finden Sie hier und den Teiler hier .

Die Synthesestatistiken von Yosys sind:

multiplizieren

  • Anzahl der Drähte: 155
  • Anzahl der Drahtbits: 214
  • Anzahl der öffentlichen Leitungen: 4
  • Anzahl der öffentlichen Kabelbits: 33
  • Anzahl der Speicher: 0
  • Anzahl der Merkerbits: 0
  • Anzahl der Prozesse: 0
  • Anzahl der Zellen: 191
    • SB_TRANSPORT 10
    • SB_DFF16
    • SB_LUT4 165

teilen

  • Anzahl der Drähte: 145
  • Anzahl der Drahtbits: 320
  • Anzahl der öffentlichen Leitungen: 4
  • Anzahl öffentlicher Kabelbits: 25
  • Anzahl der Speicher: 0
  • Anzahl der Merkerbits: 0
  • Anzahl der Prozesse: 0
  • Anzahl der Zellen: 219
    • SB_TRANSPORT 85
    • SB_DFF8
    • SB_LUT4 126

Es ist erwähnenswert, dass die Größe des generierten Verilogs für einen Multiplikator voller Breite und einen Teiler mit maximaler Teilung nicht so extrem ist. Wenn Sie sich jedoch die Bilder unten ansehen, werden Sie feststellen, dass der Multiplikator vielleicht eine Tiefe von 15 hat, während der Teiler eher wie 50 oder so aussieht; der kritische Weg (dh der längste Weg, der im Betrieb auftreten kann) bestimmt die Geschwindigkeit!

Sie werden dies sowieso nicht lesen können, um sich einen visuellen Eindruck zu verschaffen. Ich denke, die Unterschiede in der Komplexität sind möglich zu erkennen. Dies sind Einzelzyklus-Multiplikatoren/Teiler!

Multiplizieren

Multiplizieren auf einem ICE40 (Warnung: ~100 Mpixel Bild)

Skaliertes Bild des Multiplikators

Teilen

( Teilen auf einem ICE40 ) (Warnung: ~100 Mpixel Bild)

Skaliertes Bild des Teilers

Lieber Marcus, vielen Dank für diese Antwort! Jetzt werde ich versuchen, Ihre Antwort zu vereinfachen, und bitte korrigieren Sie mich, wenn ich falsch liege: Sowohl Divisions- als auch Multiplikationsoperationen erfordern mehrere Iterationen, die in einem "einzelnen Taktzyklus" durchgeführt werden können. Jedoch ist eine erforderliche Anzahl dedizierter Gatter für eine Einzelzyklus-Teilungsoperation viel höher als für eine Einzelzyklus-Multiplikationsoperation. Es ist ein Kompromiss zwischen Hardwarekomplexität und Geschwindigkeit. Habe ich das richtig verstanden?
Nein, Sie können sie nicht iterativ implementieren. Aber es wird einfach eine ganze Weile dauern, bis das gültige Ergebnis durch die Logik "rieselt". Die obigen Implementierungen sind nicht iterativ.
Können Sie die Grafikspezifikationen für diese Bilder teilen? Ich möchte sie mit meinem eigenen Rendering-Algorithmus ausführen.
Ich möchte ein Wandposter der Trennwand.
@MarcusMüller Hmm, wie ich aus deinem Beitrag ersehen kann, sind die beiden Algorithmen (Dividieren/Multiplizieren) in Bezug auf die erforderliche Anzahl von Gattern nahezu gleich. Der Teilungsalgorithmus ist jedoch viel "tiefer" (15 gegenüber 50 in Ihrem Beitrag), was zu einer viel längeren Ausbreitungsverzögerung führt. Bitte sehen Sie sich das in Ihrem Beitrag an: "Sie werden feststellen, dass der Multiplikator vielleicht eine Tiefe von 15 hat, während der Multiplikator eher wie 50 oder so aussieht". Ich denke, was Sie meinten, ist "der Teiler sieht eher aus wie 50 oder so".
@QED Ich würde Sie auf Yosys verweisen, um sich auf das obige Verilog zu bewerben: Alles, was ich getan habe, war yosys, read_verilog multiply.v, synth_ice40, show -format svg -prefix multiply_ice40. Aber warten Sie, ich werde das mit wiederholen, show -viewer /bin/true -prefix multiply_ice40um die .dot-Dateien zu erhalten :)
@QED siehe meine beiden Github-Gist-Links oben, 1 und divide
Es gibt jetzt ein PDF im Multiply Gist. Es ist 3378 × 3177 mm groß, also besprechen Sie es bitte mit Ihrem Lebensgefährten, bevor Sie es an der Schlafzimmerdecke anbringen.
@MarcusMüller Können Sie bitte meine kurze Zusammenfassung aller Antworten überprüfen.
Ihre 100-Megapixel-Bilder sind beeindruckend, aber für den Punkt, den Sie zu machen versuchen, viel zu viel des Guten, und sie verursachen große Probleme für jeden, der versucht, diese Seite auf einem Gerät mit begrenztem Speicher wie einem Telefon oder Tablet anzuzeigen. Wenn Sie die Bilder inline anzeigen möchten, finden Sie bitte eine Möglichkeit, eine Vorschau mit niedrigerer Auflösung zu erstellen.
Yo, diese Graphviz-Diagramme sind aus dem Schneider, yo!
@SpencerWilliams yo, so läuft meine Free- und Open-Source-FPGA-Synthese, Mann! Yosys erledigt das alles für mich; und sehr viel mehr!

Wir können mehrere Logikschichten pro Taktzyklus haben, aber es gibt eine Grenze, wie viele Logikschichten wir genau haben können und wie komplex diese Schichten sein können, hängt von unserer Taktgeschwindigkeit und unserem Halbleiterprozess ab.

Es gibt jedoch viele verschiedene Multiplikationsalgorithmen, und ich habe keine Ahnung, welcher von Mikrocontrollern verwendet werden kann

Die meisten Multiplikationen in Computern verwenden eine Variante der binären langen Multiplikation. Binäre lange Multiplikation beinhaltet

  • Verschieben eines Operanden um verschiedene Beträge
  • Maskieren der verschobenen Zahlen basierend auf dem zweiten Operanden
  • Addieren der Ergebnisse der Maskierung.

Werfen wir also einen Blick auf die Implementierung in Hardware.

  • Beim Schalten geht es nur darum, wie wir die Dinge verkabeln, also ist es kostenlos.
  • Das Maskieren erfordert UND-Gatter. Das bedeutet eine Ebene der Logik, also ist es aus zeitlicher Sicht billig.
  • Das Hinzufügen ist aufgrund der Notwendigkeit einer Tragekette relativ teuer. Glücklicherweise gibt es einen Trick, den wir anwenden können. Für die meisten Additionsstufen können wir, anstatt zwei Zahlen zu addieren, um eine zu erzeugen, drei Zahlen addieren, um zwei zu erzeugen.

Lassen Sie uns also festhalten, wie viele Logikstufen wir für einen 8x8-Multiplikator mit 16-Bit-Ergebnissen benötigen. Nehmen wir der Einfachheit halber an, wir versuchen nicht, die Tatsache zu optimieren, dass nicht alle Zwischenergebnisse Bits an allen Positionen haben.

Nehmen wir an, dass ein Volladdierer in zwei "Gatterstufen" implementiert ist.

  • 1 zum Maskieren, um 8 Zwischenergebnisse zu erzeugen.
  • 2, um Gruppen von drei Zahlen hinzuzufügen, um die 8 Zwischenergebnisse auf 6 zu reduzieren
  • 2, um Gruppen von drei Zahlen hinzuzufügen, um die 6 Zwischenergebnisse auf 4 zu reduzieren
  • 2, um eine Gruppe von drei Zahlen hinzuzufügen, um die 4 Zwischenergebnisse auf 3 zu reduzieren
  • 2, um eine Gruppe von drei Zahlen hinzuzufügen, um die 3 Zwischenergebnisse auf 2 zu reduzieren
  • 32, um die letzten beiden Ergebnisse zu addieren.

Insgesamt also etwa 41 Logikstufen. Die meisten davon werden für die Addition der letzten beiden Zwischenergebnisse aufgewendet.

Dies könnte weiter verbessert werden, indem die Tatsache ausgenutzt wird, dass nicht bei allen Zwischenergebnissen alle Bits vorhanden sind (das ist im Grunde das, was der Dada-Multiplikator tut), indem für den letzten Schritt ein Carry-Lookahead-Addierer verwendet wird. Durch Hinzufügen von 7 Zahlen, um 3 statt drei zu erzeugen, um zwei zu erzeugen (Reduzierung der Anzahl der Stufen zum Preis von mehr Toren und breiteren Toren) usw.

Das sind jedoch alles Kleinigkeiten, der wichtige Punkt ist, dass die Anzahl der Stufen, die benötigt werden, um zwei n-Bit-Zahlen zu multiplizieren und ein 2n-Bit-Ergebnis zu erzeugen, ungefähr proportional zu n ist.

Wenn wir uns andererseits Divisionsalgorithmen ansehen, stellen wir fest, dass sie alle einen iterativen Prozess haben, bei dem.

  1. Was bei einer Iteration getan wird, hängt stark von den Ergebnissen der vorherigen Iteration ab.
  2. Die Anzahl der zur Implementierung einer Iteration erforderlichen Logikstufen ist ungefähr proportional zu n (Subtraktion und Vergleich sind in ihrer Komplexität der Addition sehr ähnlich).
  3. die Anzahl der Iterationen ist auch ungefähr proportional zu n.

Die Anzahl der zur Implementierung der Division erforderlichen Logikstufen ist also ungefähr proportional zu n zum Quadrat.

Vielen Dank für Ihre Antwort. Ich habe im Wiki gelesen, dass Daddas Algorithmus sehr effizient ist, wenn es um die erforderliche Anzahl von Gattern geht, um diesen Algorithmus auf Hardware zu implementieren. Trotzdem verwendet die meiste Hardware "binäre lange Multiplikation"?
Es sieht so aus, als wäre der Algorithmus von Dada eine optimierte Version der binären Long-Multiplikation.
Ich brenne 8 Zyklen, um eine 1/x-Division durchzuführen. Ich verwende dies dann gegen eine 8-Zyklen-Multiplikation für feste Kosten von 16 Zyklen.
Das zeigt schön, dass die Multiplikation doch nicht so viel schlimmer ist als die Addition.
Eine Iteration erfordert eine Subtraktion, die in O(lgN)-Stufen unter Verwendung von O(NlgN)-Hardware oder in O(sqrt(N))-Stufen unter Verwendung von O(N)-Hardware durchgeführt werden kann. Der wesentliche Punkt ist jedoch, dass die Multiplikation O(lgN) Stufen erfordert, während die Division O(NlgN) Stufen erfordert. Nicht O(N*N), sondern größer als die Multiplikation mit einem Faktor O(N), es sei denn, man beginnt mit einem ungefähren Kehrwert, um mehr Arbeit pro Schritt zu ermöglichen.
Warum erfordert das Addieren der letzten beiden Ergebnisse 32 Schritte? Würde ein Carry-Lookahead-Addierer hier nicht helfen?

Die langsame Teilung ist von Natur aus iterativ, sodass sie tendenziell länger dauert. Es gibt etwas schnellere langsame Divisionsalgorithmen als die einfachen, die Nachschlagetabellen verwenden. Der SRT-Algorithmus erzeugt zwei Bits pro Zyklus. Ein Fehler in einer solchen Tabelle war die Ursache für den berüchtigten Pentium-FDIV-Bug (ca. 1994). Dann gibt es sogenannte schnelle Divisionsalgorithmen.

Natürlich könnte man im Prinzip einfach eine riesige Nachschlagetabelle verwenden, um das Produkt oder den Quotienten zweier Zahlen zu berechnen und so Ergebnisse in einem einzigen Zyklus zu erhalten, aber das wird mit zunehmender Anzahl von Bits pro Zahl schnell unpraktisch.

Aber unterm Strich lassen sich Divisionsalgorithmen im Gegensatz zu Multiplikationsalgorithmen nicht parallelisieren und sind deshalb so viel langsamer?
@MarkoGulin "kann nicht" ist eine sehr starke Behauptung. Es ist sicherlich nicht einfach.
Ich denke, Sie könnten es schwächen von "Divisionsalgorithmen können nicht parallelisiert werden" zu "Die Wege, die wir gefunden haben, um die Division zu parallelisieren, belasten die Hardware, die die Division implementiert, stärker als die parallelisierte Multiplikation". Sphero gibt ein Beispiel dafür, wie man eine Einzelzyklusdivision mit O(2^n)-Gattern durchführt, um n-Bit-Zahlen zu multiplizieren ... aber das ist einfach nicht praktikabel.
Die lange Division kann die Parallelität beliebig ausnutzen, indem ein ungefährer Kehrwert berechnet wird, der, wenn er mit dem Divisor multipliziert wird, ein Ergebnis der Form 1000 ... xxxx ergibt. Wenn man mit einem Divisor in einer solchen Form mit N führenden Nullen arbeitet, ist es einfach mit jedem Schritt N Bits des Ergebnisses zu berechnen.

Praktische Divisionsalgorithmen basieren alle auf Zahlenfolgen, die gegen den Quotienten konvergieren.

  • Es gibt additive Methoden, wie Non-Restoring oder SRT, die funktionieren, indem 2^N zum Quotienten addiert oder entfernt wird und entsprechend der 2^N * Divisor zum Teilrest addiert oder entfernt wird, bis er gegen Null konvergiert ist.

  • Es gibt multiplikative Methoden wie Newton-Raphson oder Goldshmidth, bei denen es sich um Methoden zur Wurzelfindung handelt, bei denen die Division als Umkehrung der Multiplikation berechnet wird.

Additive Verfahren ergeben ein oder wenige Bits pro Zyklus. Multiplikative Verfahren verdoppeln die Anzahl der Bits für jeden Zyklus, erfordern jedoch eine anfängliche Annäherung, die häufig mit einer konstanten Tabelle erhalten wird.

Die Bezeichnungen "langsam" und "schnell" sind irreführend, da die tatsächliche Geschwindigkeit von der Anzahl der Bits abhängt, wie viel Hardware für die Funktion verwendet wird (und ein schneller Multiplikator sehr groß ist) ...

Die Division ist langsamer als die Multiplikation, da es keine direkte, parallele Methode zu ihrer Berechnung gibt: Entweder gibt es eine Iteration, oder es wird Hardware kopiert, um die Iteration als kaskadierte (oder Pipeline-) Blöcke zu implementieren.

Ein Divisionsalgorithmus (tatsächlich jeder Algorithmus) kann in einem Taktzyklus durchgeführt werden. Wenn Sie bereit sind, für die zusätzlichen Transistoren und die niedrigere zulässige Taktrate zu zahlen.

Angenommen, Sie haben eine Reihe von Gattern, die einen Taktzyklus eines vorhandenen Mehrzyklus-Divisionsalgorithmus implementieren. Um den Algorithmus zu einem Einzelzyklus zu machen, verwenden Sie mehrere Hardwarestufen (ähnlich derjenigen, die in einer Stufe des Mehrzyklusalgorithmus verwendet wird), wobei die Ausgabe einer Stufe die nächste Stufe speist.

Der Grund, es nicht so zu machen, ist natürlich, dass es viele Transistoren verwendet. Beispielsweise kann es für eine 16-Bit-Division fast 16 x mehr Transistoren verwenden. Außerdem senkt das Vorhandensein von mehr Gatterstufen die maximal zulässige Taktfrequenz (weil es mehr Stufen der Ausbreitungsverzögerung gibt).

Anders ausgedrückt: Sie könnten den Rest der CPU verlangsamen, sodass alles andere so langsam wie die Division wäre, aber das wäre verrückt, wenn Sie es viele Zyklen dauern lassen würden, während alles andere schnell wäre.

Warum dauert die Hardware-Division so viel länger als die Multiplikation auf einem Mikrocontroller?

Das ist keine Elektronikfrage. Bestenfalls ist es eine Computerfrage, besser an Stack Overflow gerichtet.

Siehe zum Beispiel hier: Ist die Multiplikation schneller als die Float-Division?

In Wirklichkeit ist es eine Frage aus dem wirklichen Leben: Warum dauert die Division so viel länger als die Multiplikation?

Was würden Sie lieber auf Papier berechnen?

51 * 82

oder

4182 / 51

Division dauert länger als Multiplikation , weil es schwieriger ist .

Warum dauert die Hardware-Division viel länger als die Multiplikation?
AntwortenHierDatenschutz-Bestimmungen1y, 0v