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. Daher ist am Schluss kein Test notwendig. Anwesenheit ist aber wichtig.

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 14.3.: Implementiere einen Subtrahierer (HalfSub, FullSub, Sub<n>) analog zum Addierer.
• bis 4.4.: 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 11.4.: Erzeuge eine Funktion analog zu CondSum_Add, die kein incoming carry annimmt (d.h. einfach Addition zweier Zahlen x+y). Da in CondSum_AddMux jedoch ein Aufruf von CondSum_Add mit carry=1 stattfindet, muss man auch eine Variante programmieren, die x+y+1 berechnet.
• bis 18.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). (2) Berechnung von c_out nach der CarrySkip-Formel aus c_in, z[m] und p0. (3) Rekursiver Aufruf für obere Hälfte [m,n-1]. (4) p aus p0 und p1. Wenn n=1, p und z[0,1] berechnen wie üblich.
• bis 25.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).
• bis 2.5.: Implementiere eine Funktion z[0,n]=TriAdd<n>(x[0,n*(n+1)/2-1]), die mit Hilfe von CS_Add_Gen n Wörter der Länge 1, 2, 3, ..., n zusammenzählt. Also zB TriAdd<3>('1','01','101') sollte 0111 ergeben.
• bis 9.5.:
  • 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.
  • Ganz einfach: Modifiziere MulSigned so, dass nur das Argument x[0,n-1] vorzeichenbehaftet (2-er Komplement) ist, nicht aber y[0,n-1].
• bis 23.5.: Implementiere die Funktion MulRadix8, die eine Multiplikation zur Basis 8 realisiert.
• bis 30.5.: Implementiere eine Non-Restoring-Division durch 3 in der Funktion (q[0,n-1], r[0,2]) = NR_Div3<n> (x[0,n+1]). Hinweis: Am Anfang muss r[0,n+1] = x[0,n+1]; r[n+2] = r[n+1]; gesetzt werden. xd ist dann '011', wenn q[i]=0, und '100', wenn q[i]=1.
• bis 6.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])). Warum?
  Achtung: Vorführung wegen geringer Teilnehmerzahl in der LV um eine Woche verschoben.
• auch noch bis 13.6.: Versuche durch Wahl des Dividenden und des Divisors den Fehler, der in M_Div durch die Beschränkung des Zählers auf n+2 Bit entsteht, zu maximieren. Variiere auch die Präzision des Zählers. Notiere ausgewählte Beispiele. Erkläre den Grund für den Fehler.
• bis 20.6.: Modifiziere die Funktion Sqrt<n> so, dass sie auch für ungerade n funktioniert.
• bis 27.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)