Rechnen zu können ist für Computer zentral

• Grundlegende Rechenoperationen sollten durch die Hardware unterstützt werden.

Schulalgorithmus für die Addition von Dezimalzahlen

\[ \begin{array}{l|cccccccc} \text{1. Summand} & & 9 & 3 & 8 & 9 & 9 & 8 & 9\\ \text{2. Summand} & & & 9 & 7 & 9 & 8 & 9 & 8\\ \text{Übertrag} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ \hline \text{Summe} & 1 & 0 & 3 & 6 & 9 & 8 & 8 & 7 \end{array} \]

Übertragung auf Binärzahlen

\[ \begin{array}{l|cccccccc} \text{1. Summand} & & 1 & 1 & 0 & 0 & 1 & 1 & 1\\ \text{2. Summand} & & 1 & 0 & 0 & 1 & 0 & 1 & 1\\ \text{Übertrag} & 1 & & & 1 & 1 & 1 & 1 & \\ \hline \text{Summe} & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \end{array} \]

Beobachtung zu den Überträgen

• \(1+1\) erzeugt einen Übertrag
• \(0+0\) eliminiert einen vorhandenen Übertrag
• \(0+1\) und \(1+0\) reichen einen vorhandenen Übertrag weiter
• Übertrag ist höchstens 1

Kann man Addition als Boolesche Funktion ausdrücken?

\(f_{HA}\) realisiert einen sog. Halbaddierer

\(f_{HA}:B^2\to B^2\)

\(x\)	\(y\)	\(c\)	\(s\)
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Schaltung für den Halbaddierer: \(\quad c=x\land y \qquad s=x\oplus y\)

Halbaddierer

• Berechnet Übertrag aus der Addition
• Berücksichtigt keinen Übertrag, der schon vorher entstanden ist

• Größe: \(2+(n-1)\cdot 5=5n-3\)
• Tiefe: \(1+(n-1)\cdot 3=3n-2\)

Realisierung „Addition von natürlichen Zahlen“

• Sehr gut strukturiert
• Größe \(5n-3\) \(\quad\rightarrow\) sehr klein
• Tiefe \(3n-2\) \(\quad\rightarrow\) viel zu tief

Warum ist unser Schaltnetz so tief?

• Offensichtlich gilt: Überträge brauchen sehr lange
• Verbesserungsidee: Überträge früh berechnen
• Wie? Struktureinsicht

• \((x_i,y_i)=(1,1)\) generiert Übertrag
• \((x_i,y_i)=(0,0)\) eliminiert Übertrag
• \((x_i,y_i)\in\{(0,1),(1,0)\}\) reicht Übertrag weiter

Dieses Verhalten ist sehr gut durch einen Halbaddierer realisierbar

Notation

• \(f_{HA}:B^2\to B^2\), \(f_{HA}(x_i,y_i)=(u_i,v_i)\)
• \(u_i=1\) generiert Übertrag, \(v_i=1\) reicht Übertrag weiter

Vorausberechnung der Überträge

\[ c_i=u_{i-1}\lor c_{i-1}v_{i-1} \]

Notation

• \(f_{HA}:B^2\to B^2\), \(f_{HA}(x_i,y_i)=(u_i,v_i)\)
• \(u_i=1\) generiert Übertrag, \(v_i=1\) reicht Übertrag weiter

Vorausberechnung der Überträge

\[ \begin{aligned} c_1 &= u_0\\ c_2 &= u_1\lor u_0v_1\\ c_3 &= u_2\lor u_1v_2\lor u_0v_1v_2\\ c_4 &= u_3\lor u_2v_3\lor u_1v_2v_3\lor u_0v_1v_2v_3\\ c_i &= u_{i-1}\lor u_{i-2}v_{i-1}\lor u_{i-3}v_{i-2}v_{i-1}\lor\ldots\lor u_0v_1v_2\cdots v_{i-1} \end{aligned} \]

\[ c_i=\bigvee_{j=0}^{i-1}\Big(u_j\land\bigwedge_{k=j+1}^{i-1}v_k\Big) \]

\[ c_i=\bigvee_{j=0}^{i-1}\Big(u_j\land\bigwedge_{k=j+1}^{i-1}v_k\Big) \]

Gesamttiefe des CLA: 4

Quelle: Denis Pitzschel

Quelle: Denis Pitzschel

Waren wir wirklich fair bei der Bestimmung der Ebenen?

• Beliebig lange Zahlen in Tiefe 4 addieren …
• Anzahl Eingänge eines Gatters heißt Fan-In

Großes Fan-In systematisch verkleinern

Beispiel: ODER, Fan-In 16

Waren wir wirklich fair bei der Bestimmung der Ebenen?

• Beliebig lange Zahlen in Tiefe 4 addieren …
• Anzahl Eingänge eines Gatters heißt Fan-In
• Wir vergleichen ein Schaltnetz mit
  • max. Fan-In 2 (Ripple-Carry-Addierer)
  • mit einem Schaltnetz mit max. Fan-In \(n\) (Carry-Look-Ahead-Addierer)
• Große Fan-Ins sind technologisch schwierig zu realisieren

Ziel: Vergleichbarkeit herstellen

Am Beispiel

• Aus Fan-In 16 bei Tiefe 1 (Größe 1)
• wird Fan-In 2 bei Tiefe 4 (Größe 15)

Wie lässt sich das verallgemeinern?

• Größe
  • Bei jeder Stufe halb so viele Gatter wie in der Stufe davor
  • \(\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\ldots+1\approx n\) (geometrische Reihe)
• Tiefe
  • So oft halbieren, bis man bei einem Gatter ist
  • \(\approx\log_2(n)\)

• Fokus auf AND-Gatter: \[ \sum_{i=1}^{n}\sum_{j=1}^{i}(j-1) \]
• Größe \(\approx\frac{n^3}{6}\)
• Tiefe \(\approx 2\log_2(n)\)

Wolfram Alpha

Realisierung der Addition von natürlichen Zahlen

• Gut strukturiert
• Größe \(\approx\frac{n^3}{6}\) \(\quad\leftarrow\) ziemlich groß
• Tiefe \(\approx 2\log_2(n)\) \(\quad\leftarrow\) ziemlich flach

Vergleich zum Ripple-Carry-Addierer

• CLA ist flach, aber groß (\(\approx\frac{n^3}{6}\)) und komplex
• Frage: Können wir den Ripple-Carry-Addierer nur etwas verbessern, sodass er zumindest manchmal schneller ist?

Idee: mehrere kleine RCAs, jeder mit eigenem Propagate-Check

• \(P_j\): alle Stellen des Blocks reichen weiter \(\Rightarrow\) Übertrag überspringt den Block
• Sonst entsteht der Übertrag im Block selbst: normaler RCA-Übertrag

\[ c_{\text{aus}}=c_{\text{RCA}}\lor\big(P_j\land c_{\text{ein}}\big) \]

• \(v_i=x_i\oplus y_i\) berechnet jeder Volladdierer ohnehin (erstes XOR) \(\Rightarrow\) nur herausführen
• \(P_j=v_0\land v_1\land v_2\land v_3\): ein Und-Gatter, parallel zur Übertragskette

• Größe: RCA plus je Block ein Und-Gatter für \(P_j\), ein Und und ein Oder \(\Rightarrow\) nur wenig größer als RCA
• Ungünstigster Übertrag: entsteht im ersten Block, läuft durch ihn hindurch, überspringt alle mittleren Blöcke und läuft nur noch durch den letzten Block
• Aber: Der lange Pfad durch alle RCAs existiert im Schaltnetz weiterhin
  • Die Tiefe des Schaltnetzes bleibt wie beim RCA
  • Er wird nur nie gebraucht: Muss ein Übertrag lange weitergereicht werden, nimmt er die Abkürzung
• Fazit: Kompromiss zwischen RCA (klein, langsam) und CLA (groß, flach)

Direkt mit Binärzahlen …

\[ \begin{array}{ccccccccccccccc} 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & \cdot & 1 & 1 & 1 & 0 & 1 & 0\\ \hline & & & & & & & & & & & & & & 0\\ & & & & & & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & \\ & & & & & & & & & & & & 0 & & \\ & & & & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & & & \\ & & & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & & & & \\ & & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & & & & & \\ \hline & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \end{array} \]

Multiplizieren heißt

• Nullen passend schreiben
• Zahlen passend verschoben kopieren
• Viele Zahlen addieren

Multiplikation ist

• Nullen passend schreiben
• Zahlen passend verschoben kopieren
• Viele Zahlen addieren

Beobachtung

• Nullen schreiben: einfach und kostenlos
• Zahlen verschieben und kopieren: einfach und kostenlos
• Viele Zahlen addieren: nicht ganz so einfach

Gibt es einen noch besseren Ansatz?

(Verrückte?) Idee: Vielleicht ist es einfacher, drei Zahlen zu ersetzen durch zwei Zahlen gleicher Summe?

Gibt es einen noch besseren Ansatz?

(Verrückte?) Idee: Vielleicht ist es einfacher, drei Zahlen zu ersetzen durch zwei Zahlen gleicher Summe?

Beobachtung

• Es gilt immer noch:
  Gleiche Summe \(\rightarrow\) Korrektheit
• Weniger Fortschritt:
  \(3\rightarrow 2\) statt \(2\rightarrow 1\)

Gesucht

• Addierer mit drei Eingängen und zwei Ausgängen, für den gilt: \[ x+y+z=a+b \]

Gefunden

• Volladdierer, der für \(x,y,z\in\{0,1\}\) folgendes Resultat liefert: \[ x+y+z=2\cdot c+s \]
• \(s\) ist das Summenbit
• \(2\cdot c\) ist das Übertragsbit, bezogen auf seine Stelle eine Position weiter links

• Parallelschaltung von \(n\) Volladdierern
• Liefern jeweils die Summenbits
• und die Übertragsbits

Diese Volladdierer sind nicht verkettet

• Jeder liefert ein \(s\)-Bit und ein \(c\)-Bit
• Aus diesen Bits werden
  • das Summen-Wort gebildet, das an der höchstwertigen Stelle (Anfang) mit 0 erweitert wird,
  • und das Carry-Wort, das an der niederwertigsten Stelle (Ende) mit 0 erweitert wird
• Summe aus Summen-Wort und Carry-Wort bildet das Resultat

Wir addieren

• \(x=001001\)
• \(y=001111\)
• \(z=001100\)

\[ \begin{array}{lccccccccl} \text{Summen-Wort} & = & (0) & 0 & 0 & 1 & 0 & 1 & 0 & = 0001010\\ \text{Carry-Wort} & = & 0 & 0 & 1 & 1 & 0 & 1 & (0) & = 0011010 \end{array} \]

\[ \begin{array}{l|cccccccc} \text{Summand } x & & & x_5 & x_4 & x_3 & x_2 & x_1 & x_0\\ \text{Summand } y & + & & y_5 & y_4 & y_3 & y_2 & y_1 & y_0\\ \text{Summand } z & + & & z_5 & z_4 & z_3 & z_2 & z_1 & z_0\\ \color{gray}\text{Resultat} & & & \color{gray}2c_5+s_5 & \color{gray}2c_4+s_4 & \color{gray}2c_3+s_3 & \color{gray}2c_2+s_2 & \color{gray}2c_1+s_1 & \color{gray}2c_0+s_0\\ \hline \text{Carry-Wort} & & c_5 & c_4 & c_3 & c_2 & c_1 & c_0 & (0)\\ \text{Summen-Wort} & + & (0) & s_5 & s_4 & s_3 & s_2 & s_1 & s_0 \end{array} \]

\[ \begin{array}{l|cccccccc} \text{Summand } x & & & 0 & 0 & 1 & 0 & 0 & 1\\ \text{Summand } y & + & & 0 & 0 & 1 & 1 & 1 & 1\\ \text{Summand } z & + & & 0 & 0 & 1 & 1 & 0 & 0\\ \hline \text{Carry-Wort} & & 0 & 0 & 1 & 1 & 0 & 1 & (0)\\ \text{Summen-Wort} & + & (0) & 0 & 0 & 1 & 0 & 1 & 0\\ \hline \text{Summe} & & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{array} \]

Berechnung von drei \(n\)-Bit-Zahlen

• Zum Einsatz kommen \(n\) Volladdierer
• Größe: \(5n\)
• Tiefe: 3

Beobachtung

• Der (große) Carry-Look-Ahead-Addierer wird in einem Wallace-Tree erst als letzte Operation benötigt
• Der Wallace-Tree hat somit für die Addition von \(n\) Zahlen folgende Eigenschaften:
  • Größe: \(\approx\frac{n^3}{3}\) (proportional, bedingt durch den CLA)
  • Tiefe: \(\approx 3\log_{3/2}(n)+2\log_2(n)\approx 7{,}13\log_2(n)\)

Fazit: Multiplikation ist nicht wesentlich teurer oder langsamer als die Addition