Dumme Frage: 32x32 Bit Multiplikation in 2 Zyklen ?

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.

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:
>> 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

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.

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. ;-)