ParAlg, Kapitel 2.2

2.2 Binäraddierer mit Carry Look-Ahead

Ein Schaltkreis für binäre Addition

Dieses Teilkapitel finden Sie, in ausführlicherer Darstellung, auch als Kapitel 1.3 in Theoretische Informatik II. Das Problem der Addition zweier Binärzahlen ist wie folgt: Wir haben zwei Zahlen $x, y \in N$ in Ihrer Binärschreibweise $x = (x_{n - 1}, \dots, x_{2}, x_{1}, x_{0})$ und $y = (y_{n - 1}, \dots, y_{2}, y_{1}, y_{0})$ gegeben und wollen die Summe $s := x + y$ berechnen bzw. ihre Binärdarstellung $(s_{n}, s_{n - 1}, \dots, s_{1}, s_{0})$ . Wir gehen hier davon aus, dass $x$ und $y$ beide mit $n$ Bits repräsentiert sind (falls eine Zahl weniger Bits braucht, können wir sie immer mit führenden Nullen auffüllen). Die Summe $s$ benötigt dann mindestens $n + 1$ Bits. Bitte beachten Sie die unübliche "verkehrtrumme" Schreibweise $(x_{n - 1}, x_{n - 2}, \dots, x_{1}, x_{0})$ , die daher rührt, dass

\begin{array}{r} x = \sum_{i = 0}^{n - 1} x_{i} 2^{i}, \end{array}

wir aber das most significant bit links schreiben. Binäraddition geht wie Dezimaladdition, nur einfacher. Hier ein Beispiel:

Mit etwas mehr Notation sieht das dann so aus:

Wir brauchen also einen Schaltkreis mit drei Inputs $x_{i}, y_{i}, c_{i}$ , der die zwei Outputwerte $s_{i}$ und $c_{i + 1}$ berechnet:

Dann können wir diese Schaltkreise hintereinander schalten

und erhalten den sogenannten Ripple-Through-Adder.

Beobachtung 2.2.1 Ein Ripple-Through-Adder für $n$ -Bit-Zahlen hat $O (n)$ Gates und $O (n)$ Tiefe.

Übungsaufgabe 2.2.1 Implementieren Sie den Schaltkreis oneBitAdder. Versuchen Sie, so wenig Gates (AND, OR, NOT) wie möglich zu verwenden.

Der Ripple-Through-Adder ist ein sequentieller Algorithmus: um $c_{i + 1}$ zu berechnen, müssen wir zuerst $c_{i}$ kennen. Auch wenn wir uns jeden One-Bit-Adder als separaten Prozessor vorstellen, braucht der Algorithmus dennoch $n$ Zeitschritte. Es findet also gar keine Parallelisierung statt.

Carry-Lookahead: eine effiziente Parallelisierung

Effizientere Lösungen beginnen oft mit einer guten Definition. Wir betrachten ein Interval $[a, b] := {a, a + 1, \dots, b}$ für $0 \leq a \leq b \leq n - 1$ und fragen uns, ob wir was wir über den Wert von $c_{b + 1}$ sagen können, wenn wir nur die Werte $x_{b}, x_{b - 1}, \dots, x_{a}$ und $y_{b}, y_{b - 1}, \dots, y_{a}$ kennen. Hier ein paar konkrete Beispiele für das Interval $[a, b] = [5, 8]$ :

An Stelle 7 entsteht auf jeden Fall ein Übertrag, egal was $c_{7}$ ist. Es gilt also $c_{8} = 1$ . Stelle 8 reicht dann den Übertrag weiter und somit ist $c_{9} = 1$ , unabhängig von den Werten $(x_{4}, \dots, x_{0})$ und $(y_{4}, \dots, y_{0})$ . Ein weiteres Beispiel:

An Stelle 5 wird ein Übertrag erzeugt (unabhängig der weiter rechts stehenden Werte) und Stelle 6 reicht ihn weiter; an Stelle 7 wird er jedoch "verschluckt", und auch Stelle 8 erzeugt nicht aus eigener Kraft einen neuen Übertrag. Daher gilt $c_{9} = 0$ . Zuguterletzt:

Keine Stelle erzeugt aus eigener Kraft einen Übertrag, aber jede Stelle würde ihn weiterreichen, wenn denn einer hereinkäme. Daher gilt: $c_{9} = c_{5}$ . Ein Intervall kann also im Prinzip drei Dinge tun: (1) einen Übertrag erzeugen, in welchem Fall wir von einem Carry generate sprechen; (2) einen Übertrag nicht erzeugen, aber zumindest weiterreichen; (3) einen Übertrag verschlucken verschlucken. Wenn (1) der Fall ist, sprechen wir von Carry generate. Wenn (1) oder (2) der Fall ist, von Carry propagate. Wir fassen zusammen und formalisieren:

Beobachtung / Definition (Carry propagate und Carry generate für Intervalle) 2.2.2 Sei

I = {a, a + 1, \dots, b}

ein Intervall natürlicher Zahlen. Die Werte

p_{I} = p_{I} (x, y)

und

g_{I} = g_{I} (x, y)

sind wie folgt definiert:

Wenn für alle $i \in I$ das Paar $x_{i}, y_{i}$ den Wert $(0, 1)$ oder $(1, 0)$ hat, dann ist $p_{I} = 1$ und $g_{I} = 0$ .
Ansonsten sei $i^{*} := max {i \in I | (x_{i}, y_{i}) \in {(0, 0), (1, 1)}}$ .
- Falls $(x_{i^{*}}, y_{i^{*}}) = (1, 1)$ , dann sind $p_{I} = g_{I} = 1$ .
- Falls $(x_{i^{*}}, y_{i^{*}}) = (0, 0)$ , dann sind $p_{I} = g_{I} = 0$ .

Insbesondere für ein-elementige Intervalle $I = [a, a]$ gilt $p_{[a]} = x_{a} \lor y_{a}$ und $g_{[a]} = x_{a} \land y_{a}$ . Es gilt $g_{I} \leq p_{I}$ .

Was nützt das uns nun? Beachten Sie, dass $c_{0} = 0$ immer gilt, und daher $c_{i + 1} = g_{[0, i]}$ gilt. Der Übertrag an Stelle $i + 1$ ist genau dann 1, wenn das Interval $[0, i]$ einen erzeugt. Wenn wir die $g_{[0, i]}$ also parallel berechnen können, dann auch die Summe $s_{n}, s_{n - 1}, \dots, s_{1}, s_{0}$ .

Carry generate und propagate parallel berechnen

Der Trick ist nun, dass wir $g_{I}$ und $p_{I}$ aus Teilintervallen zusammensetzen können. Sei $a < i < b$ und $I = [a, b]$ , $J = [a, i]$ und $K = [i + 1, b]$ .

Wenn Interval $K$ einen Übertrag erzeugt, dann erzeugt das Gesamtinterval $I$ einen; wenn $K$ verschluckt, dann verschluckt $I$ ; ansonsten (wenn $K$ nur weiterreicht), dann tut $I$ das, was $J$ tut. Es gilt also

Beobachtung 2.2.3 Für

a < b

und

a \leq i \leq b

sei

I = [a, b]

J = [a, i]

und

K = [i + 1, b]

. Dann gilt

\begin{aligned} p_{I} & = g_{K} \lor (p_{K} \land p_{J}), \\ g_{I} & = g_{K} \lor (p_{K} \land g_{J}) . \end{aligned}

Wir können uns also einen schönen Generate-Propagate-Schaltkreis" bauen:

Wir nennen dieses Bauteil kurz ein $g p$ -Gate. Auch fassen wir die zwei Werte $g_{I}$ und $p_{I}$ zu einem Paar zusammen: $g p_{I} := (g_{I}, p_{I})$ . Wenn nun $n = 2^{d}$ eine Zweierpotenz ist, dann können wir einen vollständigen Binärbaum aus $g p$ -Gates bauen:

Die Intervalle, die in einem solchen Baum vorkommen, nenn wir Binärintervalle. Es sind Intervalle der Form $[a, b]$ , wobei $a$ und $b$ die $d$ -Bit-Binärdarstellungen

\begin{aligned} (a)_{2} & = (a_{d - 1} a_{d - 2} \dots a_{k} \underset{k viele}{\underset{⏟}{0 0 \dots 0}}) \\ (b)_{2} & = (a_{d - 1} a_{d - 2} \dots a_{k} \underset{k viele}{\underset{⏟}{1 1 \dots 1}}) \end{aligned}

haben. Es gibt $2 n - 1$ solche Binärintervalle, und so viele Knoten hat auch der obige Baum. Jedes $g p_{[i]}$ können wir mit $2$ Gates und Tiefe 1 berechnen; jedes $g p$ -Gate braucht 4 Gates und hat Tiefe 2. Das ergibt für $n = 2^{d}$ eine Tiefe von $1 + 2 d = 1 + 2 \log n$ und insgesamt $6 n - 4$ Gates.

Beobachtung 2.2.4 Die obige Konstruktion resultiert in einem Schaltkreis BI, der $2 n$ Bits $x_{n - 1}, \dots, x_{0}, y_{n - 1}, \dots, y_{0}$ als Input nimmt und $2 n - 1$ Ouput-Gates hat, nämlich für jedes Binärinterval $I$ eines, das $g p_{I}$ ausgibt. Der Schaltkreis BI hat $6 n - 4$ Gates und Tiefe $1 + 2 \log n$

Jetzt muss man sich nur noch überlegen, wie man parallel alle $p g_{I}$ für alle Präfixintervalle $I = [0, b]$ .

Präfixintervalle $[0, b]$ . Wir konstruieren nun einen Schaltpreis PI, der $g p_{I}$ für alle Präfixintervalle berechnet. Er hat $n$ Outputs (jede eines für $[0, 0], [0, 1], [0, 2], \dots, [0, n - 1]$ ) und hat $2 n - 1$ Inputs, je eines für jedes Binärinterval $K$ . Die Konstruktion wird einfacher, wenn wir statt dem geschlossenen Interval $[0, b]$ das halboffene Interval $[0, b) := [0, b - 1]$ betrachten. Wir müssen nun also $g p_{[0, b)}$ berechnen für $b = 1, 2, \dots, n$ . Wenn $b$ eine Zweierpotenz ist, dann ist $[0, b)$ ein Binärinterval, wir können also den entsprechenden Input gleich als Output durchleiten. Das eliminiert auch den Fall $b = n = 2^{d}$ und wir müssen uns nur Gedanken machen über Werte $1 \leq b \leq n - 1$ . Da $b < 2^{d}$ gilt, hat $b$ eine Binärdarstellung mit $d$ Bits. Wegen $b \geq 1$ hat diese mindestens eine $1$ . Wir fokussieren uns auf die am weitesten rechts stehende 1:

\begin{array}{r} b = {(b_{n - 1} b_{n - 2} \dots b_{k + 1} 1 0^{k})}_{2} \end{array}

wobei $0^{k}$ eine Folge von $k$ Nullen ist (und nicht Null hoch $k$ ). Wir schreiben $c = b_{n - 1} b_{n - 2} \dots b_{k + 1}$ und zerlegen $I = [0, b)$ wie folgt:

\begin{aligned} I & = [0, b) = [0^{d}, c 1 0^{k}) \\ (1) & = [0^{d}, c 0 0^{k}) \cup [c 0 0^{k}, c 1 0^{k}) \\ =: [0, b^{'}) \cup K \\ (2) & =: I^{'} \cup K . \end{aligned}

Hier zeigt sich der Vorteil der halboffenen Intervalle: für $a \leq b \leq c$ gilt einfach $[a, c) = [a, b) \cup [b, c)$ , ohne unangenehmes $+ 1$ irgendwo. Das zweite Interval in $(1)$ ist $[c 0 0^{k}, c 1 0^{k}) = [c 0 0^{k}, c 0 1^{k}]$ , wenn wir es wieder als geschlossenes Interval schreiben. Wir sehen: es ist ein Binärinterval und steht dem Schaltkreis PI bereits als Input zur Verfügung. Wir können nun $g p_{I}$ mit einem zusätzlichen $g p$ -Gate aus $g p_{I^{'}}$ und $g p_{K}$ berechnen. Für $g p_{I^{'}}$ verfahren wir rekursiv. Um abzuschätzen, wie tief diese Rekursion geht, zählen wir die Anzahl der Einsen in der Binärdarstellung von $b$ . In $b$ ist diese maximal $d$ , und in $b^{'}$ ist sie eins weniger als in $b$ ; nach maximal $d - 1$ Rekursionsschritten sind wir also bei einem Interval $[0, b^{″})$ angelegt, wo die Binärdarstellung von $b^{″}$ eine einzige $1$ hat. Die Zahl $b^{″}$ ist also eine Zweierpotenz und $[0, b^{″})$ somit ein Binärinterval, und wir haben $g p_{[0, b^{″})}$ bereits vorliegen. Wir können $g p_{I}$ also mit maximal $d - 1$ hintereinander geschalteten $g p$ -Gates berechnen. Jedes einzelne $g p$ -Gate hat Tiefe 2, und daher erhalten wir:

Beobachtung 2.2.5 Der Schaltkreis PI hat Tiefe $2 (d - 1) = 2 \log (n) - 2$ .

Wieviele Gates hat dieser Schaltkreis? Wenn wir für jedes $1 \leq b \leq n - 1$ die Konstruktion parallel durchführen und mit $| b |_{1}$ die Anzahl der Einsen in der Binärdarstellung von $b$ schreiben, dann brauchen wir

\begin{array}{r} \sum_{b = 1}^{n - 1} (| b |_{1} - 1) \leq \sum_{b = 1}^{n - 1} (d - 1) = (d - 1) (n - 1) \leq n \log n . \end{array}

viele $g p$ -Gates. In der Realität hat nicht jedes $b$ genau $d$ viele Einsen, daher ist der tatsächliche Wert der Summe etwas kleiner. Aber nicht viel:

Übungsaufgabe 2.2.2 Sei $n = 2^{d}$ . Berechnen Sie $\begin{array}{r} \sum_{b = 1}^{n - 1} | b |_{1}, \end{array}$ also die Gesamtzahl der Einsen in den Binärdarstellungen aller Zahlen $1 \leq b \leq n - 1$ .

Fundamental besser wird unsere Konstruktion, wenn wir betrachten, dass wir zum Beispiel $g p_{I}$ und $g p_{I^{'}}$ nicht separat berechnen müssen, sondern den Outputwert $g p_{I^{'}}$ in der Berechnung von $g p_{I}$ wiederverwenden können. Anders gesagt: jedes $g p$ -Gate in PI, mit dem wir $g p_{I^{'}}$ und $g p_{K}$ zu $g p_{I}$ kombinieren, ist gleichzeitig ein Output-Gate, nämlich für das Präfixinterval $I$ . Unser Schaltkreis hat $n$ Output-Gates $g p_{[0, b)}$ . Für $b = 1, 2, 4, 8, \dots, 2^{d}$ können wir einfach das Input-Gate durchschalten, brauchen also nur $n - d - 1$ zusätzliche Output-Gates. Jedes $g p$ -Gate in PI entspricht so einem zusätzlichen Output-Gate, und somit hat PI insgesamt $n - d - 1$ viele $g p$ -Gates. Der Einfachheit halber: höchstens $n$ . Für $n = 16$ schaut das so aus:

Beobachtung 2.2.6 Der Schaltkreis PI hat Tiefe $2 (d - 1)$ und besteht aus höchstens $n$ vielen $g p$ -Gates, also maximal $4 n$ Gates.

Wir komibnieren nun BI und PI und erhalten somit einen Schaltkreis der Tiefe $1 + 2 d + 2 (d - 1) = 4 d - 1$ und Größe $6 n - 4 + 4 n = 10 n - 4$ , der alle $g p_{[0, b]}$ berechnet. Wir haben nun also alle $c_{1}, c_{2}, \dots, c_{n}$ und können in einem finalen Schritt

\begin{array}{r} s_{i} = x_{i} \oplus y_{i} \oplus c_{i} \end{array}

berechnen. Hierfür berechnen wir erst $x \oplus y$ :

was vier Gates braucht, aber nur zwei neue, weil wir $x_{i} \land y_{i} = g_{[i, i]}$ und $x_{i} \lor y_{i} = p_{[i, i]}$ bereits berechnet haben. Nun berechnen wir $s_{i}$ als $(x_{i} \oplus y_{i}) \oplus c_{i}$ :

was vier weitere Gates braucht. Pro $s_{i}$ brauchen wir also sechs weitere Gates. Der gesamte Schaltkreis hat somit $16 n - 4$ Gates. Was ist seine Tiefe? Der längste Pfad von $s_{i}$ zurück zu einem Input geht durch $c_{i}$ und hat Tiefe 2 plus die Tiefe von $c_{i}$ , welche, wie oben beobachtet, $4 d - 1$ ist.

Theorem 2.2.7 Sei $n = 2^{d}$ . Der gerade konstrukierte Schaltkreis für die Addition zweier $n$ -Bit-Binärzahlen hat Tiefe $4 \log (n) + 1$ und Größe $16 n - 4$ .