Hallo, habe keine Erklärung dafür, wie ein Prozessor, der mit 80 MHz läuft, in 2 Zyklen über einen Hardware Multiplikator eine 32x32 Bit Multiplikation durchführen kann (Datenblatte PIC 32....) Eine Look up Tabelle für die Ergebnisse müsste ja eine Kapazität von 4 Miliarden x 4 Miliarden x 32 Bit Einträge haben. Wie kann er so schnell rechnen ? LG Dirk
Vollkommener Quatsch - Hyperspace ist das Stichwort!
Ganz einfach: In dem sich beim Multiplizieren sehr beeilt. OK. Scherz beiseite. Die Frage kann man so umformulieren, dass sie für die Allgemeinheit interessanter wird: Wie sieht die Struktur eines binären parallelen Multiplizierers aus? Auf solche Fragen hält das Internet sehr viele Antworten bereit. Es gibt da so "Suchmaschinen". Man gibt Worte ein und erhält eine Liste von Links die auf Seiten verweisen, in denen die eingegebenen Worte vorkommen.
dirkf schrieb: > Hallo, > habe keine Erklärung dafür, wie ein Prozessor, der mit 80 MHz läuft, in > 2 Zyklen über einen Hardware Multiplikator eine 32x32 Bit Multiplikation > durchführen kann (Datenblatte PIC 32....) > > Eine Look up Tabelle für die Ergebnisse müsste ja eine Kapazität von 4 > Miliarden x 4 Miliarden x 32 Bit Einträge haben. > > Wie kann er so schnell rechnen ? Z.B. mit einer 16x16 Bit Lookuptable und 3 Additionen: (a1, a2) * (b1, b2) = (a1*b1)<<32 + (a1*b2)<<16 + (a2*b1)<<16 + (a2*b2)
dirkf schrieb: > Wie kann er so schnell rechnen ? Erster Ansatz wäre das gleiche Verfahren wie bei der schriftlichen Multiplikation. Nur eben parallel statt sequentiell. Ergibt 32 Addierer. Verfeinere das über Carry-Save Adder statt normaler Addierer und der Aufwand schrumpft weiter. Nur so als Anregung, da geht aber noch mehr.
dirkf schrieb: > Wie kann er so schnell rechnen ? Das tut er eigentlich garnicht (rechnen). Er schreibt nur Bitmuster auf die Eingänge einer nicht getakteten Logikschaltung, wartet deren Gatterlaufzeiten ab und holt dann das Ergebnis von deren Ausgängen ab. Nix Lookuptabelle, reine bool'sche Logik. Eine größere Ansammlung von Volladdern. Aber längst nicht so groß wie eine Lookup-Tabelle...
c-hater schrieb: > Eine größere Ansammlung von Volladdern. Nö. Ein einziger Volladdierer. Um die beiden Teilsummen der Kaskade von Carry Save Addern zu addieren.
karadur schrieb: > such mal nach Barrel Shifter Was willst du denn damit in diesem Zusammenhang anstellen, wenn nicht grad um eine Zweierpotenz multipliziert wird?
A. K. schrieb: > Nö. Ein einziger Volladdierer. Um die beiden Teilsummen der Kaskade von > Carry Save Addern zu addieren. Was glaubst du, was ein Carry Save Adder ist? Das ist im Wesentlichen auch nur ein Volladder mit einem kleinen Extra.
A. K. schrieb: >> Eine größere Ansammlung von Volladdern. > > Nö. Ein einziger Volladdierer. Um die beiden Teilsummen der Kaskade von > Carry Save Addern zu addieren. PS: Wenn man es bitweise sieht, kommt das Gleiche raus. Weil dann ein 3:2 CSA ein FA ist dessen Übertrag diagonal statt horizontal läuft. Nur in der letzte Stufe nicht mehr. > Was glaubst du, was ein Carry Save Adder ist? Das ist im Wesentlichen > auch nur ein Volladder mit einem kleinen Extra. Yep. Wortweise betrachtet v. bitweise.
Hier mal ein "Paper" von 2009. Es sind einfach 32 Stück 32bit Volladdierer. Die Multiplikation dauerte 51ns. http://ijrte.academypublisher.com/vol02/no06/ijrte02068386.pdf Wir haben inzwischen 2014. Moderne FPGAs schaffen das Gleiche inzwischen vermutlich in 10ns.
Helmut S. schrieb: > Hier mal ein "Paper" von 2009. Es sind einfach 32 Stück 32bit > Volladdierer. Die Multiplikation dauerte 51ns. Ich finde in dem Paper 54ns, und zwar in der Version mit CSA (Fig 3) statt CLA (Fig 2). Also eben nicht mit 32-Bit Volladdierern (@c-hater: in den Bildern wird die wortweise Interpretation verwendet).
Moderne CPUs schaffen eine 64 bit floatingpoint multiplikation sogar in 900 ps. Gruß Kai
Wer sich gerne von Mathe erschlagen lässt: So gehts auch: https://de.wikipedia.org/wiki/Wallace-Tree-Multiplizierer Und den wohl schönsten Namen hat dieser Multipizierer: https://de.wikipedia.org/wiki/Dadda-Tree-Multiplizierer
Hallo binäre Multiplikation ist eine Kombi aus Shift und Addition.
karadur schrieb: > binäre Multiplikation ist eine Kombi aus Shift und Addition. Wenn du es sequentiell machst brauchst du keinen Barrel Shifter, weil in jedem Schritt nur um 1 Bit geschoben wird. Wenn du es - wie hier - parallel machst, dann steckt der Shift in der festen Verdrahtung. Wieder kein Barrel Shifter in Sicht.
Wenn im Multiplikator mehrere Nullen sind kannst du auch weiter shiften.
A. K. schrieb: > Was willst du denn damit in diesem Zusammenhang anstellen, wenn nicht > grad um eine Zweierpotenz multipliziert wird? Naja, die Adder werden ja immer um ein Bit verschoben, das könnte man sequenziell mit einem Barrel-Shifter machen. Gut, das geht dann nicht in zwei Taktzyklen (die ganze Multiplikation).
Helmut S. schrieb: > Wir haben inzwischen 2014. Moderne FPGAs schaffen das Gleiche inzwischen > vermutlich in 10ns. Kombinatorische Multiplizierer findet man bereits in der CDC6600 von vor 50 Jahren. Für die 48-Bit Mantisse der Fliesskommarechnung. Und zwar gleich 2 Stück. Nicht ganz so schnell, aber dafür aufgebaut aus Einzeltransistoren!
Wer es noch schneller will: http://web.ece.ucdavis.edu/~vojin/CLASSES/EEC280/Web-page/papers/Arithmetic/A%20Method%20for%20speed%20Optimized%20Partial%20product.pdf
karadur schrieb: > Wenn im Multiplikator mehrere Nullen sind kannst du auch weiter shiften. Schon mal einen gesehen, der das macht? Eine sequentielle ganzzahlige Multiplikation mit vorzeitigem Abbruch, weil nur noch Nullen übrig sind, habe ich schon gesehen, aber da brauchst du keinen Shifter. ;-)
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.