Inhalt der Lehrveranstaltung

Methoden zur optimierten Berechnung von Addition, Multiplikation, Division und elementaren mathematischen Funktionen in Hardware-Implementierungen (wie zB in Prozessoren). Die Methoden werden in ihrer algorithmischen Form besprochen und getestet (es sind im Prinzip keine Schaltungen zu entwickeln).

Prüfungsmodus

Es gibt wöchentlich auszuarbeitende Übungen. Anwesenheit ist wichtig. Es gibt drei kleine Tests, in denen genau die wöchentlichen Übungen unverändert auf Papier zu lösen sind. Die zu modifizierenden Programme sind dabei vorgedruckt verfügbar. Die Mini-Tests werden am 23. April, am 21. Mai und am 25. Juni stattfinden.

Unterlagen

• Skriptum im PDF-Format und im PS-Format.

• Der gesamte Sourcecode der Algorithmen aus dem Skriptum in einem File.

• Alluvion, die Programmiersprache compiliert für Linux oder im Sourcecode.

Übungsangaben

• bis 12.3.: Implementiere einen Subtrahierer (HalfSub, FullSub, Sub<n>) analog zum Addierer.

• bis 19.3.: Modifiziere den RCLA_Add-Algorithmus so, dass das global hereinkommende Carry-Bit ohne Zwischenverarbeitung an jeder Bitstelle zur Berechnung verwendet wird. Also, dass z[i]=xor(or(g,and(p,c)),xor(x[i],y[i])) ist, wobei g,p die Generate- und Propagate-Bits des Blocks x[0:i-1]+y[0:i-1] sind. Letztere sollen aber nach wie vor in logarithmischer Komplexität berechnet werden.

• bis 26.3.: Erzeuge eine Funktion analog zu CondSum_Add, die kein incoming carry annimmt (d.h. einfach Addition zweier Zahlen x+y). Der rekursive Aufruf mit fixem Carry 0 kann dann auch durch einen Aufruf dieser Funktion ersetzt werden. Für fixes Carry 1 empfiehlt sich dann eine eigene Funktion analog zu ersterer.
  Hier noch die modifizierte Version der Funktion CondSum_Add aus der VL.

• bis 16.4.: Erzeuge eine Funktion (p,z[0:n]) = RCS_Add<n> (x[0:n-1], y[0:n-1], c), die die CarrySkip-Addition rekursiv durchführt. Wenn n>1, dann müssen folgende Schritte durchgeführt werden: (1) Rekursiver Aufruf für untere Hälfte [0:m-1] (liefert p0 und c0). (2) Rekursiver Aufruf für obere Hälfte [m:n-1] unter Verwendung von c0. (3) p aus p0 und p1. (4) cout mit der CarrySkip-Formel aus cin, c1 und p. Wenn n=1, p und z[0:1] berechnen wie üblich.

• bis 23.4.:

  • Implementiere einen (7,3)-Zähler (z[0,2]=Count7(x[0,6])) allein mit Hilfe von (3,2)-Zählern (also Aufrufen von FullAdd).

  • freiwillig: Verwende den (7,3)-Zähler in CS_Add_Gen.

• bis 30.4.: Implementiere eine Funktion z[0,n+m-1]=RMul<n,m>(x[0,n-1],y[0,m-1]), die z=x*y berechnet, indem sie rekursiv für k=m/2 zuerst RMul<n,k>(x[0,n-1],y[0,k-1]) und dann RMul<n,m-k>(x[0,n-1],y[k,m-1]) aufruft und dann die Ergebnisse richtig zusammenzählt (d.h. das zweite Ergebnis um k Stellen nach links verschoben). Falls m=1 ist (Rekursionsabbruch), soll das Ergebnis natürlich z[0,n-1]=And<n>(x[0,n-1],y[0]) sein.

• bis 7.5.: Implementiere die Funktion MulRadix8, die eine Multiplikation zur Basis 8 realisiert. (Das modifizierte MulRadix4 hätte ich fast vergessen.)

• bis 14.5.: Implementiere die Funktion (q[0:n-2], r[0:1]) = Div3<n> (x[0:n-1]), die die Zahl x durch 3 dividiert und Quotient q und Rest r ausgibt. Anleitung: Wenn im Schritt i der Divisor 3 vom Zwischenrest r[i:i+2] subtrahiert wird (oder auch nicht), ergibt sich das Quotientenbit daraus, ob der Zwischenrest größer oder gleich 3 ist. Das ist genau dann der Fall, wenn r[i+2]='1' ist oder r[i:i+1]='11'. Das Subtrahieren von 3 (wenn das Quotientenbit 1 ist), entspricht einer Addition von '00' mit Carry-In '1'. Wenn nicht subtrahiert wird, kann man ebenfalls '00' addieren, aber es muss das Carry-In auch '0' sein. Dadurch wird das ganze einfach. Das Addieren führt man am besten händisch durch, d.h. ohne eine XY_Add-Funktion, weil der Summand ja eh '00' ist.

• bis 21.5.: Implementiere analog zur vorigen Aufgabe eine Non-Restoring-Division durch 3. Achtung: Der ausgegebene Rest r[0:2] braucht ein Bit mehr, weil er negativ sein kann. Und am Anfang muss r[n] = x[n-1] gesetzt werden.

• bis 4.6.: Verbessere die SRT-Division folgendermaßen:

  • Zeile 9-12: Führe die Addition s[0,3] = r[i+n-2,i+n+1] + rc[i+n-2,i+n+1] unter Verwendung von (g1,p1)=GP(r[i+n-1],rc[i+n-1]), (g2,p2)=GP(r[i+n],rc[i+n]), und (g,p)=GP_Op(g1,p1,g2,p2) durch.

  • Zeile 24-29: Ersetze Add durch RCLA_Add. Führe die Umwandlung von q1 und q0 in q mittels einer (rekursiven) Funktion (g,p,q[0,n-1])=S2U<n>(q1[0,n-1],q0[0,n-1],c) durch. Diese Funktion ist analog zu RCLA_Add zu implementieren. Unterschied: im Fall n=1 ist q[0]=xor(q0[0],c), g=and(q0[0],q1[0]) und p=and(not(q0[0]),not(q1[0])).

• bis 11.6.: Modifiziere die Funktion Msf_Div so, dass bei der Multiplikation mit r (bzw. dc im Skriptum) die Struktur von r berücksichtigt wird: und zwar stehen die ersten k Bits von r fest (k vor der Multiplikation mit 2). Das erste ist 1, die nachfolgenden sind 0. Übergebe dazu k and PCS_Mul und lasse dort iy nur bis ny-k-1 gehen. Das vorderste Bit von y, das ja immer 1 ist, muss dann extra behandelt werden.

• bis 18.6.: Modifiziere die Funktion Sqrt<n> so, dass sie auch für ungerade n funktioniert.

• bis 25.6.: Wandle die Funktion Expsf in eine Funktion Pow2 um, die statt e-hoch-x 2-hoch-x berechnet. Dazu sind die Werte der Tabelle lntab durch 2-er-Logarithmen zu ersetzen.

Literatur

• I. Koren. Computer Arithmetic Algorithms. A.K. Peters Ltd., 2001. ISBN 1568811608. (45.2.1-77)

• A. R. Omondi. Computer Arithmetic Systems: Algorithms, Architecture, and Implementation. Prentice Hall, 1994. ISBN 0-13-334301-4. (46.1.2-5)