Browse Files

Aufbau der ALU

Beim Mini-ALU Projekt auf CircuitVerse seht ihr einen 8-Bit Input-Device in dem man einen Maschinenbefehl eingeben kann. Diesen kann man dann mit dem Push-Button ausführen. Was für Befehle das sind wird auf der nächsten Seite erklärt.

Zunächst möchte ich erklären was mit einem Befehl gesteuert werden kann:

  • Die Register der ALU und den

  • Addierer/Subtrahierer an dessen Akkumulator ein Statusregister angeschlossen ist.

Ganz nebenbei wird dabei wiederholt was in den vorigen Session behandelt wurde und alles etwas mathematischer beschrieben. Beim Programmieren wollen wir ja nicht immer beschreiben wie etwas technisch im Computer umgesetzt wird, sondern zum Beispiel den Effekt eines Befehls allgemein (also mathematisch) beschreiben.

Register

Die ALU hat vier Register, die wir kurz mit %00, %01, %10 und %11 bezeichnen. Die Register sind also binär von 0 bis 3 durchnummeriert und % steht für “Register”. Bei der Notation kann man dann beispielsweise “%10” aussprechen mit “Register 2”.

Alle Register sind 8-bit Register. Das heißt man kann:

  • in jedes Register 8 Bits schreiben und

  • aus jedem Register 8 Bits auslesen.

Spezial-Register %00

Das Register %00 (also “Register 0”) ist ein besonderes Register (special purpose register). Es ist ein sogenanntes Zero-Register, das eigentlich gar nicht existiert. Man kann es aber scheinbar wie die anderen Register benutzen, dabei verhält es sich dann so:

  • Schreibt man in das Register etwas, dann wird das ignoriert.

  • Liest man etwas aus dem Register, dann bekommt man immer Null, also 00 00 00 00.

Wozu das gut sein kann ist zunächst wahrscheinlich nicht klar. Aber es ist billig so ein Register zu verbauen.

Arbeitsregister

Der Vollständigkeit halber sei erwähnt, dass alle anderen Register keine Spezial-Register sind, sondern Arbeitsregister (oder general purpose register).

Addierer/Subtrahierer

Die ALU hat einen Addierer/Subtrahierer mit dem man zwei Register addieren oder subtrahieren kann und das Ergebnis in ein drittes Register schreiben kann. Man kann also beispielsweise folgende Operationen durchführen:

  • Addiere %01 mit %10 und schreibe das Ergebnis in %11 oder

  • Subtrahiere %01 von %10 und schreibe das Ergebnis in %11.

Wir wissen aus den vorigen Session was mit der Addition oder Subtraktion von Bitmustern gemeint ist. Die Bitmuster können als Unsigned-Integer oder Signed-Integer interpretiert werden. Und da mit dem Zweierkomplement gearbeitet wird, kann die Addition/Subtraktion für beide Fälle “gleichzeitig” durchgeführt werden. Und natürlich kann es bei beiden Fällen zu Überläufen kommen.

Notation für die Interpretation von Bitmuster

Damit sich besser Ausdrücken lässt was nun gerechnet wird und wie ein Bitmuster interpretiert wird führen wir eine mathematische Notation ein. Ihr werdet aber sehen, dass die Notation nur das formal beschreibt was zuvor bereits anschaulich mit dem Einheitskreis erklärt wurde. Aber wie so oft in der Mathematik wollen wir das was anschaulich klar ist mit Formeln erschlagen:

Ist \(X = x_{n-1}\dots x_0\) ein \(n\)-stelliges Bitmuster, dann bezeichnet

  • \(u(X)\) die Interpretation als Unsigned-Integer Wert. Formaler kann dies mit

    \[u(x_{n-1}\dots x_0) = \sum\limits_{k=0}^{n-1} x_k \cdot 2^k\]

    ausgedrückt werden.

  • \(s(X)\) die Interpretation als Signed-Integer Wert. Formaler (aber vielleicht zunächst un-intuitiv) kann dies mit

    \[s(x_{n-1}\dots x_0) = -2^{n-1} \cdot x_{n-1} + \sum\limits_{k=0}^{n-2} x_k \cdot 2^k\]

    ausgedrückt werden. Idee hinter der Formel: Man Unterteil den Einheitskreis in \(2^n\) Segmente, denen man Zahlen zuordnet und dabei geht man so vor:

    • Beginnt ein Bitmuster mit Null, also \(x_{n-1} = 0\), dann ist es eine nicht-negative Zahl. Und es gilt

      \[s(0 x_{n-2}\dots x_0) = \sum\limits_{k=0}^{n-2} x_k \cdot 2^k = 2^{n-2} \cdot x_{n-2} + \dots + 2 \cdot x_1 + x_0.\]

      Man beginnt beim Einheitskreis bei “0 Grad” an zu zählen und beginnt mit der Zahl 0.

    • Beginnt ein Bitmuster mit Eins, also \(x_{n-1} = 1\), dann ist es eine negative Zahl. Und es gilt

      \[s(1 x_{n-2}\dots x_0) = -2^{n-1} + \sum\limits_{k=0}^{n-2} x_k \cdot 2^k = -2^{n-1} + 2^{n-2} \cdot x_{n-2} + \dots + 2 \cdot x_1 + x_0.\]

      Man beginnt beim Einheitskreis also bei “180 Grad” an zu zählen und beginnt mit \(-2^{n-1}\).

Überzeugt euch, dass ihr so in beiden Fällen die Zahlen auf dem Einheitskreis erhaltet wie in Session 5. Und dass beispielsweise gilt:

  • Bei 4-stelligen Bitmustern ist \(u(1111) = 15\) und \(s(1111) = -1\).

  • Bei 8-stelligen Bitmustern ist \(u(1111 1111) = 255\) und \(s(1111 1111) = -1\).

Wozu ist das gut? Beschreibung der Addition

Man kann jetzt formal beschreiben was bei der Operation “Addiere %01 mit %10 und schreibe das Ergebnis in %11” wirklich passiert. Und dies wie folgt ausdrücken:

\[(u(\texttt{%01}) + u(\texttt{%10})) \bmod 2^8 \to u(\texttt{%11})\]

Das ist so zu lesen:

Register %11 wird bei der Addition zu verändert, dass danach

\[(u(\texttt{%01}) + u(\texttt{%10})) \bmod 2^8 = u(\texttt{%11})\]

gilt.

Beispiel dazu:

  • Ist %01 = 00 00 00 10 also \(u(\texttt{%01}) = 2\) und

  • ist %10 = 11 11 11 11 also \(u(\texttt{%10}) = 255\) dann ist

  • \(u(\texttt{%01}) + u(\texttt{%10}) = 257\) und

  • \((u(\texttt{%01}) + u(\texttt{%10})) \bmod 2^8 = 1\).

Also muss in %11 ein 8-stelliges Bitmuster \(X\) eingetragen werden, so dass \(u(X) = 1\) gilt. Das ist gerade das Bitmuster 00 00 00 01.

Beschreibung der Addition

Analog kann beschreiben werden, dass bei der Operation “Subtrahiere %01 von %10 und schreibe das Ergebnis in %11” folgendes passiert:

\[(-u(\texttt{%01}) + u(\texttt{%10})) \bmod 2^8 \to u(\texttt{%11})\]

Beachtet, dass das bei “Subtrahiere ... von ...” der erste Operand vom zweiten abgezogen wird, weshalb das Minuszeichen hier vor dem ersten Operanden steht.

Statusregister

Wir haben im Abschnitt Addierer/Subtrahierer nur beschrieben nach welchen Regeln im Ziel-Register (also das Register rechts vom Pfeil) ein Bitmuster erzeugt wird. Wenn man es genau wissen will, die Regel für das Rechnen mit \((\mathbb{Z}/2^8 \mathbb{Z})\) bezüglich der Addition und Subtraktion.

Was uns aber eigentlich interessiert ist, ob das was man gerechnet hat auch für das Rechnen mit ganzen Zahlen verwenden kann, oder ob es dann Überläufe gab. Und dazu haben wir ja beim letzten mal das Statusregister behandelt. Das Statusregister hat vier Flags, von denen ihr zwei schon kennt.

CF (Carry Flag)

Gilt bei der Operation “Addiere %01 mit %10 und schreibe das Ergebnis in %11”

\[(u(\texttt{%01}) + u(\texttt{%10})) \bmod 2^8= u(\texttt{%01}) + u(\texttt{%10})\]

dann wird CF=0 gesetzt, da das Ergebnis als Unsigned-Integer dargestellt werden kann (es gab keinen Überlauf). Ansonsten wird CF=1 gesetzt.

Im Allgemeinen Fall kann man die Register mit X, Y, Z als Platzhalter bezeichnen und dann gilt:

  • Nach der Operation "Addiere `%X` mit `%Y` und schreibe das Ergebnis in `%Z` wird CF wie folgt gesetzt:

    \[\text{CF} = 0\quad\Leftrightarrow \quad(u(\texttt{%X}) + u(\texttt{%Y})) \bmod 2^8 =u(\texttt{%X}) + u(\texttt{%Y})\]

  • Nach der Operation "Subtrahiere `%X` von `%Y` und schreibe das Ergebnis in `%Z` wird CF wie folgt gesetzt:

    \[\text{CF} = 0\quad\Leftrightarrow \quad(-u(\texttt{%X}) + u(\texttt{%X})) \bmod 2^8 =-u(\texttt{%X}) + u(\texttt{%Y})\]

Beachtet, dass es für das Setzten von CF egal ist in welches Register das Ergebnis geschrieben wird. Das liegt daran, dass das Ergebnis im Akkumulator (und nicht das vom Ziel-Register) ausgewertet wird.

OF (Overflow Flag)

Bei der Operation “Addiere %01 mit %10 und schreibe das Ergebnis in %11” werde ich mit \(\text{Akku}\) das Bitmuster beschreiben, das im Akkumulator erzeugt wird (damit vermeide ich es \((\dots) \bmod 2^8\) für negative Zahlen definieren zu müssen).

Dann ist die Regel: Gilt

\[s(\text{Akku}) = s(\texttt{%01}) + s(\texttt{%10})\]

dann wird OF=0 gesetzt, da das Ergebnis als Signed-Integer dargestellt werden kann (es gab keinen Überlauf). Ansonsten wird OF=1 gesetzt.

Im Allgemeinen Fall kann man wieder die Register mit X, Y, Z als Platzhalter bezeichnen. Außerdem wird mit \(\text{Akku}\) wieder das Bitmuster im Akkumulator bezeichnet.

  • Nach der Operation "Addiere `%X` mit `%Y` und schreibe das Ergebnis in `%Z` wird OF wie folgt gesetzt:

    \[\text{CF} = 0\quad\Leftrightarrow \quad(s(\text{Akku}) = s(\texttt{%X}) + s(\texttt{%Y})\]

  • Nach der Operation "Subtrahiere `%X` von `%Y` und schreibe das Ergebnis in `%Z` wird CF wie folgt gesetzt:

    \[\text{CF} = 0\quad\Leftrightarrow \quad(s(\text{Akku}) = s(-\texttt{%X}) + s(\texttt{%Y})\]

ZF (Zero Flag) und SF (Sign Flag)

Diese zwei Flags sind neu, aber einfach erklärt:

  • Wenn das Ergebnis (im Akkumulator) nur aus Nullen besteht, dann wird ZF=1 gesetzt, sonst wird ZF=0 gesetzt.

    Der Zweck ist der, dass man mit ZF prüfen kann, ob beispielsweise eine Differenz Null war.

  • Wenn das Ergebnis (im Akkumulator) mit links mit einer Eins beginnt, also das Bit mit dem höchsten Index (most significant bit, dann wird SF=1 gesetzt. Und ansonsten SF=0.

    Das ist nur nützlich, wenn man mit Signed-Integern rechnet. Dann kann man hier das Vorzeichen des Ergebnisses ablesen.