Arithmetik

Der hier angegebene bitserielle Multi­plizierer [SSLH 03] wurde in einer 16-Bit-Version im Prozessor der Systola-1024, einem hoch­integrierten Parallel­rechner mit 1024 Prozessoren, eingesetzt. Die formale Verifikation der Multi­pliziererschaltung basiert auf der Methode von Moldovan und Fortes [MF 86].

Multiplikationsschema

Bild 1 zeigt das Standard­schema für die Multi­plikation zweier n-Bit-Zahlen a_n-1, ..., a₀ und b_n-1, ..., b₀, hier für n = 3. Die angegebenen Bit-Produkte müssen gebildet werden und stellen­richtig addiert werden.

Im folgenden Algorithmus wird bei der Addition der Bit-Produkte an jeder Position (i, j) als Zwischen­ergebnis ein Summenbit s_i,j und ein Übertragsbit c_i,j erzeugt. Diese Zwischen­ergebnisse und ebenso die Eingabe­variablen werden an benachbarte Positionen weiter­gegeben und dort weiter­verarbeitet.

Datenabhängigkeiten

Bild 2 zeigt, wie die Zwischen­ergebnisse und Eingabe­variablen weiter­gegeben werden. Beispiels­weise wird das Summenbit s, das als Zwischen­ergebnis an Position (i, j) gebildet worden ist, als nächstes an Position (i+1, j) benötigt. Die Eingabe­variable a wird von Position (i, j) an Position (i+1, j+1) weiter­gegeben.

Die Differenz zwischen der Position, an der eine Variable benötigt wird und der Position, an der sie erzeugt wird, ist der Daten­abhängigkeits­vektor dieser Variable. Zusammen bilden die Daten­abhängigkeits­vektoren aller Variablen die Daten­abhängigkeits­matrix D. Die Daten­abhängigkeits­matrix des obigen Multi­plikationsschemas ist

Multiplikationsalgorithmus

Der Multi­plikationsalgorithmus ist durch folgende Rekursions­gleichungen gegeben. Hierbei sind die booleschen Funktionen S wie folgt definiert:

Die Funktion S_k hat den Wert 1, wenn genau k ihrer Argumente gleich 1 sind, und sonst 0. S_k,m ist dasselbe wie S_k ∨ S_m. Durch S_1,3 und S_2,3 werden also das Summenbit und das Übertragsbit berechnet.

Rekursions­gleichungen

Anfangswerte für die Rekursion sind:

für alle i, j ∈ {0, ..., n-1}. Alle sonstigen Anfangswerte sind 0.

Die Rekursionen werden für alle Index­positionen (i,j) berechnet, die nötig sind, um das Ergebnis der Multi­plikation zu erzeugen. Anders als beim Standard­schema der Multi­plikation werden die Ergebnisbits nicht "unterm Strich" abgelesen, sondern diagonal. Die Ergebnisbits sind s_2n,2n-1, ..., s_1,0.

Transformation

Um aus dem Algorithmus eine Schaltung zu erhalten, wird der Indexraum {(i, j)} des Algorithmus in den Indexraum {(t, p)} aus Zeit und Prozessor­elementen trans­formiert. Dies geschieht nach der Methode von Moldovan und Fortes [MF 86]. Die lineare Trans­formation

bildet jede Index­position (i, j) auf eine entsprechende Index­position (t, p), bestehend aus Zeit und Prozessor­element, ab. Dabei werden die Index­positionen als Spalten­vektoren aufgefasst. Beispiels­weise ist

T·(1,1)^T  =  (1,0)^T,

d.h. die Berechnung an Index­position (i, j) = (1,1) des Multi­plikationsalgorithmus wird zum Zeitpunkt t = 1 in Prozessor p = 0 ausgeführt. Bild 3 zeigt den trans­formierten Indexraum {(t, p)}.

Das erste Bit des Multi­plikationsergebnisses ist s_1,0; es erscheint zum Zeitpunkt t = 1 am Eingang von Prozessor­element p = -1 (d.h. am Ausgang von Prozessor­element p = 0), denn es ist

T · (1, 0)^T  =  (1, -1)^T.

Das letzte Ergebnisbit erscheint zum Zeitpunkt t = 2n am Eingang von Prozessor­element p = -1, denn es ist

T · (2n, 2n-1)^T  =  (2n, -1)^T.

Die mit der linearen Trans­formation T trans­formierte Daten­abhängigkeits­matrix gibt an, in welcher Weise die Variablen im trans­formierten Indexraum und damit in der Schaltung weiter­gegeben werden.

So wird beispiels­weise s in jedem Takt zum vorherigen Prozessor­element weiter­gegeben, c wird in jedem Takt im selben Prozessor­element gespeichert, a wird ebenfalls in jedem Takt im selben Prozessor­element gehalten, b wird in Null Takten jeweils um ein Prozessor­element weiter­gegeben, d.h. es wird gleichzeitig an alle Prozessor­elemente gegeben.

Die Bits des Operanden a müssen somit offenbar parallel an den Prozessor­elementen anliegen. Es ist jedoch möglich, den Operanden a vor Beginn der eigentlichen Multi­plikation bitseriell einzugeben und mit Hilfe eines Steuer­signals in den Prozessor­elementen zu speichern.

Bitserieller Multiplizierer

Das folgende Bild 4 zeigt die entsprechende Multi­pliziererschaltung, hier für eine Operanden­länge von n = 3. Jedes der n Prozessor­elemente besteht aus einem AND-Gatter zur Bildung des Bit-Produktes, einem Volladdierer (full adder), sowie zwei Verzögerungs­elementen.

Bild 4: Bit-serieller Multiplizierer für Operanden der Länge n = 3

Es ist möglich, zusätzlich einen Operanden s einzugeben und damit s = s + a·b zu berechnen. Die ersten n Bits müssen vor Beginn der eigentlichen Multi­plikation in den Multi­plizierer geladen werden.

Der Multi­plizierer benötigt n Takte zum Laden des Operanden a und der ersten n Bits von s, anschließend dann noch weitere 2n Takte zur Ausgabe des Ergebnisses, also insgesamt 3n Takte.

Zusammenfassung

Der hier vorgestellte bitserielle Multi­plizierer für n-Bit-Operanden besteht aus n Prozessor­elementen, die im Wesentlichen jeweils ein AND-Gatter, einen Volladdierer sowie Verzögerungs­elemente enthalten. Alle Operanden werden bitseriell eingegeben, das Ergebnis wird bitseriell ausgegeben. Eine Multi­plikation dauert 3n Takte. Die Korrektheit der Schaltung ergibt sich unmittelbar durch Trans­formation des Standard-Multi­plikationsschemas.

Literatur

[SSLH 03]   M. Schimmler, B. Schmidt, H.W. Lang, S. Heithecker: An Area-Efficient Bit-Serial Integer Multiplier. In: H.R. Arabnia, L.T. Yang (Eds.): Proceedings of the International Conference on VLSI, CSREA Press (2003)

[MF 86]   D.I. Moldovan, J.A.B. Fortes: Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays. IEEE Transactions on Computers C-35, 1, 1-12 (1986)

[Web 1]   http://www.inf.fh-flensburg.de/lang/papers/multipli/multipli.htm