Es gibt viele Details über Carry-Lookahead-Addierer wie Kogge-Stone, Lander-Fischer usw. in College-CS-Kursen. Sie werden als "branchenüblich" bezeichnet. Ich kann jedoch keine Beweise (abgesehen von vielleicht der Manchester-Tragekette) aus jüngster Zeit finden, dass sie tatsächlich irgendwo speziell verwendet werden. Eine Google-Suche gibt nur Seiten mit Zeitschriften und akademischer Forschung zurück. Es werden höchstens hypothetische Implementierungen angegeben.
Meine Frage ist, gibt es bestimmte Stellen / Implementierungen, an denen Carry-Lookahead-Addierer verwendet werden? Oder sind sie für die reale Welt irrelevant?
Antworten:
Dies ist eine einfache Frage mit einer sehr komplexen Antwort.
Zunächst einige Hintergrundinformationen.
Das reale VLSI-Design ist ein äußerst technisches Feld, in dem sich die Kompromisse ständig ändern. Die Zeit, die eine Schaltung benötigt, um eine Antwort zu berechnen, ist selten der einzige wichtige Faktor. Es gibt auch Stromverbrauch und physischen Bereich sowie eine Reihe von Faktoren, die zeigen, dass die von Ihnen entworfenen Schaltkreise tatsächlich analog sind (z. B. Drahtwiderstand, parasitäre Kapazität). All dies ist in einer realen Schaltung wichtig und kann sich auf das gewählte Design auswirken.
Zweitens müssen Sie den gesamten Lebenszyklus eines Projekts berücksichtigen. Ein Addierer, der für eine VLSI-Realisierung geeignet ist, ist möglicherweise nicht für eine FPGA-Realisierung geeignet. Wenn das Design eine Phase durchläuft, die auf einem FPGA getestet wird, erhalten Sie das Bild.
Drittens wird nicht jeder Addierer gleich gemacht. Auf einer typischen CPU hängen viele Addierer herum, die unterschiedliche Aufgaben ausführen. Es gibt wahrscheinlich mehrere ganzzahlige ALUs, einen Gleitkomma-Mantissen-Addierer, einen Addierer, der die Adressberechnung durchführt, einen Addierer, der Verzweigungsziele berechnet, und so weiter. Das gilt nicht für die Carry-Save-Addierer, die Sie in modernen Multiplikationseinheiten finden. Jeder hat seine eigenen Besonderheiten und Einschränkungen.
Die Berechnung des Verzweigungsziels umfasst beispielsweise typischerweise das Hinzufügen einer kleinen Konstante zu einem vollständigen Wort, was ein anderes Addiererdesign vorschlägt als eines, bei dem zwei vollständige Wörter addiert werden. In ähnlicher Weise erfordert die Gleitkommaaddition einen Rundungsschritt nach der Addition, der möglicherweise weniger als einen Zyklus dauert. Es gibt also keinen Grund, warum Sie den Rest des Zyklus nicht stehlen könnten, um die Addition abzuschließen.
Schließlich und vielleicht am wichtigsten ist, dass die großen Player (z. B. Intel, AMD, NVIDIA) aus offensichtlichen Gründen ziemlich genau über Implementierungsdetails auf niedriger Ebene informiert sind, es sei denn, sie glauben, dass sie ein Papier und / oder Patent daraus ziehen können. Selbst dann kann man ohne Reverse Engineering oft nicht sicher sein, was sie tatsächlich getan haben.
Trotzdem gibt es ein paar Dinge, die wir wissen.
Das Wichtigste, was Sie wissen müssen, ist, dass Carry-Lookahead-Methoden Bausteine sind und nicht unbedingt Methoden an sich. Eine Analogie könnte hier angebracht sein.
Wenn Sie an Algorithmusklassen denken, haben Sie wahrscheinlich eine Reihe von Sortieralgorithmen gelernt, z. B. Schnellsortierung, Zusammenführungssortierung, Einfügesortierung usw. Wenn das Sortieren in der realen Welt ein Leistungsengpass ist, würde jeder anständige Ingenieur diese als primitive Bausteine betrachten, aus denen eine "echte" Sortierung konstruiert werden kann.
Der Sortieralgorithmus aus der GNU C ++ - Standardbibliothek verwendet beispielsweise eine schnelle Sortierung und eine Einfügesortierung, wenn die Intervalle klein genug werden. Wenn es jedoch nach einigen Durchgängen so aussieht, als hätte die schnelle Sortierpartitionierung das pathologische Verhalten getroffen, wird auf die Heap-Sortierung zurückgegriffen. Das sind drei verschiedene Sortieralgorithmen, um eine Sortierung mit industrieller Stärke zu erstellen.
Gleiches gilt für Addiererschaltungen. Es ist zum Beispiel bekannt, dass die Pentium 4-Ganzzahleinheit einen Han-Carlson-Addierer verwendete, der eine Mischung aus Kogge-Stone und Brent-Kung ist. (Han-Carlson ist besonders interessant, weil es ein "Sweet Spot" im Kompromiss zwischen Ausbreitungsverzögerung und Chipbereich ist, der auch sehr energieeffizient ist.) Es lohnt sich oft, eine Mischung aus mehreren Methoden zu verwenden.
"Reine" Carry-Lookahead-Addierer sind in synthetisierten Schaltkreisen (z. B. wenn Sie Cadence oder Synopsys einen Verilog "+" - Operator zuführen) immer noch die Norm. Of-Order-Ausführungs-Engines scheinen sich in Richtung eines etwas anderen Designs für ihre ganzzahligen Einheiten zu bewegen.
Spekulative Addierer sind Schaltungen, die eine extrem geringe Ausbreitungsverzögerung aufweisen, aber nur teilweise korrekt funktionieren (95% der Zeit sind typisch), und es ist möglich, mit sehr wenig Logik zu sagen, ob der spekulative Addierer das richtige Ergebnis zurückgibt oder nicht. Die Idee ist also, eine spekulative Addition und die Hälfte einer Carry-Lookahead-Addition parallel in einem Zyklus durchzuführen. Wenn der spekulative Addierer die richtige Antwort zurückgegeben hat, ist die Anweisung abgeschlossen. Andernfalls blockieren Sie die Pipeline und führen Sie die andere Hälfte der genauen Addition durch.
Da Sie wissen, dass der langsame Pfad zwei Zyklen dauert, könnten die Entwickler eine platz- und energieeffizientere Methode verwenden, selbst wenn sie für den allgemeinen Gebrauch zu langsam wäre.
quelle
Ja, viele Computer verwenden Carry-Lookahead-Addierer. Ich habe einige alte Mikroprozessoren rückentwickelt und kann einige Beispiele nennen.
Die ALU des Intel 8008 (ihr erster 8-Bit-Prozessor) enthielt eine große Carry-Lookahead-Schaltung, die mit dynamischer Logik implementiert war. Diese Schaltung nahm ungefähr so viel Platz ein wie die ALU selbst. Carry Lookahead ist auf dem 8008-Datenblatt in Abbildung 3 dargestellt. Ich habe keine anderen Prozessoren aus den 1970er Jahren mit Carry-Lookahead für die ALU gesehen, daher ist der 8008 in dieser Hinsicht etwas ungewöhnlich.
Der 6502 verwendet einen primitiven Carry-Lookahead für den Inkrementierer des Programmzählers (PC). Es erkennt, ob ein Übertrag vom unteren Byte des PCs vorliegt, und erhöht damit das obere Byte. Dies reduziert den Ripple-Carry von möglicherweise 16 Bit auf 8 Bit. Die ALU des 6502 verwendet Ripple-Carry, obwohl die Carry-Logik für alternierende Bits invertiert ist, wodurch ein Inverter aus dem Pfad herausgeschnitten und etwas schneller gemacht wird.
Der Z-80 verfügt über einen 16-Bit-Inkrementierer / Dekrementierer für PC-Updates, Inc / Dec-Anweisungen und einen Schleifenzähler. Es wird eine Übertrags-Sprung-Struktur verwendet, sodass Übertragungen für Gruppen von zwei Bits berechnet werden. Außerdem wird ein Carry-Lookahead verwendet, um den Carry aus den Bits 0-7, 7-11 und 12-14 zu generieren. Andere Übertragungen werden mit Welligkeitsübertrag ( Details ) berechnet . Die ALU des Z-80 besteht überraschenderweise aus 4 Bit, sodass jede 8-Bit-Operation zwei Durchgänge durch die ALU ausführt.
Der 8085 verwendet dagegen Ripple Carry für seinen 16-Bit-Inkrementierer / Dekrementierer. Aber wie beim 6502 wird es etwas beschleunigt, indem die Übertragslogik in abwechselnde Bits invertiert wird.
Der ARM-1 verfügt über eine 32-Bit-ALU ohne Carry-Lookahead, nur über Ripple-Carry. Es verwendet auch den Trick des Invertierens des Übertrags in alternierende Bits.
In der Minicomputer-Welt wurden viele Prozessoren aus dem bekannten 4-Bit-ALU-Chip 74181 mit internem Carry-Lookahead gebaut. Beispiele hierfür sind der Data General Nova, der Xerox Alto, der VAX-11/780 und der TI-990. (Siehe längere Wikipedia-Liste .) Einige dieser verwendeten Ripple-Übertragungen zwischen den einzelnen 4-Bit-Chips und andere verwenden den 74182-Übertrags-Lookahead-Chip für einen vollständigen Lookahead.
Zusammenfassend lässt sich sagen, dass verschiedene Mikroprozessoren je nach ihren Leistungszielen und den Vorgängen auf dem kritischen Pfad verschiedene Übertragungsverfahren verwenden. Die ALU kann einen vollständigen Carry-Lookahead (wie der 8008) oder sogar eine halbe Größe (wie der Z-80) verwenden. Der Inkrementierer kann ein Leistungsproblem sein, da er in einem 8-Bit-Prozessor normalerweise 16 Bit beträgt, was zu einer doppelten Welligkeitsverzögerung führt. Der Inkrementierer kann einen Ripple-Carry (8085), einen Carry-Lookahead (6502) oder mehrere Carry-Lookahead-Stufen (Z-80) aufweisen.
quelle