Warum ist Addition in modernen Prozessoren so schnell wie bitweise Operationen?

73

Ich weiß, dass bitweise Operationen auf modernen Prozessoren so schnell sind, weil sie parallel mit 32 oder 64 Bits arbeiten können, sodass bitweise Operationen nur einen Taktzyklus benötigen. Die Addition ist jedoch eine komplexe Operation, die aus mindestens einer und möglicherweise bis zu einem Dutzend bitweiser Operationen besteht, daher dachte ich natürlich, dass sie 3-4 mal langsamer sein wird. Ich war überrascht, als ich nach einem einfachen Benchmark feststellte, dass die Addition genauso schnell ist wie alle bitweisen Operationen (XOR, OR, AND usw.). Kann jemand Licht ins Dunkel bringen?

SoloNasus
quelle
1
Ja, die Multiplikation war auch in meinen Tests ziemlich schnell. Es war nur ungefähr 2x langsamer als Addition, während Division ungefähr 30x (!) Mal langsamer war.
SoloNasus
Kompakter Überblick über die neuesten
Franki
Weiter ausgearbeitet: Dissertation von PhD Jun Chen "Parallelpräfixstrukturen für binäre und modulo {2n − 1, 2n, 2n + 1} Addierer" digital.library.okstate.edu/etd/Chen_okstate_0664D_10070.pdf
Franki

Antworten:

104

Die Addition erfolgt schnell, da die CPU-Entwickler die erforderlichen Schaltkreise eingebaut haben, um sie schnell zu machen. Es erfordert deutlich mehr Gates als bitweise Operationen, aber es ist häufig genug, dass CPU-Designer dies als wertvoll erachtet haben. Siehe https://en.wikipedia.org/wiki/Adder_(electronics) .

Beide können so schnell ausgeführt werden, dass sie innerhalb eines einzelnen CPU-Zyklus ausgeführt werden können. Sie sind nicht gleich schnell - Addition erfordert mehr Gates und mehr Latenz als eine bitweise Operation -, aber es ist schnell genug, dass ein Prozessor es in einem Taktzyklus tun kann. Für die Befehlsdecodierungs- und -steuerlogik entsteht ein Zeitaufwand pro Befehl, und der Zeitaufwand für eine bitweise Operation ist erheblich höher als der Zeitaufwand für eine bitweise Operation, sodass die Differenz zwischen den beiden durch diesen Zeitaufwand überlastet wird. AProgrammer's answer und Paul92's answer erklären diese Effekte gut.

DW
quelle
Kommentare sind nicht für längere Diskussionen gedacht. Diese Unterhaltung wurde in den Chat verschoben .
DW
38

Es gibt verschiedene Aspekte.

  • Die relativen Kosten einer bitweisen Operation und einer Addition. Ein naiver Addierer hat eine Gate-Tiefe, die linear von der Breite des Wortes abhängt. Es gibt alternative Ansätze, die hinsichtlich der Gatter teurer sind und die Tiefe verringern (IIRC, die Tiefe hängt dann logarithmisch von der Breite des Wortes ab). Andere haben Referenzen für solche Techniken angegeben. Ich möchte nur darauf hinweisen, dass der Unterschied auch weniger wichtig ist, als wenn man nur die Kosten der Operation in Betracht zieht, da Steuerlogik erforderlich ist, die Verzögerungen hinzufügt.

  • Hinzu kommt die Tatsache, dass Prozessoren normalerweise getaktet sind (mir sind Forschungsergebnisse oder nicht getaktete Sonderkonstruktionen bekannt, aber ich bin mir nicht sicher, ob einige kommerziell erhältlich sind). Dies bedeutet, dass unabhängig von der Geschwindigkeit einer Operation ein ganzzahliges Vielfaches des Taktzyklus erforderlich ist.

  • Schließlich gibt es noch die Überlegungen zur Mikroarchitektur: Sind Sie sicher, dass Sie messen, was Sie wollen? Heutzutage sind Prozessoren in der Regel mehrskaliert, nicht in der richtigen Reihenfolge ausgeführt und was auch immer. Dies bedeutet, dass sie mehrere Anweisungen gleichzeitig und in verschiedenen Abschlußstadien ausführen können. Wenn Sie durch Messungen zeigen möchten, dass eine Operation mehr Zeit in Anspruch nimmt als eine andere, müssen Sie diesen Aspekt berücksichtigen, da das Ziel darin besteht, diesen Unterschied zu verbergen. Wenn Sie unabhängige Daten verwenden, haben Sie möglicherweise denselben Durchsatz für Additions- und bitweise Operationen, aber ein Maß für die Latenz oder das Einführen von Abhängigkeiten zwischen den Operationen kann etwas anderes anzeigen. Und Sie müssen auch sicherstellen, dass der Engpass Ihrer Maßnahme in der Ausführung und nicht etwa in den Speicherzugriffen liegt.

Ein Programmierer
quelle
6
+1. Ja, die meisten Prozessoren werden getaktet, aber einige wenige taktlose CPUs sind im Handel erhältlich.
David Cary
2
Eine andere Möglichkeit besteht darin, dass ein Prozessor ein 64-Bit-Register als ein 16-Bit-Stück und drei 17-Bit-Stücke speichert, wobei die zusätzlichen Bits jedes Stücks einen verzögerten Übertrag von unten enthalten. Eine Addition, auf die eine bitweise Operation oder ein Speicher folgt, erfordert möglicherweise 1-2 zusätzliche Zyklen, um den Übertrag zu verbreiten, eine Addition, auf die eine andere Addition folgt, jedoch nicht. Ferner kann im "Speicher" -Fall die zusätzliche Ausbreitungszeit die Leistung des Speichers verzögern, aber es wäre nicht erforderlich, dass Code darauf "wartet".
Supercat
3
@supercat Der Pentium 4 hat so etwas mit einer ALU mit doppelter Geschwindigkeit (im Vergleich zum Rest des Prozessors) gemacht, bei der die niedrigen 16 oder 32 Bits einen halben Zyklus vor den Bits der oberen Hälfte für eine nachfolgende Operation bereit wären.
Jeffrey Bosboom
2
Sind Sie sicher, dass Sie messen, was Sie wollen? In diesem Fall ist die Schlussfolgerung des OP aus den Messungen für die überwiegende Mehrheit der CPUs korrekt. Das Hinzufügen ist so verbreitet, dass superskalare CPUs Add-Units an allen Ausführungsports haben, und Boolesche Werte sind (in der Anzahl der Transistoren) so billig zu implementieren, dass sie auch an allen Ports vorhanden sind. Add und Boolean haben also fast immer den gleichen Durchsatz (z. B. 4 pro Takt in Intel Haswell).
Peter Cordes
2
Das Hinzufügen von SIMD-Ganzzahlen führt jedoch häufig zu einem niedrigeren Durchsatz als das boolesche SIMD-Verfahren, obwohl diese normalerweise dieselbe Latenz haben. Intel-CPUs von PentiumII bis Broadwell können nur vector-int-Adds (z. B. paddw) mit 2 pro Takt ausführen, Boolesche Werte (wie z. B. pand) mit 3 pro Takt. (Skylake setzt einen Vektoraddierer auf alle drei Vektorausführungsports.)
Peter Cordes
24

CPUs arbeiten in Zyklen. Bei jedem Zyklus passiert etwas. Normalerweise dauert die Ausführung eines Befehls mehr Zyklen, es werden jedoch mehrere Befehle gleichzeitig in verschiedenen Zuständen ausgeführt.

Ein einfacher Prozessor kann beispielsweise drei Schritte für jeden Befehl enthalten: Abrufen, Ausführen und Speichern. Es werden zu jeder Zeit 3 ​​Befehle verarbeitet: Einer wird abgerufen, einer wird ausgeführt und einer speichert seine Ergebnisse. Dies wird als Pipeline bezeichnet und hat in diesem Beispiel 3 Stufen. Moderne Prozessoren haben Pipelines mit über 15 Stufen. Die Addition sowie die meisten arithmetischen Operationen werden jedoch normalerweise in einer Stufe ausgeführt (ich spreche von der Operation des Addierens von 2 Zahlen durch die ALU, nicht von der Anweisung selbst - abhängig von der Prozessorarchitektur, die die Anweisung möglicherweise erfordert mehr Zyklen zum Abrufen von Argumenten aus dem Speicher, Durchführen von Bedingungen, Speichern von Ergebnissen im Speicher).

Die Dauer eines Zyklus wird durch den längsten kritischen Pfad bestimmt. Grundsätzlich ist es die längste Zeit, die für die Fertigstellung eines Abschnitts der Pipeline erforderlich ist. Wenn Sie die CPU schneller machen möchten, müssen Sie den kritischen Pfad optimieren. Wenn es nicht möglich ist, den kritischen Pfad per se zu reduzieren, kann er in zwei Phasen der Pipeline aufgeteilt werden, und Sie können jetzt Ihre CPU mit fast der doppelten Frequenz takten (vorausgesetzt, es gibt keinen anderen kritischen Pfad, der Sie daran hindert ). Dies ist jedoch mit einem Mehraufwand verbunden: Sie müssen ein Register zwischen den Stufen der Pipeline einfügen. Das bedeutet, dass Sie nicht wirklich die doppelte Geschwindigkeit erreichen (das Register benötigt Zeit zum Speichern der Daten), und Sie haben das gesamte Design kompliziert.

Es gibt bereits sehr effiziente Methoden zur Ausführung der Addition (z. B. Carry-Lookahead-Addierer), und die Addition ist kein kritischer Pfad für die Prozessorgeschwindigkeit, weshalb es keinen Sinn macht, sie in mehrere Zyklen aufzuteilen.

Beachten Sie außerdem, dass es für Sie kompliziert erscheinen mag, dass Hardware-Vorgänge jedoch sehr schnell parallel ausgeführt werden können.

Paul92
quelle
3
Der große Aufwand für längere Pipelines besteht darin, dass mehr Zyklen erforderlich sind, um eine Verzweigungsfehlvorhersage zu beheben! Die Ausgaben für Transistoren zum Puffern von Daten zwischen Stufen sind heutzutage gering. Sogar eine einfache Pipeline-CPU muss vor den tatsächlich ausgeführten Befehlen abrufen / dekodieren. Wenn die CPU feststellt, dass das Front-End am falschen Code gearbeitet hat, weil ein Zweig anders verlaufen ist als vorhergesagt (oder auf andere Weise falsch spekuliert), muss sie diese Arbeit wegwerfen und mit der richtigen Anweisung beginnen. Schlimmer wird es nur mit superskalaren Out-of-Order-CPUs, die viele Insns im Flug haben können.
Peter Cordes
12

Prozessoren werden getaktet, so dass einige Anweisungen, auch wenn sie deutlich schneller ausgeführt werden können als andere, möglicherweise die gleiche Anzahl von Zyklen benötigen.

Sie werden wahrscheinlich feststellen, dass die zum Transport von Daten zwischen Registern und Ausführungseinheiten erforderliche Schaltung wesentlich komplizierter ist als die Addierer.

Beachten Sie, dass der einfache MOV-Befehl (Register to Register) noch weniger Berechnungen ausführt als die bitweise Logik, MOV und ADD jedoch normalerweise einen Zyklus benötigen. Wenn MOV doppelt so schnell ausgeführt werden könnte, würden die CPUs doppelt so schnell getaktet und die ADDs wären zwei Zyklen.

James Hollis
quelle
Kommentare sind nicht für längere Diskussionen gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Gilles
1
Zusammenfassung der Diskussion: Einige CPUs außerhalb der Reihenfolge verarbeiten MOV speziell mit Registerumbenennung und praktisch ohne Latenz. Siehe Can x86 des MOV wirklich „frei“ sein? Warum kann ich das überhaupt nicht reproduzieren? für die vollständigen Details, was MOV wirklich kostet.
Peter Cordes
12

Die Addition ist wichtig genug, um nicht darauf warten zu müssen, dass ein Übertragsbit einen 64-Bit-Akkumulator durchläuft. Der Begriff dafür ist ein Übertrags-Lookahead-Addierer und sie sind im Grunde Teil von 8-Bit-CPUs (und ihren ALUs) und höher. Tatsächlich benötigen moderne Prozessoren für eine vollständige Multiplikation in der Regel nicht viel mehr Ausführungszeit: Carry-Lookahead ist tatsächlich ein sehr altes (und vergleichsweise erschwingliches) Tool in der Toolbox eines Prozessordesigners.

user72735
quelle
Die ganzzahlige Multiplikation ist definitiv eine höhere Latenz und einen niedrigeren Durchsatz als ADD auf x86. Aber es ist erstaunlich schnell, wenn man bedenkt, wie viele Addierer benötigt werden, um einen schnellen Multiplikator aufzubauen: Zum Beispiel bei Intel seit Nehalem und bei AMD seit Ryzen beträgt die 8/16/32/64-Bit-Skalar-Integer-Multiplikation eine Latenz von 3 Zyklen mit einem pro 1 c Durchsatz (eine Ausführungseinheit mit vollständiger Pipeline). Dies ist schlecht im Vergleich zu einem ADD-Durchsatz von 3 oder 4 pro Takt, ist aber erstaunlich im Vergleich zu einer IMUL-Latenz von 9 Zyklen in Intel Pentium P5. Ähnliches gilt für SIMD: Vektor-Int-Multiplikation ist eine höhere Latenz und ein geringerer Durchsatz als Add, aber immer noch schnell.
Peter Cordes
Also ja, multiplizieren war früher im Vergleich zu anderen Anweisungen viel teurer als heute. Es lohnt sich normalerweise nicht, es mit mehr als zwei Anweisungen zu vermeiden, und manchmal lohnt sich nicht einmal ein Ersatz mit zwei Anweisungen (z. B. mit einer Umschalt- + Hinzufügungsanweisung lea).
Peter Cordes
9

Ich glaube, Sie werden kaum einen Prozessor finden, dessen Addition mehr Zyklen als eine bitweise Operation benötigt. Teilweise, weil die meisten Prozessoren mindestens eine Addition pro Befehlszyklus ausführen müssen, um einfach den Programmzähler zu erhöhen. Bloße bitweise Operationen sind nicht allzu nützlich.

(Befehlszyklus, kein Taktzyklus - z. B. benötigt der 6502 mindestens zwei Taktzyklen pro Befehl, da keine Pipeline vorhanden ist und kein Befehls-Cache vorhanden ist.)

Das eigentliche Konzept, das Sie möglicherweise vermissen, ist das des kritischen Pfads : Innerhalb eines Chips bestimmt die längste Operation, die innerhalb eines Zyklus ausgeführt werden kann, auf Hardwareebene, wie schnell der Chip getaktet werden darf.

Die Ausnahme ist die (selten verwendete und kaum kommerzialisierte) asynchrone Logik, die je nach Logiklaufzeit, Gerätetemperatur usw. tatsächlich mit unterschiedlichen Geschwindigkeiten ausgeführt wird.

pjc50
quelle
Es handelt sich nicht um vom Benutzer steuerbare bitweise Operationen, aber einige Anweisungen auf dem 8086 (z. B. das Löschen des Interrupt-Flags ) haben weniger Zyklen als eine Ganzzahladdition gedauert. Abstrakter könnte ein RISC-System, bei dem alle Anweisungen ein Wort groß sind, einen einfachen Binärzähler für den PC verwenden, der eine viel schnellere Schaltung als ein Allzweckaddierer wäre.
Markieren Sie
Die Addition auf dem Programmzähler ist im Vergleich zu einer Additionsarithmetik sehr einfach, da einer der Operanden klein ist (entweder eine Befehlsgröße oder ein relativer Sprungversatz, der ebenfalls größenbegrenzt ist)
Ben Voigt,
6502 wurde weitergeleitet - es hat das erste Byte der nächsten Anweisung während des letzten Zyklus der vorherigen Anweisung gelesen. Ansonsten hätte das Abrufen / Dekodieren / Ausführen mindestens drei Zyklen gedauert.
gnasher729
8

Auf der Gate-Ebene haben Sie Recht, dass das Hinzufügen mehr Arbeit erfordert und daher länger dauert. Diese Kosten sind jedoch so gering, dass sie keine Rolle spielen.

Moderne Prozessoren werden getaktet. Sie können nur ein Vielfaches dieser Taktrate ausführen. Wenn die Taktraten erhöht würden, müssten Sie mindestens 2 Zyklen für die Addition aufwenden, um die Geschwindigkeit der bitweisen Operationen zu maximieren. Ein Großteil dieser Zeit würde damit verbracht, herumzuwarten, weil Sie nicht wirklich die vollen 2 Zyklen Zeit brauchten. Sie brauchten nur 1.1 (oder eine solche Zahl). Jetzt fügt Ihr Chip langsamer hinzu als alle anderen auf dem Markt.

Schlimmer noch, das bloße Hinzufügen oder Ausführen bitweiser Operationen ist nur ein winziger Teil dessen, was während eines Zyklus vor sich geht. Sie müssen in der Lage sein, Anweisungen innerhalb eines Zyklus abzurufen / zu decodieren. Sie müssen in der Lage sein, Cache-Operationen innerhalb eines Zyklus auszuführen. Viele andere Dinge laufen auf der gleichen Zeitskala wie das einfache Hinzufügen oder die bitweise Operation.

Die Lösung besteht natürlich darin, eine extrem tiefe Pipeline zu entwickeln, die diese Aufgaben in winzige Teile zerlegt, die in die winzige Zykluszeit passen, die durch eine bitweise Operation definiert wird. Der Pentium 4 hat bekanntermaßen die Grenzen des Denkens in dieser tiefen Pipeline aufgezeigt. Es treten alle möglichen Probleme auf. Insbesondere das Verzweigen wird notorisch schwierig, da Sie die Pipeline leeren müssen, sobald Sie über die Daten verfügen, um herauszufinden, welche Verzweigung vorgenommen werden soll.

Cort Ammon
quelle
7

Moderne Prozessoren werden getaktet: Jede Operation benötigt eine ganzzahlige Anzahl von Taktzyklen. Die Entwickler des Prozessors bestimmen die Länge eines Taktzyklus. Dabei gibt es zwei Überlegungen: Zum einen die Geschwindigkeit der Hardware, beispielsweise gemessen als Verzögerung eines einzelnen NAND-Gatters. Dies hängt von der verwendeten Technologie und von Kompromissen zwischen Geschwindigkeit und Stromverbrauch ab. Es ist unabhängig vom Prozessordesign. Zweitens entscheiden die Designer, dass die Länge eines Taktzyklus n Verzögerungen eines einzelnen NAND-Gatters entspricht, wobei n 10 oder 30 oder ein beliebiger anderer Wert sein kann.

Diese Auswahl begrenzt, wie komplex Operationen sein können, die in einem Zyklus verarbeitet werden können. Es wird Operationen geben, die in 16, aber nicht in 15 NAND-Verzögerungen ausgeführt werden können. Wenn Sie also n = 16 wählen, bedeutet dies, dass eine solche Operation in einem Zyklus ausgeführt werden kann. Wenn Sie n = 15 wählen, bedeutet dies, dass dies nicht ausgeführt werden kann.

Die Konstrukteure werden n auswählen, damit viele wichtige Operationen in einem oder vielleicht zwei oder drei Zyklen ausgeführt werden können. n wird lokal optimal gewählt: Wenn Sie n durch n-1 ersetzen, wären die meisten Operationen etwas schneller, aber einige (diejenigen, die wirklich die vollen n NAND-Verzögerungen benötigen) wären langsamer. Wenn sich nur wenige Vorgänge verlangsamen würden, sodass die gesamte Programmausführung im Durchschnitt schneller ist, hätten Sie n-1 gewählt. Sie hätten auch n + 1 auswählen können. Das macht die meisten Operationen etwas langsamer, aber wenn Sie viele Operationen haben, die nicht innerhalb von n Verzögerungen, sondern innerhalb von n + 1 Verzögerungen ausgeführt werden können, würde dies den Prozessor insgesamt schneller machen.

Jetzt Ihre Frage: Addieren und Subtrahieren sind so übliche Operationen, dass Sie sie in einem Zyklus ausführen möchten. Infolgedessen spielt es keine Rolle, dass AND, OR usw. schneller ausgeführt werden können: Sie benötigen immer noch diesen einen Zyklus. Natürlich hat die Einheit, die UND, ODER usw. "berechnet", viel Zeit, um ihre Daumen zu drehen, aber dem kann nicht geholfen werden.

Beachten Sie, dass es nicht nur darum geht, ob eine Operation innerhalb von n NAND-Verzögerungen ausgeführt werden kann oder nicht: Eine Addition kann zum Beispiel schneller erfolgen, indem Sie ein bisschen clever sind, noch schneller, indem Sie sehr clever sind, noch ein bisschen schneller, indem Sie außerordentlich viel Hardware investieren , und endlich kann ein Prozessor eine Mischung aus sehr schnellen, sehr teuren und etwas langsameren und billigeren Schaltungen haben, so dass die Möglichkeit besteht, eine Operation gerade so schnell genug zu machen, indem man mehr Geld dafür ausgibt.

Jetzt könnten Sie die Taktrate so hoch / den Zyklus so kurz machen, dass nur die einfachen Bitoperationen in einem Zyklus ausgeführt werden und alles andere in zwei oder mehr. Das würde den Prozessor höchstwahrscheinlich verlangsamen. Bei Operationen, die zwei Zyklen dauern, ist es in der Regel mit einem Mehraufwand verbunden, eine unvollständige Anweisung von einem Zyklus zum nächsten zu verschieben. Zwei Zyklen bedeuten also nicht, dass Sie doppelt so viel Zeit für die Ausführung haben. Um die Addition in zwei Zyklen durchzuführen, konnte man die Taktrate nicht verdoppeln.

gnasher729
quelle
6

Lassen Sie mich ein paar Dinge korrigieren, die in Ihren bisherigen Antworten nicht explizit erwähnt wurden:

Ich weiß, dass bitweise Operationen auf modernen Prozessoren so schnell sind, weil sie parallel mit 32 oder 64 Bit arbeiten können.

Das ist wahr. Die Bezeichnung einer CPU als "XX" -Bit bedeutet normalerweise (nicht immer), dass die meisten ihrer üblichen Strukturen (Registerbreiten, adressierbarer RAM usw.) XX-Bits groß sind (häufig "+/- 1" oder so). In Bezug auf Ihre Frage können Sie jedoch mit Sicherheit davon ausgehen, dass eine CPU mit 32 oder 64 Bit jede grundlegende Bitoperation mit 32 oder 64 Bit in konstanter Zeit ausführt.

Daher dauern bitweise Operationen nur einen Taktzyklus.

Diese Schlussfolgerung ist nicht unbedingt der Fall. Insbesondere CPUs mit umfangreichen Befehlssätzen (google CISC vs. RISC) können selbst für einfache Befehle problemlos mehr als einen Zyklus benötigen. Mit Interleaving können sogar einfache Befehle mit 3 Takten (als Beispiel) in den Fetch-Exec-Store zerfallen.

Das Hinzufügen ist jedoch eine komplexe Operation

Nein, die Ganzzahladdition ist eine einfache Operation. Subtraktion auch. Es ist sehr einfach, Addierer in voller Hardware zu implementieren, und sie erledigen ihre Aufgaben so schnell wie grundlegende Bitoperationen.

Das besteht aus mindestens einer und möglicherweise bis zu einem Dutzend bitweiser Operationen, also dachte ich natürlich, dass es 3-4 mal langsamer sein wird.

Es wird 3-4 mal so viele Transistoren aufnehmen, aber im Vergleich zum Gesamtbild ist das vernachlässigbar.

Ich war überrascht, nach einem einfachen Benchmark zu sehen, dass die Addition genau so schnell ist wie jede der bitweisen Operationen (XOR, OR, AND usw.). Kann jemand Licht ins Dunkel bringen?

Ja: Ganzzahladdition ist eine bitweise Operation (mit ein paar mehr Bits als die anderen, aber immer noch). Es ist nicht notwendig, irgendetwas in Schritten zu tun, es sind keine komplizierten Algorithmen, Uhren oder irgendetwas anderes erforderlich.

Wenn Sie mehr Bits als Ihre CPU-Architektur hinzufügen möchten, müssen Sie dies schrittweise tun. Dies ist jedoch auf einer anderen Komplexitätsebene (Programmiersprachenebene, nicht Baugruppen- / Maschinencodeebene). Dies war in der Vergangenheit (oder heute auf kleinen Embedded-CPUs) ein häufiges Problem. Für PCs usw. reichen ihre 32 oder 64 Bit für die gängigsten Datentypen aus, damit dies zu einem Streitpunkt wird.

AnoE
quelle
Es ist interessant zu bemerken, dass die Reduzierung der Zeitkosten für das Hinzufügen von O (N) zu O (sqrt (N)) die erforderliche Anzahl von Transistoren oder die Routing-Komplexität nicht signifikant erhöht (jede Stufe muss nur einen Tragdraht von unten hereinschleichen lassen) und es müssen zusätzliche sqrt (N) Verschmelzungsstufen vorhanden sein. Die Zeitkosten können auf 0 (lgN) zu Kosten von 0 (lgN) Transistoren reduziert werden, aber in vielen Fällen kann es hilfreich sein, so etwas wie einen 64-Bit-Prozess zu verarbeiten. Bit-Addition als zB acht 8-Bit-Additionen (unter Verwendung von sqrtN-Weiterleitung), die mit drei Ebenen der Zusammenführungslogik verbunden sind, anstatt als 64 1-Bit-
Additionen
Ja, Addierer sind ziemlich einfach. Was wirklich beeindruckend ist, sind moderne x86-CPUs mit einem 64-Bit-Integer- Multiplikator mit 3-Zyklus-Latenz . (zB imul rax, rcxhat 3c Latenz und einen pro 1c Durchsatz bei der Intel Sandybridge-Familie und AMD Ryzen). Selbst eine 64-Bit-Vollmultiplikation (die das 128-Bit-Ergebnis in rdx: rax erzeugt) hat die gleiche Latenz und den gleichen Durchsatz, wird jedoch als 2 Uops implementiert (die an verschiedenen Ports parallel ausgeführt werden). ( Anweisungen und eine ausgezeichnete Anleitung für Mikroarchive finden Sie unter agner.org/optimize .)
Peter Cordes
[Add-with-Carry] befindet sich auf einer anderen Komplexitätsebene (Programmiersprachenebene, nicht Assembler- / Maschinencodeebene . Dies hängt von der Sprache ab. AC-Compiler, die auf eine 16-Bit-CPU abzielen, müssen beim Kompilieren add / adc für Sie ausgeben Addition von zwei uint32_tWerten: Dies ist auch heute noch für int64_t auf 32-Bit-Zielen relevant. AVR ist ein 8-Bit-RISC-Mikrocontroller, daher erfordern 32-Bit-Ganzzahlen vier Anweisungen: godbolt.org/g/wre0fM
Peter Cordes
Ja, @PeterCordes, das habe ich gemeint, ich habe meinen Satz ein wenig geklärt.
AnoE