Warum dauert die Hardwareteilung viel länger als die Multiplikation?

37

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

Ich habe einige Tutorials durchgearbeitet, darunter Divisionsalgorithmus und Multiplikationsalgorithmus auf Wikipedia. Hier ist meine Argumentation.

Ein Divisionsalgorithmus ist wie eine langsame Divisionsmethode mit Wiederherstellung auf Wikipedia ein rekursiver Algorithmus. Dies bedeutet, dass (Zwischen-) Ergebnisse von 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, wohingegen nes sich um eine Anzahl von Bits in einer Dividende handelt. 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, welche von Mikrocontrollern verwendet werden können. Wie funktioniert die Multiplikation auf einem Hardware- / Mikrocontroller?

Ich habe einen Dadda-Multiplikator- Algorithmus gefunden, dessen Abschluss nur einen Taktzyklus benötigen soll. Was ich hier jedoch nicht verstehe, ist, dass Daddas Algorithmus in drei Schritten abläuft, wohingegen die Ergebnisse aus Schritt 1 in Schritt 2 usw. verwendet werden. Demnach würde dies mindestens drei Taktzyklen dauern, um fertig zu sein.

Marko Gulin
quelle
2
Der Algorithmus definiert die Anzahl der Taktzyklen nicht wirklich. Ihre spezifische CPU verfügt möglicherweise über einen Hardware-Multiplikator / Divisor, der unabhängig von der internen Implementierung in einem oder 20 Zyklen arbeitet.
Eugene Sh.
1
OP, können Sie einen Link bereitstellen, der weitere Informationen zu den 19 vs 1 Zyklen enthält, über die Sie sprechen? Etwas Besonderes an Ihrem DSP.
Vladimir Cravero
1
Danke für die Antworten. Hier ist ein Datenblatt für meinen Mikrocontroller: ww1.microchip.com/downloads/en/DeviceDoc/70005127c.pdf . Siehe Übersicht über Befehlssätze ab Seite 292. Alle DIV-Befehle dauern 18 Zyklen, während alle MUL-Befehle nur 1 Zyklus dauern. Ist aber nicht nur bei dieser MCU üblich, das habe ich bei vielen anderen MCUs gesehen.
Marko Gulin
2
@Curd, na ja, sie sind ungefähr gleich, oder? Sind für mich. Ich glaube nicht, dass das so gut illustriert, wie Sie es sich vorstellen können.
TonyM
1
Der andere Faktor ist Wirtschaftlichkeit und Nutzungsmuster. Die meisten Verwendungen rufen die Multiplikation weitaus häufiger hervor als die Division. Die Verwendung einer großen Siliziumfläche für eine schnellere Funktion zur Aufteilung der Hardware, die relativ selten verwendet wird, ist wirtschaftlich unzureichend. Besser einen kleineren und billigeren Chip bauen oder die zusätzliche Logik produktiver einsetzen. Übrigens, als ich mit Minicomputern anfing, war Teilen nicht immer eine Anweisung. Auf einigen Rechnern handelte es sich um einen Softwarebibliotheksaufruf wie Quadratwurzel.
Nigel222

Antworten:

34

Ein Teiler ordnet einer typischen Hardware viel weniger elegant zu. Nehmen Sie als Beispiel Lattice ICE40 FPGAs.

Vergleichen wir zwei Fälle: diesen 8x8-Bit-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-Ergebnisse 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ß, ist die Uhr nicht tut nichts)

Eine Übersicht über das generierte Schema beim Mappen des Multiplikators auf ein ICE40-FPGA finden Sie hier und den Teiler hier .

Die Synthesestatistiken von Yosys sind:

multiplizieren

  • Anzahl der Adern: 155
  • Anzahl der Drahtbits: 214
  • Anzahl der öffentlichen Kabel: 4
  • Anzahl der öffentlichen Drahtbits: 33
  • Anzahl der Speicherplätze: 0
  • Anzahl der Speicherbits: 0
  • Anzahl der Prozesse: 0
  • Anzahl der Zellen: 191
    • SB_CARRY 10
    • SB_DFF 16
    • SB_LUT4 165

Teilen

  • Anzahl der Adern: 145
  • Anzahl der Drahtbits: 320
  • Anzahl der öffentlichen Kabel: 4
  • Anzahl der öffentlichen Drahtbits: 25
  • Anzahl der Speicherplätze: 0
  • Anzahl der Speicherbits: 0
  • Anzahl der Prozesse: 0
  • Anzahl der Zellen: 219
    • SB_CARRY 85
    • SB_DFF 8
    • SB_LUT4 126

Es ist erwähnenswert, dass die Größe des generierten Verilog für einen Multiplikator mit 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 möglicherweise eine Tiefe von 15 hat, wohingegen der Teiler eher wie 50 oder so aussieht. Der kritische Pfad (dh der längste Pfad, der während des Betriebs auftreten kann) definiert die Geschwindigkeit!


Sie können dies sowieso nicht lesen, um sich einen visuellen Eindruck zu verschaffen. Ich denke, die Unterschiede in der Komplexität sind erkennbar. Dies sind Single-Cycle-Multiplikatoren / Dividierer!

Multiplizieren

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

Skaliertes Bild des Multiplikators

Teilen

( Auf einem ICE40 teilen ) (Warnung: ~ 100 Mpixel Bild)

Skaliertes Bild des Teilers

Marcus Müller
quelle
4
Nein, Sie können sie nicht iterativ implementieren. Aber es wird einfach einige Zeit dauern, bis das gültige Ergebnis durch die Logik "kräuselt". Die obigen Implementierungen sind nicht iterativ.
Marcus Müller
9
Ich möchte ein Wandposter der Trennwand.
Ian Howson
5
Es gibt jetzt ein PDF im Multiplikationsverzeichnis . Es ist 3378 × 3177 mm, also besprechen Sie dies bitte mit Ihrem Lebensgefährten, bevor Sie es an die Decke des Schlafzimmers hängen.
Marcus Müller
2
Ihre 100-Megapixel-Bilder sind beeindruckend, aber für den Punkt, den Sie anstreben, übertrieben, und sie bereiten jedem, der versucht, diese Seite auf einem Gerät mit begrenztem Speicher wie einem Telefon oder Tablet anzuzeigen, große Probleme. Wenn Sie die Bilder inline anzeigen möchten, finden Sie eine Möglichkeit, eine Vorschau mit geringerer Auflösung zu erstellen.
Dave Tweed
4
Yo, diese Grafikkarten sind aus dem Schneider, yo!
Spencer Williams
8

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

Natürlich können Sie im Prinzip einfach eine große Nachschlagetabelle verwenden, um das Produkt oder den Quotienten aus zwei Zahlen zu berechnen und so Ergebnisse in einem einzigen Zyklus zu erhalten. Dies kann jedoch mit zunehmender Anzahl von Bits pro Zahl schnell unpraktisch werden.

Spehro Pefhany
quelle
Unterm Strich können Divisionsalgorithmen im Gegensatz zu Multiplikationsalgorithmen nicht parallelisiert werden, weshalb sie so viel langsamer sind.
Marko Gulin
2
@MarkoGulin "kann nicht" ist eine sehr starke Behauptung. Es ist sicherlich nicht einfach.
Spehro Pefhany
2
Ich denke, Sie könnten es abschwächen von "Divisionsalgorithmen können nicht parallelisiert werden" zu "der Art und Weise, wie wir die Division parallelisieren, belastet die Hardware, die die Division implementiert, stärker als die parallelisierte Multiplikation." Sphero gibt ein Beispiel dafür, wie man mit O (2 ^ n) -Toren eine Ein-Zyklus-Division durchführt, um n-Bit-Zahlen zu multiplizieren ... aber das ist einfach nicht praktisch.
Cort Ammon
1
Eine lange Division kann die Parallelität in jedem gewünschten Ausmaß ausnutzen, indem ein ungefährer Kehrwert berechnet wird, der, multipliziert mit dem Divisor, ein Ergebnis der Form 1000 ... xxxx ergibt. Wenn mit einem Divisor in einer solchen Form mit N führenden Nullen gearbeitet wird, ist es einfach mit jedem Schritt N Bits des Ergebnisses zu berechnen.
Superkatze
8

Wir können mehrere Logikschichten pro Taktzyklus haben, aber es gibt eine Grenze, wie viele Logikschichten wir 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, welche von Mikrocontrollern verwendet werden können

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

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

Schauen wir uns also die Implementierung in Hardware an.

  • Das Schalten ist nur eine Frage der Verkabelung, es ist also kostenlos.
  • Das Maskieren erfordert UND-Gatter. Das bedeutet eine Logikebene, aus zeitlicher Sicht ist es also billig.
  • Das Hinzufügen ist relativ teuer, da eine Transportkette erforderlich ist. Zum Glück gibt es einen Trick, den wir anwenden können. Für die meisten Additionsstufen können wir, anstatt zwei Zahlen zu addieren, drei Zahlen addieren, um zwei zu erzeugen.

Lassen Sie uns also festlegen, wie viele Logikstufen wir für einen 8x8-Multiplikator mit 16-Bit-Ergebnissen benötigen. Der Einfachheit halber nehmen wir an, dass wir nicht versuchen, zu optimieren, dass nicht alle Zwischenergebnisse Bits an allen Positionen aufweisen.

Nehmen wir an, dass ein Volladdierer in zwei "Gate-Stufen" implementiert ist.

  • 1 für die Maskierung, um 8 Zwischenergebnisse zu erzielen.
  • 2 zum Hinzufügen von Dreiergruppen, um die 8 Zwischenergebnisse auf 6 zu reduzieren
  • 2 zum Hinzufügen von Dreiergruppen, um die 6 Zwischenergebnisse auf 4 zu reduzieren
  • 2, um eine Gruppe von drei Zahlen hinzuzufügen und die 4 Zwischenergebnisse auf 3 zu reduzieren
  • 2, um eine Gruppe von drei Zahlen hinzuzufügen und die 3 Zwischenergebnisse auf 2 zu reduzieren
  • 32, um die letzten beiden Ergebnisse zu addieren.

Insgesamt also etwa 46 Logikstufen. Die meisten davon werden ausgegeben, um die letzten beiden Zwischenergebnisse zu addieren.

Dies könnte weiter verbessert werden, indem die Tatsache ausgenutzt wird, dass nicht alle Zwischenergebnisse alle vorhandenen Bits aufweisen (das ist im Grunde das, was der Dada-Multiplikator tut), indem ein Carry-Lookahead-Addierer für den letzten Schritt verwendet wird. Durch Addition von 7 zu 3 anstelle von 3 zu 2 (Reduzierung der Anzahl der Stufen zum Preis von mehr Toren und breiteren Toren) usw.

Das sind alles Kleinigkeiten, der wichtige Punkt ist jedoch, dass die Anzahl der Stufen, die benötigt werden, um zwei n-Bit-Zahlen zu multiplizieren und ein 2n-Bit-Ergebnis zu erzeugen, in etwa 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 gemacht wird, hängt stark von den Ergebnissen der vorherigen Iteration ab.
  2. Die Anzahl der zur Implementierung einer Iteration erforderlichen Logikstufen ist in etwa 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 in etwa proportional zu n im Quadrat.

Peter Green
quelle
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"?
Marko Gulin
1
Es sieht so aus, als ob Papas Algorithmus eine optimierte Version der binären Long-Multiplikation ist.
Peter Green
Ich brenne 8 Zyklen, um eine 1 / x-Division durchzuführen. Ich verwende das dann gegen eine 8-Zyklen-Multiplikation für feste Kosten von 16 Zyklen.
b degnan
Dies zeigt deutlich, dass die Multiplikation nicht viel schlimmer ist als die Addition.
Hagen von Eitzen
1
Eine Iteration erfordert eine Subtraktion, die in O (1gN) -Stufen unter Verwendung von O (NlgN) -Hardware oder O (sqrt (N)) -Stufen unter Verwendung von O (N) -Hardware durchgeführt werden kann. Der wesentliche Punkt ist jedoch, dass die Multiplikation 0 (1gN) Stufen erfordert, während die Division 0 (1gN) Stufen erfordert. Nicht O (N * N), sondern größer als die Multiplikation mit dem Faktor O (N), es sei denn, man geht von einem ungefähren Kehrwert aus, um mehr Arbeit pro Schritt ausführen zu können.
Superkatze
4

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

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

Der Grund dafür ist natürlich, dass viele Transistoren verwendet werden. Beispielsweise können für eine 16-Bit-Teilung fast 16 x mehr Transistoren verwendet werden. Wenn auch mehr Stufen von Gattern vorhanden sind, wird die maximal zulässige Taktfrequenz verringert (da mehr Stufen der Ausbreitungsverzögerung vorhanden sind).

user4574
quelle
4

Praktische Divisionsalgorithmen basieren alle auf numerischen Reihen, die zum Quotienten konvergieren.

  • Es gibt additive Methoden wie Non-Restoring oder SRT, bei denen 2 ^ N zum Quotienten hinzugefügt oder daraus entfernt und der 2 ^ N * -Divisor entsprechend zum Teilrest hinzugefügt oder daraus entfernt wird, bis er gegen Null konvergiert.

  • Es gibt multiplikative Methoden wie Newton-Raphson oder Goldshmidth, bei denen die Division als Umkehrung der Multiplikation berechnet wird.

Additive Methoden ergeben ein oder mehrere Bits pro Zyklus. Multiplikative Verfahren verdoppeln die Anzahl der Bits für jeden Zyklus, erfordern jedoch eine anfängliche Approximation, 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.

TEMLIB
quelle
0

Warum dauert die Hardwareteilung so viel länger als die Multiplikation auf einem Mikrocontroller?

Dies ist keine elektronische Frage. Bestenfalls handelt es sich um eine Computerfrage, die sich besser an Stack Overflow richtet.

Siehe zum Beispiel hier: Ist die Multiplikation schneller als die Gleitkommadivision?

In Wirklichkeit ist es eine Frage des wirklichen Lebens: Warum dauert die Teilung so viel länger als die Multiplikation?

Welchen würden Sie lieber auf Papier berechnen?

51 * 82

oder

4182 / 51

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

Nick Gammon
quelle