Arithmetik

Bitserieller Multiplizierer (1)

 aufwärts

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 an-1, ..., a0 und bn-1, ..., b0, hier für n = 3. Die angegebenen Bit-Produkte müssen gebildet werden und stellen­richtig addiert werden.

Bild 1: Standardschema für die Multiplikation
Bild 1: Standardschema für die Multiplikation

Im folgenden Algorithmus wird bei der Addition der Bit-Produkte an jeder Position (i, j) als Zwischen­ergebnis ein Summenbit si,j und ein Übertragsbit ci,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.

Bild 2: Weitergeben der Eingabevariablen und Zwischenergebnisse
Bild 2: Weitergeben der Eingabevariablen und Zwischenergebnisse

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

  a b s c
  D  = i 1 0 1 1
 j 1 1 0 1

 

Multiplikationsalgorithmus

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

Die Funktion Sk hat den Wert 1, wenn genau k ihrer Argumente gleich 1 sind, und sonst 0. Sk,m ist dasselbe wie Sk oder Sm. Durch S1,3 und S2,3 werden also das Summenbit und das Übertragsbit berechnet.

Rekursions­gleichungen
ai+1,j+1 = ai,j
bi,j+1 = bi,j
si+1,j = S1,3 (ai,j·bi,jsi,jci,j)
ci+1,j+1 = S2,3 (ai,j·bi,jsi,jci,j)

 

Anfangswerte für die Rekursion sind:

a0,j = aj 
bi,i = bi 

für alle i, j Element {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 s2n,2n-1, ..., s1,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

  i j
  T   = t 1 0
 p -1 1

 

bildet jede Index­position (i, j) auf eine ent­sprechende 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)}.

Bild 3: Transformierter Indexraum
Bild 3: Transformierter Indexraum

Das erste Bit des Multi­plikationsergebnisses ist s1,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.

  a b s c
TD  = t 1 0 1 1
 p 0 1 -1 0

 

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 ent­sprechende 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
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  

 

Weiter mit:   [Bitserieller Multiplizierer (2)]   oder   up

 

homeH.W. Lang   Fachhochschule Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 08.04.2003   Updated: 09.02.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Angewandte Informatik

mit Schwerpunkten auf Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik