Vom Halbaddierer zum von-Neumann-Rechner

Bis hierher stehen zwei Dinge nebeneinander: Rechnen mit Dualzahlen auf der einen Seite, Gatter und Schaltterme auf der anderen.

Dieses Kapitel verbindet beides. Aus zwei Gattern wird ein Halbaddierer, aus zwei Halbaddierern ein Volladdierer, aus mehreren Volladdierern ein Rechenwerk, das ganze Zahlen addiert.

Und dann kommt der Schritt, der aus einer Rechenmaschine einen Computer macht. Er besteht nicht aus mehr Bauteilen, sondern aus einer Idee: Das Programm steht im selben Speicher wie die Daten. Was daraus folgt, prägt jeden Rechner bis heute.

Vorausgesetzt werden die Gatter und die DNF aus Schaltalgebra, die Dualaddition aus Rechnen mit Dualzahlen sowie EVA-Prinzip, Prozessor, Speicher und Bus aus Aufbau von Informatiksystemen.

Neu ist, wie beides zusammenhängt: Wie werden aus Gattern Rechenwerke, und wie wird aus einem Rechenwerk ein Computer?

Gesucht ist eine Schaltung, die zwei Bits addiert. Ergebnis sind zwei Bits: die Summe $s$ und der Übertrag $c$.

Die letzte Zeile ist der interessante Fall: $1 + 1 = 10_2$, also Summe 0 mit Übertrag 1.

Jetzt wendet man einfach das Verfahren aus dem vorigen Kapitel an, für jede Ausgangsspalte einzeln.

Für $s$: Einsen in den Zeilen $01$ und $10$, also

$$s = (\bar{a} \land b) \lor (a \land \bar{b}) = a \oplus b$$

Das ist genau XOR.

Für $c$: Eine Eins in Zeile $11$, also

$$c = a \land b$$

Der ganze Halbaddierer besteht damit aus einem XOR- und einem AND-Gatter. Bemerkenswert daran ist nicht die Schaltung, sondern der Weg: Niemand musste sie sich ausdenken. Die Tabelle stand fest, das DNF-Verfahren lieferte den Rest.

Warum „halb"?

Der Halbaddierer hat nur zwei Eingänge. Beim schriftlichen Addieren mehrstelliger Zahlen kommt aber an jeder Stelle außer der ersten noch der Übertrag der vorigen Stelle hinzu:

  1 1 1        ← Überträge
  0 1 1 1
+ 0 0 1 1
---------
  1 0 1 0

An der zweiten Stelle sind drei Bits zu addieren: $1$, $1$ und der eingehende Übertrag $1$. Der Halbaddierer kann das nicht; er reicht nur für die niederwertigste Stelle. Daher der Name.

Der Volladdierer hat drei Eingänge: $a$, $b$ und den eingehenden Übertrag $c_{\text{ein}}$. Ausgänge sind wieder Summe $s$ und ausgehender Übertrag $c_{\text{aus}}$.

Man liest die Tabelle als Abzählen: $s$ ist 1, wenn eine ungerade Anzahl der Eingänge 1 ist; $c_{\text{aus}}$ ist 1, wenn mindestens zwei Eingänge 1 sind. Die zweite Bedingung kennst du bereits aus dem vorigen Kapitel.

Statt die DNF aufzustellen, baut man ihn aus zwei Halbaddierern:

a ──┐
    ├─[HA 1]─ s1 ──┐
b ──┘        c1    ├─[HA 2]─ s   (Summe)
                   │
c_ein ─────────────┘   c2

c_aus = c1 OR c2

Warum das stimmt: Der erste Halbaddierer addiert $a + b$ und liefert die Zwischensumme $s_1$ und den Übertrag $c_1$. Der zweite addiert dazu $c_{\text{ein}}$ und liefert die endgültige Summe $s$ und einen zweiten Übertrag $c_2$.

Ein ausgehender Übertrag entsteht, wenn bei einer der beiden Additionen einer aufgetreten ist, also $c_{\text{aus}} = c_1 \lor c_2$. Dass niemals beide zugleich auftreten, sieht man so: Liefert der erste Halbaddierer $c_1 = 1$, so waren $a = b = 1$ und damit $s_1 = 0$; der zweite Halbaddierer addiert dann $0 + c_{\text{ein}}$ und kann keinen Übertrag erzeugen.

Schaltet man $n$ Volladdierer hintereinander und verbindet jeweils $c_{\text{aus}}$ mit dem $c_{\text{ein}}$ des nächsten, entsteht ein Addierwerk für $n$-stellige Dualzahlen:

 a3 b3      a2 b2      a1 b1      a0 b0
  │  │       │  │       │  │       │  │
 ┌┴──┴┐     ┌┴──┴┐     ┌┴──┴┐     ┌┴──┴┐
 │ VA │←────│ VA │←────│ VA │←────│ HA │
 └──┬─┘     └──┬─┘     └──┬─┘     └──┬─┘
    s3         s2         s1         s0

An der niederwertigsten Stelle genügt ein Halbaddierer, weil dort kein Übertrag hereinkommt.

Damit ist der Bogen geschlagen: Aus einem Gattertyp entsteht über DNF ein Halbaddierer, daraus ein Volladdierer, daraus ein Rechenwerk. Und weil im vorigen Kapitel gezeigt wurde, dass sich Subtraktion, Multiplikation und Division auf Addition und Verschieben zurückführen lassen, kann dieses Werk alle vier Grundrechenarten.

Eine Grenze zeigt sich hier bereits: Der Übertrag muss von rechts nach links durchlaufen, bevor die letzte Stelle stimmt. Bei 64 Bit summieren sich diese Laufzeiten. Deshalb benutzen echte Prozessoren aufwendigere Bauformen, die den Übertrag vorausberechnen; das Prinzip bleibt aber dasselbe.

Ein Addierwerk allein ist noch kein Computer. Frühe Rechenmaschinen wurden für jede neue Aufgabe umgesteckt; die Verkabelung war das Programm, und ein Wechsel dauerte Tage.

1945 formulierte John von Neumann das Prinzip, das das beendete:

Programm und Daten stehen im selben Speicher. Ein Befehl ist ein Bitmuster wie jedes andere.

Die Architektur besteht aus fünf Teilen:

Rechenwerk und Steuerwerk zusammen bilden den Prozessor. Verbunden ist alles über Busse: Adressbus (wohin?), Datenbus (was?), Steuerbus (lesen oder schreiben?).

Du erkennst das EVA-Prinzip aus Klasse 9 wieder, nun aber mit der entscheidenden Ergänzung, wo das Programm steht.

Das Steuerwerk wiederholt unablässig denselben Ablauf:

1. Holen. Der Befehlszähler enthält die Adresse des nächsten Befehls. Der Befehl wird aus dem Speicher geladen. 2. Entschlüsseln. Das Steuerwerk erkennt, welche Operation gemeint ist. 3. Ausführen. Rechenwerk oder Speicher führen aus. 4. Befehlszähler erhöhen und von vorn beginnen.

Ein Sprungbefehl verändert einfach den Befehlszähler. Genau daraus entstehen Verzweigungen und Schleifen: Eine Wiederholung ist nichts anderes als ein Sprung zurück auf eine frühere Adresse, verbunden mit einer Bedingung.

Die Speicherung des Programms als Daten hat weitreichende Konsequenzen:

Ein Programmwechsel ist ein Speicherinhalt, kein Umbau. Derselbe Rechner leistet Textverarbeitung und Bildbearbeitung.

Programme können Programme verarbeiten. Übersetzer lesen Quelltext und schreiben Maschinencode, beides sind Daten. Ohne dieses Prinzip gäbe es keine Programmiersprachen im heutigen Sinn. Auch der Halteproblem-Beweis aus der theoretischen Informatik lebt genau davon, dass ein Programm ein Programm als Eingabe nimmt.

Es gibt keinen Schutz von Natur aus. Wenn Befehle und Daten ununterscheidbar sind, kann eine zu große Eingabe Speicher überschreiben, in dem Befehle stehen. Genau darauf beruht eine ganze Familie von Angriffen. Heutige Systeme markieren Speicherbereiche deshalb ausdrücklich als „nicht ausführbar", aber das ist eine nachträgliche Absicherung und keine Eigenschaft der Architektur.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Weil Befehle und Daten denselben Speicher und denselben Bus benutzen, können sie nicht gleichzeitig übertragen werden. Der Prozessor wartet also regelmäßig auf den Speicher. Das nennt man den von-Neumann-Flaschenhals.

Er ist über die Jahrzehnte schärfer geworden, denn Prozessoren wurden weit schneller als Speicher. Ein heutiger Prozessorkern kann in der Zeit eines einzigen Hauptspeicherzugriffs mehrere hundert Rechenschritte ausführen.

Gegenmaßnahmen:

• Zwischenspeicher (Cache) direkt im Prozessor, klein und sehr schnell.
• Getrennte Busse für Befehle und Daten (Harvard-Architektur), verbreitet in Mikrocontrollern und innerhalb moderner Prozessoren.
• Mehrere Kerne und Fließbandverarbeitung, um Wartezeiten zu überbrücken.

🔴 Beachte, dass keine dieser Maßnahmen das Prinzip aufhebt. Sie mildern die Folgen. Die von-Neumann-Architektur ist deshalb kein überholtes Modell, sondern die Grundlage praktisch jedes heutigen Rechners, ergänzt um Technik, die ihre bekannteste Schwäche abfedert.