Arithmetik

Das Carry-Lookahead-Verfahren ist ein paralleles Verfahren zur Berechnung der Summe von zwei n-Bit-Binärzahlen in Zeit O(log(n)).

Problem

Gegeben sind zwei n-Bit-Zahlen a und b. Die Summe s = a + b wird nach folgendem Schema berechnet, wobei die c_i die entstehenden Übertrags­bits sind (Bild 1):

Bei der Addition ist c₀ = 0; bei der Subtraktion werden die b_i invertiert und es ist c₀ = 1. Die Operation ⊕ ist das logische Exklusiv-Oder (Xor). Im Folgenden werden ferner das Symbol · für das logische Und sowie das Symbol + für das logische Oder verwendet.

Die normale Schulmethode berechnet die Übertrags­bits nacheinander von rechts nach links. Dabei kann es vorkommen, dass ein Übertrag von ganz rechts bis nach ganz links durchklappert. Dies ist z.B. bei der Addition von 00...01 und 11...11 der Fall. Daher benötigt das Verfahren im schlechtesten Fall Θ(n) Zeit. Von dem Durch­klappern der Übertrags­bits leitet sich der Name des Verfahrens ab: Ripple-Carry-Addierer.

Es stellt sich die Frage, ob sich die Addition durch Parallel­verarbeitung schneller als in Zeit Θ(n) durchführen lässt. Die Summenbits s_i können alle parallel berechnet werden, wenn die Übertrags­bits c_i bekannt sind:

s_i = a_i ⊕ b_i ⊕ c_i.

Die Schwierig­keit liegt also in der Berechnung der Übertrags­bits. Jedes Übertragsbit c_i hängt von allen a_j und b_j mit j < i ab. Am schwierigsten zu berechnen ist offenbar das Übertragsbit c_n, da es von allen Stellen der Zahlen a und b abhängt.

Idee

Beim Carry-Lookahead-Verfahren wird die in den Stellen 0, ..., n-1 enthaltene Information, die zum Wert von c_n beiträgt, über einen voll­ständigen binären Baum in O(log(n)) Schritten zusammen­gefasst. Die benötigte Information ist die folgende:

Entsteht irgendwo innerhalb der Stellen 0, ..., n-1 ein Übertrag c_k+1 (dadurch, dass a_k · b_k = 1 ist) und klappert dieser Übertrag nach links bis an Position n durch (dadurch dass an allen Positionen i mit k < i < n gilt:  a_i + b_i = 1)?¹) Dann bedeutet dies, dass die Stellen 0, ..., n-1 einen Übertrag generieren:

g(0, n-1) = 1.

Oder ist c₀ = 1 und klappert es bis an Position n durch (dadurch dass an allen Positionen i mit 0 ≤ i < n gilt:  a_i + b_i = 1)? Dann bedeutet dies, dass die Stellen 0, ..., n-1 einen Übertrag propagieren:

p(0, n-1) = 1.

Das folgende Bild 2 zeigt das Additions­schema ohne Summenbits sowie andeutungs­weise die beiden eben geschilderten Möglich­keiten:

Bild 2: (a) Additionsschema, (b) Generieren eines Übertrags, (c) Propagieren des Übertrags c₀

Durch Verwendung der Funktionen g und p ergibt sich also

c_n  =  g(0, n-1)  +  c₀ · p(0, n-1),

d.h. das Übertragsbit c_n ist gleich 1, wenn die Stellen 0, ..., n-1 einen Übertrag generieren oder wenn c₀ gleich 1 ist und die Stellen 0, ..., n-1 den Übertrag propagieren.

Diese an sich triviale Tatsache bekommt dadurch ihre Bedeutung, dass sich die Funktionen g und p rekursiv in O(log(n)) Schritten berechnen lassen.

Berechnung der Funktionen g und p

Es gilt für alle i ≤ k < j:

p(i, j)  =  p(i, k) · p(k+1, j)   und

g(i, j)  =  g(k+1, j) + g(i, k) · p(k+1, j).

Für i = j gilt:

p(i, i)  =  a_i + b_i   und

g(i, i)  =  a_i · b_i.

In Bild 3 ist das Zustande­kommen von p(i, j) sowie von g(i, j) schematisch dargestellt. Die Stellen von i bis j propagieren einen Übertrag, wenn zunächst die Stellen von i bis k den Übertrag propagieren und dann die Stellen von k+1 bis j den Übertrag weiter­propagieren (Bild 3 a). Die Stellen von i bis j generieren einen Übertrag, wenn die Stellen von k+1 bis j einen Übertrag generieren (Bild 3 b) oder wenn die Stellen von i bis k einen Übertrag generieren und die Stellen von k+1 bis j den Übertrag propagieren (Bild 3 c).

Bild 3: Berechnung von  p(i, j) = p(i, k) · p(k+1, j),   g(k+1, j)  und  g(i, k) · p(k+1, j)

Die Werte g(0, n-1) und p(0, n-1) lassen sich nach dem Divide-and-Conquer-Prinzip effizient berechnen. Das Problem wird in zwei Hälften geteilt und die Teilprobleme parallel nach derselben Methode gelöst. Beispiels­weise wird g(0, n-1) wie folgt berechnet (im Folgenden sei der Einfachheit halber voraus­gesetzt, dass n eine Zweierpotenz ist):

g(0, n-1)  =  g(n/2, n-1)  +  g(0, n/2-1) · p(n/2, n-1).

Die Teilprobleme g(n/2, n-1), g(0, n/2-1) und p(n/2, n-1) werden wiederum in kleinere Teilprobleme aufgespalten usw., bis sich schließlich Teilprobleme der Länge 1 ergeben, die direkt aus a und b berechnet werden können. Das folgende Bild 4 zeigt den Daten­fluss­graphen für n = 8.

Bild 4: Datenfluss bei der Berechnung von g(0,7) und p(0,7)

Berechnung aller Übertrags­bits

Bisher ist lediglich

c_n  =  g(0, n-1)  +  c₀ · p(0, n-1)

berechnet worden. Auf ähnliche Weise lassen sich auch die anderen Übertrags­bits berechnen, und zwar in O(log(n)) Schritten unter Verwendung der bereits berechneten g- und p-Werte sowie bereits berechneter Übertrags­bits (indem der Baum aus Bild 4 in noch einmal umgekehrter Richtung durchlaufen wird).

Es gilt nämlich für beliebige i, k ∈ {1, ..., n} mit i < k:

c_k  =  g(i, k-1)  +  c_i · p(i, k-1),

d.h. ein Übertragsbit c_k ist gleich 1, wenn es von den Stellen i, ..., k-1 generiert wird oder wenn c_i gleich 1 ist und es von den Stellen i, ..., k-1 propagiert wird.

Dies wird benutzt, um z.B. c₆ mithilfe von c₄ zu berechnen:

c₆  =  g(4, 5)  +  c₄ · p(4, 5).

Bild 5 zeigt die entsprechende Erweiterung von Bild 4 zur Berechnung der Übertrags­bits und der Summenbits.

Bild 5: Datenfluss des Carry-Lookahead-Addierers

Schaltbild

Der Daten­fluss­graph des Carry-Lookahead-Addierers lässt sich direkt in eine Schaltung umsetzen; diese besteht aus folgenden Bausteinen , die farblich wie die entsprechenden Knoten des Daten­fluss­graphen gekenn­zeichnet sind (Bild 6). ²)

Analyse

Die Schaltzeiten für die einzelnen Bausteine sind die folgenden:

Der violette Baum hat die Tiefe log(n), der grüne Baum ebenfalls log(n). Der längste Datenpfad führt offenbar zu c_n-1; er durchläuft den violetten Baum nur bis zur vorletzten Stufe. Damit beträgt die Schaltzeit des Carry-Lookahead-Addierers

T(n)   =   1 + 2·(log(n)-1) + 2·log(n) + 3   =   4·log(n) + 2.

Algorithmus

Die folgende Funktion simuliert den Carry-Lookahead-Addierer. Die Funktion addiert zwei n-Bit-Binärzahlen, deren Bits in den Arrays a und b stehen, und liefert die Summe im Array s. Die einzelnen Bits werden mit den Operationen | (Oder), & (Und) sowie ^ (Xor) verknüpft. In diesem Programm braucht n keine Zweierpotenz zu sein.

Literatur

[CLRS 01]   T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)

[HP 96]   J.L. Hennessy, D.A. Patterson: Computer Architecture -- a Quantitative Approach. 2. Auflage, Morgan Kaufmann (1996)

[Lan 12]   H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Den Carry-Lookahead-Addierer finden Sie auch in meinem Buch über Algorithmen.
Weitere Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, algorithmische Geometrie, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]