Wie kann eine 8-Bit-CPU große Zahlen berechnen?

Ich versuche, in Logisim eine anweisbare 8-Bit-CPU zu entwerfen. Ist es möglich, mit einer 8-Bit-CPU große Zahlen zu berechnen?

In einem 32-Bit-Computer können Sie Zahlen berechnen, die größer als 32-Bit sind. Ich denke, das ist ein Softwaretrick, aber wer kann mir erklären, wie es funktioniert?

8 Bit auf einmal.
In der Schule hast du die Ziffern 0-9 gelernt, aber ich wette, du weißt, wie man weiter zählt und sogar einige grundlegende Berechnungen im Kopf hat. Fragen Sie sich, wie Sie das schaffen, denn die „Ziffern“ mögen unterschiedlich sein, aber die Methode ist genau identisch. Die Magie, der Sie sich wahrscheinlich nicht bewusst waren, ist das 'versteckte' 9. Bit in der Recheneinheit namens 'Carry'-Flag.

Antworten (3)

Selbst auf 8-Bit- oder 4-Bit-Rechnern ist es durchaus möglich, mit sehr großen Zahlen zu arbeiten. Es ist nicht sehr effizient, aber es ist möglich. Dies geschieht durch stückweise Bearbeitung der Zahlen mit Unterstützung spezifischer Prozessorbefehle.

Ein gängiger 8-Bit-Mikrocontroller ist die Atmel AVR-Serie. Um 8-Bit-Zahlen zu addieren, verwendet es eine Anweisung namens ADD. Dieser Befehl wird verwendet, um zwei Registerwerte zu addieren. Zum Beispiel können Sie tun

LDI R16, 5
LDI R17, 10
ADD R16, R17
; R16 = 15

R16 und R17 addieren und das Ergebnis in R16 eingeben. Um 16-Bit-Zahlen hinzuzufügen, tun Sie dies im Grunde einfach mehrmals. Es gibt jedoch einen Haken: das Carry-Bit. Ein weiterer AVR-Befehl ist ADC, für ADd mit Übertrag. Dies macht genau dasselbe wie ADD, fügt aber auch das Carry-Flag hinzu. Sowohl ADD als auch ADC setzen das Carry-Flag, wenn die Additionsoperation überläuft. Sagen Sie, wenn Sie 128 zu 128 addieren, erhalten Sie als Ergebnis 0 mit gesetztem Carry-Flag. Wenn Sie ADC mit gesetztem Carry-Flag aufrufen, wird dem Ergebnis eine 1 hinzugefügt. Hier ist ein Beispiel für eine 16-Bit-Addition:

LDI R16, 232
LDI R17, 3
; R17:R16 = 1000
LDI R18, 208
LDI R19, 7
; R19:R18 = 2000
ADD R16, R18
ADC R17, R19
; R16 = 184
; R17 = 11
; R17:R16 = 3000

Dies kann so oft wie nötig wiederholt werden, um große Zahlen hinzuzufügen. Beachten Sie, dass ein wenig Logik erforderlich ist, um dies zu unterstützen: die Fähigkeit, das Carry-Flag in den Carry-In des Addierers einzuspeisen.

Ein ähnlicher Prozess kann verwendet werden, um Zahlen zu multiplizieren. Das Durchführen von 16-Bit-Multiplikationen auf einem 8-Bit-Prozessor erfordert 4 8-Bit-Multiplikationen und mehrere Additionen. Das Verfahren ist genau dasselbe wie das Multiplizieren von Zahlen von Hand Ziffer für Ziffer, außer dass Sie Bytes anstelle von Ziffern verwenden. Sie müssen alle vier möglichen Bytepaare multiplizieren und sie dann gemäß ihren Stellenwerten addieren. Beispiel in AVR ASM:

LDI R16, 232
LDI R17, 3
; R17:R16 = 1000
LDI R18, 208
LDI R19, 7
; R19:R18 = 2000
MUL R16, R18
; R1:R0 = R16*R18 (1s place product)
MOVW R3:R2, R1:R0
; R3:R2 = R16*R18
MUL R16, R19
; R1:R0 = R16*R19 (256s place product #1)
CLR R4
ADD R3, R0
ADC R4, R1
; R4:R3:R2 = R16*R18 + 256*R16*R19
MUL R17, R18
; R1:R0 = R17*R18 (256s place product #2)
ADD R3, R0
ADC R4, R1
; R4:R3:R2 = R16*R18 + 256*(R16*R19+R17*R18)
MUL R17, R19
; R1:R0 = R17*R19 (65536s place product)
CLR R5
ADD R4, R0
ADC R5, R1
; R5:R4:R3:R2 = R16*R18 + 256*(R16*R19+R17*R18) + 65536*R17*R19
; R5:R4:R3:R2 = 2000000

Sie werden feststellen, dass Sie genau so mit Zahlen von Hand auf Papier arbeiten, aber anstatt mit Ziffern zur Basis 10 zu arbeiten, arbeitet die CPU mit Blöcken von Bits in Wortgröße - in diesem Fall 8 Bits.

Wenn Sie eine CPU verwenden, die mit mehr Bits gleichzeitig arbeiten kann, wird das Arbeiten mit großen Zahlen einfacher, da weniger Anweisungen erforderlich sind. Sie können jedoch dieselben Techniken verwenden, um mit größeren Zahlen zu arbeiten, als der Befehlssatz direkt unterstützt.

Bearbeiten: Der AVR GCC-Compiler enthält Assembler-Code, den er für verschiedene gängige Operationen wie Multiplikation und Division verwendet, was eine gute Referenz dafür sein kann, wie so etwas gemacht wird: https://github.com/gcc-mirror /gcc/blob/master/libgcc/config/avr/lib1funcs.S . Ich denke, meine Multiplikation von 16x16 zu 32 sollte __umulhisi3 entsprechen.

Ich habe eine späte Frage zu Ihrer Antwort. Das Addieren von Zahlen, die zu einem Wert größer als 255 führen, oder das Überlaufen der 8 Bits führt dazu, dass das Carry-Flag gesetzt wird und das Zählen wieder bei Null beginnt. Das Carry-Flag sagt uns also, wenn die Zahl größer als 255 ist, aber wie speichern Sie diese größeren Zahlen unter der Annahme von 8-Bit-Registern und Speicher?
Das Carry-Flag fungiert effektiv als 9. Bit. Die Addition von 8 Bit plus 8 Bit ergibt ein 9-Bit-Ergebnis, die unteren 8 Bit landen im Ausgangsregister und das 9. Bit kommt in das Carry-Flag. Wie Sie das speichern, hängt also davon ab, was Sie tun. In den meisten Fällen, TBH, speichern Sie es nicht wirklich. Entweder verwenden Sie das Übertragsbit in der nächsten Anweisung (add-with-carry) oder Sie überprüfen es vielleicht als Teil einer Überlaufprüfung. Wenn Sie es speichern möchten, können Sie das Übertragsbit einfach in ein zweites Byte kopieren, sodass Sie eine 16-Bit-Zahl haben.
Ok ja das macht Sinn. Aber noch zwei Fragen......
1- Angenommen, Sie führen eine Berechnung durch, die zu einem 16-Bit-Wert führte, z. B. 42000, und dieser wird in 2 aufeinanderfolgenden Bytes im Speicher gespeichert. Woher weiß der Prozessor, dass die Zahl in zwei Bytes und nicht nur in einem Byte gespeichert ist, da es sich um eine 8-Bit-Maschine handelt? Oder wenn Sie einen alten RISC-basierten Prozessor verwenden und in Assembler programmieren, muss der Programmierer wissen, dass dort eine 16-Bit-Zahl vorhanden ist, und beim Schreiben von Software darauf achten, dies zu berücksichtigen?
2- Gleiches gilt für die Verwendung der Add-with-Carry (ADC)-Anweisung. Ist es Sache des Programmierers zu wissen, wann er diese Anweisung im Vergleich zur ADD-Anweisung verwenden soll? Ich vermute, dass moderne Compiler dies heutzutage für uns tun?
1 - Wenn es sich um eine 8-Bit-CPU handelt, hat sie im Allgemeinen per Definition keine Möglichkeit, etwas zu wissen, das größer als 8 Bit ist. Es spielt also keine Rolle, ob sie in benachbarten Bytes sind oder nicht, die Organisation liegt beim Programmierer und/oder Compiler. Gleiches gilt für Register - Sie müssen nicht einmal benachbarte 8-Bit-Register für 16-Bit-Werte verwenden. Aber normalerweise geben Aufrufkonventionen an, dass sie benachbart sein müssen, da dies die Dinge nur einfacher macht.
2 - wenn Sie in Assembler schreiben, ja. Wenn Sie in C schreiben, kümmert sich der Compiler darum. Alles, was Sie als Programmierer tun müssen, ist die Verwendung der richtigen Typen und des Operators +.
Ok ja, jeder Speicherort kann für >8-Bit-Werte verwendet werden, solange Sie wissen, wo sie sich befinden. Aber ab Frage 1 beseitigen Compiler auch die Notwendigkeit für Programmierer, sich Gedanken darüber zu machen, wo sie im Speicher gespeichert werden. In höheren Sprachen wie C kann der Programmierer einfach einen 16-Bit-Wert deklarieren und den Operator + gedankenfrei verwenden?
Beispiel: godbolt.org/z/nvjqbY1vv . Der Compiler hat den Code selbst auf O3 nicht sehr gut optimiert, was seltsam erscheint (scheint, als gäbe es viele nullwertige Register). Und das Multiplizieren ruft __mulsi3 von github.com/gcc-mirror/gcc/blob/master/libgcc/config/avr/… auf .
Ach das ist interessant. Danke Alex, ich habe viel aus dieser Diskussion gelernt.
@alex.forencich FYI/FWIW und AFAIK - GCC optimiert die Zwischendarstellung (GIMPLE), bevor es in die endgültige Ausgabe (AVR usw.) übersetzt wird. Grob gesagt wird AVR als 16-Bit-Maschine behandelt (avr-gcc intist 16 Bit), fast mit Makros implementiert, die zu nativen Anweisungen erweitert werden. Daher die ziemlich schlechte Optimierung bei der Registerzuordnung, dem Herummischen (Vorzeichenerweiterung, Byteverschiebung) und der Arithmetik (16x16+ mul/div usw.).
Was für die gegenwärtige Konversation relevant ist: "lange" Mathematik wird einfach mit der richtigen Auswahl magischer Beschwörungsformeln durchgeführt. Es spielt fast keine Rolle, wohin diese Makros erweitert werden, solange sie das tun, was auf der Verpackung steht. Es ist einfach so, dass 16-Bit-Arithmetik auf AVR ziemlich einfach ist, also neigen sie dazu, kurz zu sein (ein paar Anweisungen). Auf einer allgemeineren Ebene kann jeder universelle Computer dasselbe tun - obwohl Universalität keine Garantien für die Ausführungszeit mit sich bringt (!!).

Wie Sie sagten, können 32-Bit-CPUs Zahlen verarbeiten, die größer als 32 Bit sind. Warum sollte eine 8-Bit-CPU dies also nicht können?

Wenn Sie zwei Zahlen addieren, beginnen Sie mit dem letzten Bit von beiden. Wenn einer von ihnen 1 ist, ist das Ergebnis 1, wenn beide 1 sind, ist das Ergebnis 0, und Sie müssen eine 1 zur Berechnung des zweiten Bits übertragen.

Für das zweite Bit haben Sie die beiden Bits der Zahlen und das getragene Bit. Wenn einer oder alle drei 1 sind, ist das Ergebnis 1. Wenn zwei oder alle 1 sind, müssen Sie wieder eine 1 zur Berechnung des dritten Bits übertragen.

Dies geschieht normalerweise in Hardware, dh es gibt Logikgatter, Sie geben einfach die Zahlen an die Eingänge und erhalten den Ausgang. Beachten Sie, dass Sie bei einem 8-Bit-Addierer auch das sogenannte Carry-Flag aus der Addition der 8. Bits erhalten.

Wenn Sie nur zwei 8-Bit-Zahlen addieren, zeigt das Carry-Flag nur an, ob das Ergebnis größer als 255 ist, die größte Zahl, die eine 8-Bit-Ganzzahl (ohne Vorzeichen) enthalten kann.

Wenn Sie größere Zahlen haben, beginnen Sie jetzt mit der Addition der Bits des zweiten Bytes und berücksichtigen bei der Addition des ersten Bits dieses Bytes das Carry-Flag aus der vorherigen Addition.

Der einzige Unterschied besteht darin, dass eine 32-Bit-CPU 32 Bit auf einmal hinzufügen kann, sodass das Hinzufügen von 64-Bit-Zahlen aus zwei Schritten besteht, während eine 8-Bit-CPU 8 Schritte benötigt.

Auf diese Weise können Sie beliebig große Zahlen auf jeder CPU hinzufügen. Alle anderen Berechnungen werden ähnlich durchgeführt, die kleinere CPU benötigt nur mehr Schritte.

Das Hinzufügen von Zahlen beliebiger Größe ist durch den verfügbaren Arbeitsspeicher eingeschränkt. Wenn Sie 1 KB für einen 8-Bit-Prozessor haben, ist sogar das Hinzufügen von zwei 1024-Bit-Zahlen möglich, aber für 4096-Bit-Zahlen benötigen Sie mehr RAM.

Wenn Sie zwei Zahlen mit Bleistift und Papier addieren, arbeiten Sie von rechts nach links, addieren zwei Ziffern, notieren das Ergebnis und tragen jeden Überlauf. Das Addieren großer Zahlen auf einem Computer funktioniert auf die gleiche Weise. Jede Zahl wird durch eine Reihe von "Ziffern" dargestellt, wobei jede "Ziffer" ein Computerwort ist: in Ihren beiden Beispielen 8 oder 32 Bit breit. Wenn zwei solche Zahlen addiert werden, ist es genau der gleiche Vorgang: Addieren Sie zwei "Ziffern", notieren Sie das Ergebnis und tragen Sie jeden Überlauf. Der Unterschied besteht darin, dass jede Ziffer einen Wert zwischen 0 und 2^8 (für einen 8-Bit-Prozessor) oder einen Wert zwischen 0 und 2^32 (für einen 32-Bit-Prozessor) darstellt. Wenn Sie gerne in Zahlenbasen denken, funktioniert die Bleistift-und-Papier-Addition in der Basis 10,

Wie kann eine 8-Bit-CPU große Zahlen berechnen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v