Zahlen, bitte! Verrückt: Für ×3 brauchte der Pentium einen eigenen Schaltkreis

Inhaltsverzeichnis

close notice

This article is also available in English. It was translated with technical assistance and editorially reviewed before publication.

Don’t show this again.

Der folgende Text ist erster Teil eines ins Deutsche übertragendes Exponats, das IT-Historiker Ken Shirriff ursprünglich in seinem Blog veröffentlicht hat. Der zweite Teil samt Schlussfolgerung ist separat verfügbar. Der Verlag dankt Ken Shirriff herzlich für die freundliche Genehmigung.

1993 brachte Intel den Hochleistungsprozessor Pentium auf den Markt, der den Beginn der langlebigen Pentium-Reihe markierte. Ken Shirriff hat die Schaltkreise des Pentium im Detail untersucht und ist dabei auf einen Schaltkreis gestoßen, der mit 3 multipliziert, und sonst nichts. Es ist ein komplexer Schaltkreis mit Tausenden von Transistoren. Warum hat der Pentium einen Schaltkreis, der speziell mit 3 multipliziert? Warum ist er so kompliziert? Shirriff beschreibt diesen Multiplikator, den er als ×3-Schaltkreis bezeichnet, und erklärt seinen Zweck und seine Funktionsweise.

Der separate x3-Schaltkreis des Intel Pentium ist ein Teil dessen Gleitkomma-Multiplikatorschaltung. Insbesondere multipliziert der Pentium zwei 64-Bit-Zahlen mittels Oktal-Multiplikation, die schneller ist als binäre Multiplikation¹. Die Multiplikation mit 3 muss als Sonderfall behandelt werden. Da der Rest des Multiplikationsprozesses erst beginnen kann, wenn die Multiplikation mit 3 abgeschlossen ist, muss dieser Schaltkreis außerdem sehr schnell sein. Wenn Sie sich mit digitalem Design auskennen, haben Sie vielleicht schon von Techniken wie Carry-Lookahead, Kogge-Stone-Addition und Carry-Select-Addition gehört. Ich werde erklären, wie der ×3-Schaltkreis all diese Methoden kombiniert, um ihre Leistung zu maximieren.

Zahlen, bitte!

In dieser Rubrik stellen wir immer dienstags verblüffende, beeindruckende, informative und witzige Zahlen aus den Bereichen IT, Wissenschaft, Kunst, Wirtschaft, Politik und natürlich der Mathematik vor.

• Alle Artikel zu "Zahlen, bitte!"

Das Foto unten zeigt den daumennagelgroßen Siliziumchip des Pentium unter einem Mikroskop. Ich habe die wichtigsten Funktionsblöcke beschriftet. In der Mitte befindet sich die Integer-Ausführungseinheit, die die meisten Anweisungen ausführt. Links verbessern der Code- und der Daten-Cache die Speicherleistung. Die Gleitkommaeinheit unten rechts führt Gleitkommaoperationen aus. Fast die Hälfte der Gleitkommaeinheit wird vom Multiplikator belegt, der eine Reihe von Addierer verwendet, um zwei 64-Bit-Zahlen schnell zu multiplizieren. Der Schwerpunkt dieses Artikels liegt auf dem ×3-Schaltkreis, der in der Nähe des oberen Endes des Multiplikators gelb hervorgehoben ist ("x3 circuit"). Wie Sie sehen können, nimmt der ×3-Schaltkreis einen nicht unerheblichen Teil des Pentium-Chips ein, insbesondere wenn man bedenkt, dass seine Aufgabe einfach zu sein scheint.

Warum verwendet der Pentium das Oktalsystem, um zu multiplizieren?

Die Multiplikation zweier Zahlen im Binärsystem ist konzeptionell einfach. Man kann sich die binäre Multiplikation ähnlich, wie das lange Einmaleins vorstellen, nur dass statt Dezimalzahlen Binärzahlen verwendet werden. Das folgende Beispiel zeigt, wie 5×6 im Binärsystem berechnet wird: Die drei Terme werden addiert, um das Ergebnis zu erhalten. Praktischerweise ist jeder Term entweder der Multiplikand (in diesem Fall 101) oder 0, entsprechend verschoben, sodass die Berechnung der Terme einfach ist.

     101
    ×110
     ―――
     000    i.e. 0×101
    101     i.e. 1×101
  +101      i.e. 1×101
   ―――――
   11110

Leider ist dieser einfache Multiplikationsansatz langsam. Bei den oben genannten 3-Bit-Zahlen müssen drei Terme addiert werden. Wenn Sie jedoch zwei 64-Bit-Zahlen multiplizieren, müssen Sie 64 Terme addieren, was viel Zeit und/oder Schaltkreise erfordert.

Der Pentium verwendet einen komplizierteren Ansatz, indem er die Multiplikation im Oktalsystem berechnet. Die Idee besteht darin, den Multiplikator in Gruppen von drei Bits zu betrachten, sodass man nicht bei jedem Schritt mit 0 oder 1 multipliziert, sondern mit einer Zahl von 0 bis 7. Jeder Term, der addiert wird, ist immer noch binär, aber die Anzahl der Terme wird um den Faktor drei reduziert. Anstatt also 64 Terme zu addieren, addieren Sie 22 Terme, was eine erhebliche Reduktion der erforderlichen Schaltkreise ermöglicht. (Ich werde die vollständigen Details des Pentium-Multiplikators in einem zukünftigen Artikel beschreiben.²)

Warum x3 für den Chip so schwierig ist

Der Nachteil der Oktal-Multiplikation besteht darin, dass die Multiplikation mit einer Zahl von 0 bis 7 viel komplizierter ist als die Multiplikation mit 0 oder 1, die fast trivial ist. Glücklicherweise gibt es einige Abkürzungen. Beachten Sie, dass die Multiplikation mit 2 dasselbe ist wie das Verschieben der Zahl um eine Bitposition nach links, was in der Hardware sehr einfach ist: Sie verdrahten jedes Bit um eine Position nach links. Um mit 4 zu multiplizieren, verschieben Sie den Multiplikanden um zwei Bitpositionen nach links.

Die Multiplikation mit 7 scheint umständlich zu sein, aber es gibt einen Trick, der als Booth-Algorithmus bekannt ist. Anstatt mit 7 zu multiplizieren, addiert man das Achtfache der Zahl und subtrahiert die Ausgangszahl selbst, wodurch man das siebenfache dieser Zahl erhält. Man könnte meinen, dass dies zwei Schritte erfordert, doch der Trick besteht darin, mit einer weiteren Ziffer in der (Oktal)-Ziffer links zu multiplizieren, sodass man den Faktor 8 ohne zusätzlichen Schritt erhält. (Eine Analogie zum Dezimalsystem ist, dass man, wenn man mit 19 multiplizieren möchte, mit 20 multiplizieren und den Multiplikanden subtrahieren kann.) So kann man durch Subtrahieren das ×7 erhalten. Ebenso kann man für ×6 einfach ×2 subtrahieren und in der nächsten Ziffer ×8 addieren. Das einzige schwierige Vielfache ist also ×3. (Und was ist mit ×5? Wenn Sie ×3 berechnen können, können Sie das von ×8 subtrahieren, um ×5 zu erhalten.)

Zusammenfassend lässt sich sagen, dass der Oktal-Booth-Algorithmus des Pentium eine schnelle Methode zum Multiplizieren ist, aber eine spezielle Schaltung erfordert, um das ×3-Vielfache des Multiplikanden zu erzeugen.

Implementierung einer schnellen ×3-Schaltung mit Carry-Lookahead

Das Multiplizieren einer Zahl mit 3 ist in binärer Darstellung einfach: Die Zahl wird mit sich selbst addiert, wobei sie um eine Position nach links verschoben wird. (Wie oben erwähnt, entspricht das Verschieben nach links einer Multiplikation mit 2 und ist in der Hardware einfach zu bewerkstelligen.) Leider ist die Verwendung eines einfachen Addierers zu langsam.

Das Problem bei der Addition ist, dass der Übertrag die Addition verlangsamt. Versuchen Sie einmal, 99999+1 von Hand zu berechnen. Sie beginnen mit 9+1=10, übertragen dann die Eins, erzeugen einen weiteren Übertrag, der einen weiteren Übertrag erzeugt, und so weiter, bis Sie alle Ziffern durchgegangen sind. Bei der Computeraddition gibt es dasselbe Problem: Wenn Sie zwei Zahlen addieren, können die Bits niedriger Ordnung einen Übertrag erzeugen, der sich dann auf alle Bits ausbreitet. Ein Addierer, der auf diese Weise arbeitet – ein sogenannter Ripple-Carry-Addierer – ist langsam, da der Übertrag durch alle Bits wandern muss. Daher verwenden CPUs spezielle Schaltkreise, um Additionen zu beschleunigen.

Eine Lösung ist der Carry-Lookahead-Addierer. In diesem Addierer werden alle Übertrag-Bits parallel berechnet, bevor die Summen berechnet werden. Anschließend können die Summen-Bits unter Verwendung der Übertrag-Bits parallel berechnet werden. Dadurch kann die Addition schnell abgeschlossen werden, ohne dass abgewartet werden muss, bis die Überträge die gesamte Summe durchlaufen haben.

Es mag unmöglich erscheinen, die Überträge zu berechnen, ohne zuerst die Summe zu berechnen, aber es gibt eine Möglichkeit, dies zu tun. Für jede Bitposition werden Signale bestimmt, die als carry generate ("Übertrag erzeugen") und carry propagate ("Übertrag verbreiten") bezeichnet werden. Diese Signale können dann verwendet werden, um alle Überträge parallel zu bestimmen. Das Signal generate zeigt an, dass die Position einen Übertrag generiert. Wenn Sie etwa die Binärzahlen 1xx und 1xx (wobei x ein beliebiges Bit ist) addieren, wird unabhängig von den nicht spezifizierten Bits ein Übertrag vom obersten Bit generiert. Wenn Sie hingegen 0xx und 0xx addieren, wird nie ein Übertrag generiert. Das Signal generate wird also für den ersten Fall erzeugt, nicht jedoch für den zweiten.

Aber was ist mit 1xx plus 0xx? Wir könnten einen Übertrag erhalten, zum Beispiel 111+001, aber auch nicht, beispielsweise 101+001. In diesem Vielleicht-Fall setzen wir das Signal carry propagate, das anzeigt, dass ein Übertrag in die Position aus der Position heraus übertragen wird. Wenn es beispielsweise einen Übertrag aus der mittleren Position gibt, hat 1xx+0xx einen Übertrag vom obersten Bit. Wenn es jedoch keinen Übertrag aus der mittleren Position gibt, gibt es auch keinen Übertrag vom obersten Bit. Mit anderen Worten: Das Signal propagate zeigt an, dass ein Übertrag in das oberste Bit aus dem obersten Bit heraus übertragen wird.

Zusammenfassend lässt sich sagen, dass die Addition von 1+1 einen Übertrag erzeugt. Die Addition von 0+1 oder 1+0 führt zur Weiterverbreitung eines Übertrags. Somit wird das Signal generate an jeder Position durch G_n = A_n·B_n gebildet, wobei A und B die Eingaben sind. Das Signal propagate ist P_n = A_n+B_n, das logische ODER der Eingaben.³

Nachdem nun die Signale propagate und generate definiert sind, kann eine moderat komplexe Logik⁴ den Übertrag C_n in jede Bitposition berechnen. Wichtig ist, dass alle Übertragbits parallel berechnet werden können, ohne darauf zu warten, dass der Übertrag durch jede Bitposition wandert. Sobald jeder Übertrag berechnet ist, können die Summenbits parallel berechnet werden: S_n = A_n ⊕ B_n ⊕ C_n. Mit anderen Worten werden die beiden Eingangsbits und der berechnete Übertrag mit Exklusiv-ODER (XOR) verknüpft. Somit kann die gesamte Summe durch Übertragsvorgriffe parallel berechnet werden. Leider gibt es Schwierigkeiten.

Implementierung von Übertragsvorgriff mit einem parallelen Präfixaddierer

Die Übertrag-Bits können direkt aus den G- und P-Signalen generiert werden. Allerdings erfordert der direkte Ansatz zu viel Hardware, wenn die Anzahl der Bits zunimmt. Darüber hinaus benötigt dieser Ansatz Gatter mit vielen Eingängen, die aus elektrischen Gründen langsam sind. Daher verwendet der Pentium zwei Techniken, um die Hardwareanforderungen für Carry-Lookahead (Übertragsvorschau) überschaubar zu halten. Erstens wird ein "Parallel-Präfix-Addierer"-Algorithmus für die Carry-Lookahead-Funktion über 8-Bit-Blöcke verwendet.⁷ Zweitens wird ein zweistufiger hierarchischer Ansatz für die Carry-Lookahead-Funktion verwendet: Die obere Carry-Lookahead-Schaltung verarbeitet acht 8-Bit-Blöcke unter Verwendung desselben 8-Bit-Algorithmus.⁵

Das Foto unten zeigt den vollständigen ×3-Schaltkreis. Sie können sehen, dass er in Blöcke zu 8 Bit unterteilt ist. (Obwohl ich dies als 64-Bit-Schaltkreis bezeichne, erzeugt er tatsächlich eine 69-Bit-Ausgabe: Es gibt fünf "zusätzliche" Bits auf der linken Seite, um Überlauf zu vermeiden und zusätzliche Bits für Rundungen bereitzustellen.)

Die Idee des Parallel-Präfix-Addierers besteht darin, die Signale über Bitbereiche hinweg zu verbreiten (propagate) und zu erzeugen (generate), nicht nur über einzelne Bits wie bisher. So zeigt beispielsweise das Verbreitungssignal P₃₂ an, dass ein Übertrag in Bit 2 aus Bit 3 heraus verbreitet würde (dies würde beispielsweise bei 10xx+01xx passieren). Und G₃₀ zeigt an, dass die Bits 3 bis 0 einen Übertrag aus Bit 3 erzeugen. (Dies würde beispielsweise bei 1011+0111 passieren).

Mit einigen mathematischen Tricks können⁶ Sie die P- und G-Werte für zwei kleinere Bereiche nehmen und sie zu den P- und G-Werten für den kombinierten Bereich zusammenführen. Sie können beispielsweise mit den P- und G-Werten für die Bits 0 und 1 beginnen und P₁₀ und G₁₀ erzeugen, die Signale propagate generate, die zwei Bits beschreiben. Diese könnten mit P₃₂ und G₃₂ zusammengeführt werden, um P₃₀ und G₃₀ zu erzeugen, die angeben, ob ein Übertrag über die Bits 3-0 weitergegeben oder von den Bits 3-0 erzeugt wird. Beachten Sie, dass G_n0 angibt, ob ein Übertrag von allen niedrigeren Bits in Bit n+1 erzeugt wird, was der C_n+1-Übertragungswert ist, den wir zur Berechnung der Endsumme benötigen. Dieser Zusammenführungsprozess ist effizienter als die Brute-Force-Implementierung der Carry-Lookahead-Logik, da logische Teilausdrücke wiederverwendet werden können.

Es gibt viele verschiedene Möglichkeiten, die P- und G-Terme zu kombinieren, um die gesuchten Terme zu erzeugen.⁸ Der Pentium verwendet einen Ansatz namens Kogge-Clone, der versucht, die Gesamtverzögerung zu minimieren und gleichzeitig die Anzahl der Schaltkreise in einem angemessenen Rahmen zu halten. Das folgende Diagramm ist das Standarddiagramm, das die Funktionsweise eines Kogge-Stone-Addierers veranschaulicht. Es ist ziemlich abstrakt, aber ich werde versuchen, es zu erklären. Das Diagramm zeigt, wie die P- und G-Signale zusammengeführt werden, um die einzelnen Ausgaben unten zu erzeugen. Jedes Quadrat oben erzeugt die P- und G-Signale für dieses Bit. Jede Linie entspricht sowohl dem P- als auch dem G-Signal. Jede Raute kombiniert zwei Bereiche von P- und G-Signalen, um neue P- und G-Signale für den kombinierten Bereich zu erzeugen. So decken die Signale nach unten hin immer größere Bitbereiche ab und enden mit den G_n0-Ausgängen, die Übertragungen anzeigen.

Ich habe einige der Zwischensignale beschriftet, damit Sie sich ein Bild davon machen können, wie es funktioniert. Schaltung A kombiniert P₇ und G₇ mit P₆ und G₆, um die Signale zu erzeugen, die zwei Bits beschreiben: P₇₆ und G₇₆. In ähnlicher Weise kombiniert Schaltung B P₇₆ und G₇₆ mit P₅₄ und G₅₄, um die Signale zu erzeugen, die vier Bits beschreiben: P₇₄ und G₇₄. Schließlich erzeugt Schaltung C die endgültigen Ausgaben für Bit 7: P₇₀ und G₇₀. Beachten Sie, dass die meisten Zwischenergebnisse zweimal verwendet werden, was die Anzahl der Schaltkreise reduziert. Darüber hinaus gibt es höchstens drei Ebenen von Kombinationsschaltungen, wodurch die Verzögerung im Vergleich zu einem tieferen Netzwerk reduziert wird.

Der entscheidende Punkt ist, dass die P- und G-Werte parallel berechnet werden, sodass die Übertrag-Bits alle parallel berechnet werden können, ohne darauf warten zu müssen, dass der Übertrag durch alle Bits wandert. (Wenn diese Erklärung keinen Sinn ergibt, finden Sie in meiner Diskussion des Kogge-Stone-Addierers in der Pentium-Divisions-Schaltung eine andere – aber vielleicht immer noch verwirrende – Erklärung.)

Rekursive Kogge-Stone-Lookahead

Der Kogge-Stone-Ansatz kann auf 64 Bit erweitert werden, aber die Menge an Schaltkreisen und Verdrahtung wird überwältigend. Stattdessen verwendet der Pentium einen rekursiven, hierarchischen Ansatz mit zwei Ebenen Kogge-Stone-Lookahead (Vorschau). Die untere Schicht verwendet acht Kogge-Stone-Addierer wie oben beschrieben und unterstützt insgesamt 64 Bit.

Die obere Schicht verwendet eine einzelne 8-Bit-Kogge-Stone-Lookahead-Schaltung, die jeden der unteren Blöcke als einzelnes Bit behandelt. Das heißt, ein unterer Block hat ein propagete-Signal P, das anzeigt, dass ein Übertrag in den Block hinein übertragen wird, sowie ein generate-Signal G, das anzeigt, dass der Block einen Übertrag generiert. Die obere Kogge-Stone-Schaltung kombiniert diese Signale, um zu bestimmen, ob Überträge von Gruppen von Blöcken generiert oder übertragen werden.⁹

Zusammenfassend lässt sich sagen, dass jede der acht unteren Lookahead-Schaltungen die Übertragssignale innerhalb eines 8-Bit-Blocks berechnet. Die obere Lookahead-Schaltung berechnet die Übertragssignale in und aus jedem 8-Bit-Block. In Kombination liefern die Schaltungen schnell alle Übertragssignale, die zur Berechnung der 64-Bit-Summe notwendig sind.

Der Carry-Select-Addierer

Nehmen wir an, Sie nehmen an einer Spielshow teil: "Was ist 553 + 246 + c? In zehn Sekunden sage ich Ihnen, ob c 0 oder 1 ist, und wer zuerst die Antwort gibt, gewinnt 1.000 Euro." Natürlich sollten Sie nicht einfach herumsitzen, bis Sie c erhalten. Sie sollten die beiden Summen jetzt ausführen, damit Sie den Buzzer drücken können, sobald c bekannt gegeben wird. Dies ist das Konzept hinter dem Carry-Select-Addierer: Es werden zwei Additionen durchgeführt – mit Übertrag und ohne – und dann wird die richtige Antwort geliefert, sobald der Übertrag verfügbar ist. Der Carry-Select-Addierer erfordert zusätzliche Hardware – zwei Addierer zusammen mit einem Multiplexer zur Auswahl des Ergebnisses –, aber er überlappt die Zeit für die Berechnung der Summe mit der Zeit für die Berechnung des Übertrags. Letztlich werden die Additions- und Übertrag-Lookahead-Operationen parallel ausgeführt, und der Multiplexer kombiniert die Ergebnisse aus beiden.

Der Pentium verwendet einen Carry-Select-Addierer für jeden 8-Bit-Block in der ×3-Schaltung. Der Übertrag aus dem Übertrag-Lookahead der zweiten Ebene wählt aus, welche Summe für den Block erzeugt werden soll. Somit überschneidet sich die Zeit für die Berechnung des Übertrags mit der Zeit für die Berechnung der Summe.

Weiter geht’s mit Teil 2 unseres Zahlen, bitte! rund um den wunderlichen x3-Pentium-Schaltkreis in einer Woche an gleicher Stelle.

Der Pentium-Teppich

Anlässlich eines Besuches in der National Gallery of Art in Washington, DC, kam Ken Shirriff der Pentium Navajo Teppich (offiziell "Replica of a Chip") unter. Das von Marilou Schultz gewebte Kunstwerk hat Shirriff dazu inspiriert, den Pentium-Prozessor genauer zu untersuchen. Er plant noch weitere Artikel zu diesem Meilenstein der CPU-Geschichte. Updates zu seinen Veröffentlichungen gibt es zB bei Mastodon unter @kenshirriff sowie in seinem RSS-Feed.

Fußnoten und Quellenangaben

1. Eine Gleitkomma-Multiplikation auf dem Pentium dauert drei Taktzyklen, von denen die Multiplikationsschaltung zwei Zyklen lang beschäftigt ist (siehe Agner Fogs Optimierungshandbuch). Im Vergleich dazu ist die Ganzzahlmultiplikation (MUL) viel langsamer und dauert elf Zyklen. Die Nehalem-Mikroarchitektur des Jahres 2008 hat die Gleitkomma-Multiplikationszeit auf einen Zyklus reduziert.
2. Ich gebe einen kurzen Überblick über den Gleitkomma-Multiplikator des Pentium als Vorschau: Der Multiplikator besteht aus einem Baum zehner Carry-Save-Addierern, die die Terme summieren. Jeder Carry-Save-Addierer ist ein 4:2-Kompressionsaddierer, der vier Eingangsbits nimmt und zwei Ausgangsbits erzeugt. Das Ausgangssignal des Carry-Save-Addierers wird von einem Addierer unter Verwendung von Kogge-Stone-Lookahead und Carry-Select in das Endergebnis umgewandelt. Die Multiplikation zweier 64-Bit-Zahlen ergibt 128 Bit, aber der Pentium erzeugt ein 64-Bit-Ergebnis. (Tatsächlich gibt es noch ein paar Bits mehr für die Rundung.) Die unteren 64 Bits können nicht einfach verworfen werden, da sie einen Übertrag in die erhaltenen Bits erzeugen könnten. Daher werden die unteren 64 Bit in eine weitere Kogge-Stone-Lookahead-Schaltung eingespeist, die keine Summe erzeugt, sondern anzeigt, ob ein Übertrag vorliegt. Da der Datenpfad 64 Bit breit ist, das Produkt jedoch 128 Bit umfasst, gibt es viele Schiebestufen, um die Bit in die rechte Spalte zu verschieben. Darüber hinaus sind die Addierer etwas breiter als 64 Bit, da sie die Zwischensummen aufnehmen müssen.
3. Die Bits 1+1 werden generiert, aber sollte auch propagiert gesetzt werden? Für die Gleichungen macht es keinen Unterschied. Dieser Addierer setzt propagieren für 1+1, einige andere Addierer jedoch nicht. Die Antwort hängt davon ab, ob Sie ein Inklusiv-Oder- oder Exklusiv-Oder-Gatter verwenden, um das propagierte Signal zu erzeugen.
4. Der Übertrag C_n an jeder Bitposition n kann aus den Signalen G und P berechnet werden, indem die verschiedenen Fälle berücksichtigt werden:
   C₁ = G₀: Ein Übertrag in Bit 1 tritt auf, wenn ein Übertrag von Bit 0 erzeugt wird.
   C₂ = G₁ + G₀P₁: Ein Übertrag in Bit 2 tritt auf, wenn Bit 1 einen Übertrag generiert oder Bit 1 einen Übertrag von Bit 0 weitergibt.
   C₃ = G₂ + G₁P₂ + G₀P₁P₂: Ein Übertrag in Bit 3 tritt auf, wenn Bit 2 einen Übertrag generiert oder Bit 2 einen von Bit 1 generierten Übertrag weitergibt oder die Bits 2 und 1 einen von Bit 0 generierten Übertrag weitergeben.
   C₄ = G₃ + G₂P₃ + G₁P₂P₃ + G₀P1P2P3: Ein Übertrag in Bit 4 tritt auf, wenn ein Übertrag von Bit 3, 2, 1 oder 0 zusammen mit den erforderlichen Übertragungssignalen erzeugt wird.
   Und so weiter ...
   Beachten Sie, dass die Formel für jede Bitposition komplizierter wird. Die Komplexität der Schaltung beträgt ungefähr O(N³), je nachdem, wie man sie misst. Daher wird die direkte Implementierung der Carry-Lookahead-Formel mit zunehmender Bitanzahl unpraktisch. Der Kogge-Stone-Ansatz verwendet ungefähr O(N log N) Transistoren, aber die Verdrahtung wird für große N zu umfangreich, da es N/2 Drähte mit einer Länge von N/2 gibt. Durch die Verwendung eines Baumes aus Kogge-Stone-Schaltungen wird der Verdrahtungsaufwand reduziert.
5. Die 8-Bit-Blöcke in der Schaltung haben nichts mit Bytes zu tun. Der Grund dafür ist, dass acht Bit eine vernünftige Größe für einen Block sind und eine schöne Aufteilung in acht Blöcke zu je acht Bit ermöglichen. Andere Systeme haben 4-Bit-Blöcke für die Carry-Lookahead-Funktion verwendet (zum Beispiel Minicomputer, die auf der Arithmetisch-logischen Einheit 74181 von Texas Instruments basieren).
6. Ich werde nicht näher auf die Mathematik des Zusammenführens von P- und G-Signalen eingehen; siehe zum Beispiel Addierschaltungen oder Carry-Lookahead-Addierer für weitere Details. Wichtig ist, dass der Übertrag-Zusammenführungsoperator assoziativ ist (eigentlich ein Monoid), sodass die Teilbereiche in beliebiger Reihenfolge zusammengeführt werden können. Diese Flexibilität ermöglicht verschiedene Algorithmen mit unterschiedlichen Kompromissen.
7. Die Idee hinter einem Präfixaddierer ist, dass wir sehen wollen, ob es einen Übertrag von Bit 0, Bits 0-1, Bits 0-2, Bits 0-3, 0-4 und so weiter gibt. Dies sind alle Präfixe des Wortes. Da die Präfixe parallel berechnet werden, spricht man von einem parallelen Präfixaddierer.
8. Der Lookahead-Merging-Prozess kann auf verschiedene Weisen implementiert werden, darunter Kogge-Stone, Brent-Kung und Ladner-Fischer, mit unterschiedlichen Kompromissen. Das folgende Diagramm zeigt beispielsweise, dass Brent-Kung weniger "Diamanten", aber mehr Schichten verwendet. Ein Brent-Kung-Addierer verwendet also weniger Schaltkreise, ist aber langsamer. (Sie können jeden Ausgang nach oben verfolgen, um zu überprüfen, ob der Baum die richtigen Eingänge erreicht.)

9. Die übergeordnete Kogge-Stone-Lookahead-Schaltung verwendet die acht P₇₀– und G₇₀–Signale von den acht untergeordneten Lookahead-Schaltungen. Beachten Sie, dass P₇₀ und G₇₀ anzeigen, dass ein 8-Bit-Block einen Übertrag weitergibt oder erzeugt. Die übergeordnete Lookahead-Schaltung behandelt 8-Bit-Blöcke als eine Einheit, während die untergeordnete Lookahead-Schaltung 1-Bit-Blöcke als Einheit behandelt. Somit sind die über- und untergeordneten Lookahead-Schaltungen im Wesentlichen identisch und wirken auf 8-Bit-Werte.

(ds)