Hier ist das Script für die Vorlesung Informatik 2. Zum Ausdrucken benutzen Sie die Print-Funktion an Ihrem Browser, mit den Standard-Einstellungen werden ca. 90 Seiten gedruckt.
Dies ist Version 3 vom 10.2.98. Es ist die für die Klausur relevante Version.
In diesem Abschnitt werden Boolesche Funktionen und deren Darstellung durch Schaltkreise definiert.
x y | AND(x,y) x y | OR(x,y) x | NOT(x) ------------------- ------------------ ------------ 0 0 | 0 0 0 | 0 0 | 1 0 1 | 0 0 1 | 1 1 | 0 1 0 | 0 1 0 | 1 1 1 | 1 1 1 | 1Weitere Beispiele sind (für jedes n) die folgenden n-stelligen Funktionen:
x y z | f(x,y,z) --------------------- 0 0 0 | 0 0 0 1 | 1 0 1 0 | 0 0 1 1 | 1 1 0 0 | 0 1 0 1 | 0 1 1 0 | 1 1 1 1 | 1
Es gibt 2 0-stellige Funktionen, nämlich die beiden konstanten Funktionen 0 und 1, und es gibt folgende 4 1-einstellige Funktionen:
x | 0 id NOT 1 ---------------------- 0 | 0 0 1 1 1 | 0 1 0 1Es gibt folgende 16 2-stelligen Funktionen:
x y | f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 -------------------------------------------------------------------------- 0 0 | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 | 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 | 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1Neben f2 = AND und f8 = OR haben auch die folgenden Funktionen spezielle Namen (die restlichen auch, aber die werden nicht gebraucht): f7 heißt EXOR oder "Parity", f9 heißt NOR, f10 heißt "Äquivalenz", und f15 heißt NAND.
Der folgende Satz zeigt, daß die Anzahl der Booleschen Funktionen abhängig von der Stelligkeit enorm wächst. Schon für n=9 gibt es mit 2512 mehr Boolesche Funktionen der Stelligkeit 9 als z.B. Atome im Universum.
Satz Es gibt 2(2n) verschiedene Boolesche Funktionen der Stelligkeit n.
Beweis: Die Anzahl der Abbildungen einer Menge X in eine Menge Y ist |Y||X|. Weil X = Bn 2n Elemente hat, ergibt sich die Behauptung 1.1.
Ein Schaltkreis ist eine Komposition aus Variablen und Gattern: Alle Eingänge von Gattern (jeweils ein oder zwei) werden mit 0 oder1, mit Variablen oder mit Ausgängen von anderen Gattern verbunden. Wichtig ist, daß dabei keine Zyklen auftreten, d.h. es darf keine Gatter G1,...,Gn geben, so daß ein Eingang von G1 mit dem Ausgang von G2 verbunden ist, ein Eingang von G2 mit dem Ausgang von G3 verbunden ist, usw., und ein Eingang von Gn mit dem Ausgang von G1 verbunden ist. Zusätzlich wird verlangt, daß es genau ein Gatter gibt, dessen Ausgang nicht mit dem Eingang eines anderen Gatters verbunden ist, dieses Gatter heißt das Ergebnisgatter des Schaltkreises.
Bemerkung. Die Definition ist nicht ganz formal. Man kann sie voll formalisieren, indem man Schaltkreise als auf die folgende Weise als markierte, gerichtete, zyklenfreie Graphen mit genau einer Senke definiert. Ein endlicher, gerichteter, markierter Graph ist ein Tripel (K,E,M), wobei die Menge K endlich und nichtleer ist und Menge der Knoten heißt, E eine Teilmenge des Produkts K x K ist (d.h. E besteht aus Paaren (x,y) mit x und y aus K) und heißt Menge der Kanten, und M eine Abbildung von K in eine Menge L ist, M heißt dabei Markierung und L heiß Menge der labels. Die Menge der labels ist im Fall von Schaltkreisen die Vereinigung der Menge der Variablen V={x1,x1,...} und der Menge {AND, OR, NOT, 0,1}. Der in-degree eines Knotens k ist die Anzahl aller Kanten (x,y) mit y=k, der out-degree eines Knotens k ist die Anzahl aller Kanten (x,y) mit x=k. Ein Graph heiß korrekt markiert, falls die Markierung folgende Eigenschaft erfüllt: Wenn der label M(k) eines Knotens k eine Variable oder 0 oder 1 ist, dann hat k in-degree 0, d.h. keine Kante führt zu ihm. Wenn der label M(k) = NOT ist, dann hat k in-degree 1, d.h. genau eine Kante führt zu ihm. Und wenn M(k) gleich AND oder OR ist, dann hat k in-degree 2, d.h. genau zwei Kanten führen zu ihm. Ein Graph heißt zyklenfrei, falls es keine Knoten k1, k2, ..., kn gibt, so daß die Paare (k1,k2), k2, k3),..., (kn-1,kn), und (kn,k1) Kanten in ihm sind, d.h Elemente aus E sind. Eine Senke ist ein Knoten mit outdegree 0. Hier ist die formale Definition für einen Schaltkreis: Ein Schaltkreis ist ein endlicher, gerichteter, korrekt markierter Graph, der zyklenfrei ist und genau eine Senke hat.
Ein Schaltkreis mit n Eingabevariablen definiert auf folgende Weise eine Boolesche Funktion auf den Eingabevariablen: ein Eingabevektor (a1,...,an) aus Bn wird an die Eingabevariablen (in der Reihenfolge ihrer Benennung) gelegt und die Gatter werden in Richtung des Ergebnisgatters ausgewertet. Das Boolesche Wert am Ergebnisgatter ist der Funktionswert für die Eingabe a. Weil es keine Zyklen gibt, ist die Auswertung eindeutig. Der Schaltkreis oben stellt z.B. folgende Boolesche Funktion dar.
a b c | z --------------- 0 0 0 | 0 0 0 1 | 1 0 1 0 | 1 0 1 1 | 1 1 0 0 | 0 1 0 1 | 1 1 1 0 | 1 1 1 1 | 1
Wichtig für das Verständnis: Schaltkreise sind keine Booleschen Funktionen (sondern mathematisch gesehen letztendlich Graphen), sondern stellen Boolesche Funktionen nur da! - wie zum Beispiel Folgen von Ziffern wie "26" oder "1997" keine Natürlichen Zahlen sind sondern nur Natürliche Zahlen darstellen. Oder wie zum Beispiel der Ausdruck "x2+y" keine zweistellige reele Funktion ist sondern eine solche nur darstellt.
Die Größe eines Schaltkreises ist definiert als die Anzahl seiner Gatter. Die Höhe eines Schaltkreises ist die Länge des längsten Weges von einer Variablen zum Ergebnisgatter, gezählt werden dabei die passierten Gatter. Daß die Größe ein wichtiges Kriterium fü einen Schaltkreis ist, ist klar. Aber in der Praxis ist auch die Höhe ein wichtiges Kostenkriterium, denn sie vergrößert die maximale Signallaufzeit. Je größer diese Signallaufzeit ist, desto langsamer muß ein Prozessor getaktet werden, denn jeder Takt muß die Ergebnisauswertung abwarten.
Der fanout (gleich out-dergree, s.o.) eines Gatters G in einem Schaltkreis ist die Anzahl der Gatter, die mit dem Ausgang von G verbunden sind. Ein Schaltkreis heißt Boolesche Formel falls alle Gatter außer dem Ergebnisgatter (das hat definitionsgemäß fanout 0) fanout 1 haben. Eine Boolesche Formel kann man in Klammerschreibweise notieren, z.B. ((x AND y) OR (NOT x)). Das funktioniert nicht mit allgemeinen Schaltkreisen: wenn an einer Stelle der fanout größer als 1 ist, kann man das nicht mit Klammern dastellen ( - versuchen Sie es! - natürlich ohne Kopien zu produzieren!). Vereinbarung: Die leere Formel () entspreche dem Schaltkreis (x AND (NOT x)) und definiere damit die Konstant-0-Funktion.
Zwei Schaltkreise heißen äquivalent, falls sie die gleiche Boolesche Funktion darstellen. Natürlich läßt sich jeder Schaltkreis in eine äquivalente Boolesche Formel umwandeln, z.B. indem folgenden Schritt iteriert solange, bis alle gatter fanout 1 haben: Nimm ein Gatter G mit fanout n > 1 und kopiere das Gatter G und den Schaltkreis darunter (n-1)-fach; diese n einzelnen Schaltkreise an die n Gatter hängen, die einen Eingang haben, der mit dem Ausgang von G verbunden ist. Allerdings produziert das Verfahren bei gewissen Schaltkreisen exponentiell große Boolesche Formeln. Es ist eines der interessantesten offenen Probleme der Theoretischen Informatik, ob es ein polynomielles Verfahren für die Umwandlung von Schaltkreisen in Boolesche Formeln gibt (das ist das P/poly versus NC1 Problem).
Ein Literal ist eine Formel der Form x oder NOT(x), also entweder eine Variable oder eine negierte Variable. Eine Klausel sei eine Boolesche Formel der Form (L1 AND ... AND Lm), wobei jedes Li ein Literal ist. Die AND's sind ohne Klammern geschrieben, weil die Funktion (wie auch die OR Funktion) assoziativ ist. Eine Boolesche Formel ist eine sogenannte DF-Formel (d.h. eine Formel in disjunktiver Form), falls sie von der Form C1 OR ... OR Cn ist, wobei jedes Ci eine Klausel ist. Ein Beispiel ist die Formel (x AND NOT(z)) OR y OR (x AND NOT(y) AND z).
Spezielle DF-Formeln sind die Formeln in DNF-Form, d.h. in disjunktiver Normalform. Bei Ihnen sind alle Klauseln verschieden und in jeder Klausel kommen alle Variablen genau einmal vor. Beispiel (das ist die EXOR-Funktion): (x AND NOT(y)) OR (NOT(x) AND y). Die DNF-Formel für eine Booleschen Funktion ist - abgesehen von der Reihenfolge - eindeutig.
DNF-Formeln sind spezielle DF-Formeln, diese sind spezielle Formeln, und diese sind wiederum spezielle Schaltkreise. Wir zeigen, daß jedes dieser vier Konzepte in der Lage ist, alle Booleschen Funktionen darzustellen. Das ist nicht selbstverständlich: für Klauseln gilt das beispielsweise nicht, z.B. ist die zweistellige OR-Funktion nicht als Klausel darstellbar.
Satz Jede Boolesche Funktion ist durch eine Formel in DNF darstellbar.
Beweis. Sei f eine n-stellige Boolesche Funktion. Wenn f die Konstant-0-Funktion ist, ist f durch die leere Formel () darstellbar. Ansonsten betrachten wir das Urbild f-1(1). Es sei a = (a1,...,an) ein Element dieses Urbilds, d.h. f(a1,...,an) = 1. Definiere Ca als die Klausel L1 AND ... AND Ln mit Li = xi falls ai = 1 und Li = NOT(xi) falls ai = 0. Die von Ca dargestellte Boolesche Funktion hat genau bei der Eingabe a den Wert 1. Die Funktion f wird also von der DNF-Formel Ca1 OR ... OR Can dargestellt, wobei a1,...,an die Urbilder von 1 unter f sind. Zum Beispiel hat die Multiplexer-Funktion "if x then y else z", siehe oben, folgende DNF-Formel:
(NOT (x) AND NOT (y) AND z ) OR (NOT (x) AND y AND z ) OR ( x AND y AND NOT(z)) OR ( x AND y AND z )
Korollar Jede Boolesche Funktion ist durch einen Schaltkreis darstellbar.
Es bleibt die Frage, warum vier verschiedene Konzepte (Schaltkreise, Formeln, DF-Formeln und DNF-Formeln) eingeführt werden, die alle die dieselben mathematischen Objekte beschreiben, nämlich die Booleschen Funktionen. Der Grund ist, daß DNF-Formeln und DF-Formeln zwar mathematisch einfacher zu handhaben sind, aber Formeln (und eventuell Schaltkreise) von Menschen im Allgemeinen besser gelesen und entworfen werden können. Außerdem können Formeln und Schaltkreise manche Booleschen Funktionen komprimierter darstellen. Bemerkung. Z.B. gibt es einen Schaltkreis mit weniger als 260 Gattern, der die 64-stellige Parity-Funktion darstellt, aber jede DF-Formel für diese Funktion enthät mindestens die Klauseln der DNF-Formel - und das sind 232 Klauseln der Länge 64 - und hat damit mehr als 200 Millarden Gatter.
Eine Klausel C heißt Implikant einer Booleschen Funktion f, falls bei jeder Belegung der Variablen, die die Klausel C erfüllt, auch f den Wert 1 hat. Beispiel: Jede Klausel der DNF-Formel einer Booleschen Funktion f ist Implikant von f. Anderes Beispiel: x AND y ist Implikant von if-then-else(x,y,z).
Eine Klausel C heißt Primimplikant von einer Booleschen Funktion f falls C Implikant von f ist, aber jede Verkürzung von C um ein oder mehr Literale kein Implikant mehr ist. Beispiele: x AND y AND (NOT(z)) ist nicht Primimplikant von if-then-else(x,y,z), denn die Verkürzung x AND y ist Implikant von f. Und x AND y ist tatsächlich Primimplikant von f, denn die Formeln x und y (die bestehen jeweils nur aus einer Variablen) sind beides keine Implikanten von if-then-else(x,y,z).
Wenn in einer Formel in disjunktiver Form zwei Klausel C, D gleich sind bis auf Reihenfolge und bis auf jeweils ein Literal, das in der einen Formel x und in der anderen NOT(x) ist, dann kann man die beiden Klauseln C und D streichen und anstattdessen die Klausel hinschreiben, die aus C bzw. D entsteht, wenn man das Literal x bzw. NOT(x) streicht. Die entstandende Formel ist immer noch in disjunktiver Form und stellt immer noch die gleiche Boolesche Funktion dar, hat aber eine Klausel und ein Literal weniger. Diese Operation soll matching genannt werden. Matching entspricht also dem Gesetz, daß (x AND y) OR (x AND (NOT(y))) äquivalent ist zu x.
Das Verfahren von Quine-McClusky berechnet die Menge aller Primimplikanten PI(f) einer Booleschen Funktion f mithilfe iterierten matchings. Es funktioniert folgendermaßen. Sei f n-stellig. Dann sei Qn die Menge aller Klauseln der DNF-Darstellung von f. Finde alle Paare von Klauseln aus Qn, die zu matchen sind. Sei Qn-1 die Menge aller Klauseln, die durch solche matchings entstanden sind, und sei Pn-1 die Menge aller Klauseln aus Qn, für die es keine andere Klausel aus Qn zum Matchen gab. Bilde aus Qn-1 auf die gleiche Art die Mengen Qn-2 und Pn-2, etc., solange bis irgendwann Qi leer ist. Ausgegeben wird dann als Ergebnis die Menge aller Primimplikanten PI(f) als die Vereinigung aller Pi.
Beispiel. Sei f die Funktion if-then-else(x,y,z). Dann ist Q3 die Menge {(NOT(x)) AND (NOT(y)) AND z, (NOT(x)) AND y AND z, x AND y AND (NOT(z)), x AND y AND z}. Zu matchen ist jetzt z.B. (x AND y AND (NOT(z))) zusammen mit (x AND y AND z) zu (x AND y). Es ergibt sich, daß Q2 = {(NOT(x)) AND z, x AND y, y AND z} und P2 = {}. In Q2 gibt es keine Paare mehr zum Matchen, d.h., das Verfahren bricht ab und gibt als Ergebnis P1 = {(NOT(x)) AND z, x AND y, y AND z} aus.
Sei f eine Boolesche Funktion. Die Formel in disjunktiver Form, die durch die Primimplikanten von f als Klauseln bestimmt ist, stellt f dar. Diese Formel ist im Allgemeinen kürzer als die DNF-Form. Deshalb ist das Verfahren von Quine-McClusky eine Möglichkeit, zu einer DNF-Formel eine kürzere Formel in disjunktiver Form zu finden. Das obige Beispiel zeigt aber schon, daß das Verfahren nicht die kürzeste Formel in disjunktiver Form findet, denn die beiden Primimplikanten ((NOT(x)) AND z) und (x AND y) reichen zur Darstellung der if-then-else-Funktion in disjunktiver Form schon aus. Allgemein gilt, daß alle Klauseln der kürzesten Darstellung in disjunktiver Form Primimplikanten sein müssen (das kann man sich leicht klar machen), aber welche Teilmenge der Primimplikanten das ist, muß man durch Ausprobieren herausfinden (Bemerkung: Diese Teilmenge aus einer gegebenen Menge von Primimplikanten herauszufinden, ist ein NP-hartes Problem, siehe Vorlesung Informatik 1). Das Verfahren von Quine-McClusky ist also nur der erste Schritt zum Finden der kürzesten DF-Formel. Es sollte auch beachtet werden, daß es Boolesche Funktionen gibt, für die es keine kürzere DF-Form als die DNF-Form gibt, eine Beispiel ist die Parity-Funktion, siehe oben. Das Verfahren von Quine-McClusky nützt hier also nichts. Außerdem sollte erwähnt werden, daß es hier nur um das Finden von kürzeren Formeln in disjunktiver Form geht. Das Finden von kürzeren Formeln (nicht unbedingt in disjunktiver Form) oder Schaltkreisen ist also ein ganz anderes und noch schwierigeres Problem.
Man kann die OR-Funktion mithilfe der AND- und NOT-Funktion darstellen, und umgekehrt kann man die AND-Funktion durch die OR- und NOT-Funktion darstellen
Satz (Gesetz von de Morgan)
Diese Vereinbarung wird wegen der besseren Lesbarkeit von Schaltkreisen getroffen. Wenn es jedoch darum geht, die Größe oder die Tiefe eines Schaltkreises zu messen, wird nur eine Darstellung mithilfe von AND, OR und NOT zugelassen (es sei denn, es denn wird etwas anderes vereinbart). Man nennt eine Menge von Booleschen Funktionen vollständig, wenn man mit ihnen als Gatter-Funktionen jede Boolesche Funktion durch einen Schaltkreis mit diesen Gattern darstellen kann. Deshalb ist nach dem obigen Korollar aus 1.3 zum Beispiel die Menge {AND, OR, NOT} vollständig. Überraschend ist, daß es auch ein-elementige vollständige Mengen gibt.
Satz. Die folgenden Mengen von Booleschen Funktionen sind vollständig (das sind nur Beispiele, es gibt noch mehr):
Beweis. Die Vollständigkeit von {AND, NOT} ergibt sich nach dem Gesetz von de Morgan aus der Vollständigkeit von {AND, OR, NOT}, denn man ersetzt jedes OR-Gatter durch einen entspechenden Sub-Schaltkreis aus AND- und NOT-Gattern. Genauso ergibt sich die Vollständigkeit von {OR, NOT}. Die Vollständigkeit von {NAND} ergibt sich aus der von {AND, NOT}: zuerst ersetzt man alle AND(x,y) durch NOT(NAND(x,y)) und dann alle NOT(x) durch NAND(x,x). Analog ergibt sich die Vollständigkeit von {NOR}.
Bemerkung. Eine theoretisch interessante vollständige Menge ist {EXOR, AND,1}, wobei 1 die 0-stellige Konstant-1-Funktion ist. Die Vollständigkeit ergibt sich aus der von {AND, NOT}: man ersetzt NOT(x) durch EXOR(1,x). Diese Operationen entsprechen der Addition (EXOR) und Multiplikation (AND) im Körper mit zwei Elementen {0,1}. Interessant ist außerdem, daß hier sogar die DF-Form (mit EXOR statt OR) eindeutig ist, siehe das Buch von Oberschelp/Vossen.
x2 x1 x0 | y2 y1 y0 ------------------------------ 0 0 0 | 0 0 1 0 0 1 | 0 1 0 0 1 0 | 0 1 1 0 1 1 | 1 0 0 1 0 0 | 1 0 1 1 0 1 | 1 1 0 1 1 0 | 1 1 1 1 1 1 | 0 0 0Eine Schaltnetz ist definiert wie ein Schaltkreis, nur daß in ihm nicht nur ein Ergebnisgatter sondern m Ergebnisgatter als solche definiert sind. Ein Schaltnetz mit n Eingabevariablen und m Ergebnisgattern definiert offensichtlich eine m-wertige n-stellige Boolesche Funktion. Die Begriffe Größe und Höhe übertragen sich von Schaltkreisen auf Schaltnetze. Da jede m-wertige Boolesche Funktion in ihre m Komponenten zerlegbar ist, gilt das folgende Korollar aus Korollar 1.3.
Korollar Jede mehrwertige Boolesche Funktion ist durch einen Schaltnetz darstellbar.
Der Vorteil eines Schaltnetzes mit m Ergebnisgattern gegenüber m Schaltkreisen (die haben jeweils ein Ergebnisgatter) ist natürlich, daß gemeinsame Sub-Schaltungen nur einmal gebaut werden müssen. Diesen "Synergie-Effekt" sollte man also bei der Konstruktion von Schaltnetzen zu nutzen versuchen.
Der Additionsalgorithmus für Binärzahlen funktioniert ganz analog zum Grundschul-Algorithmus für die Addition von Dezimalzahlen: Anstatt den Algorithmus zu beschreiben, wird ein Beispiel angegeben:
3859650695 Erster Summand
+ 939402223 Zweiter Summand
----------------
101100010 Übertrag
----------------
= 4799052918 Ergebnis
Und jetzt ein analoges Beispiel für Binärzahlen:
1110101010 Erster Summand
+ 10001100 Zweiter Summand
----------------
1110001000 Übertrag (oder carry-bit)
----------------
= 10000110110 Ergebnis
Zur Kontrolle: der erste Summand beschreibt die Zahl 938, der zweite die Zahl
140, und deren Summe ist tatsächlich die Zahl 1078.
Ebenso wie der Additionsalgorithmus ist auch der Multiplikationsalgorithmus für Binärzahlen ganz analog zum Grundschul-Algorithmus für die Multiplikation von Dezimalzahlen:
4206 x 307
----------------
12618 (= 3 x 4206)
00000 (= 0 x 4206)
29442 (= 7 x 4206)
----------------
= 1291242
Und für Binärzahlen:
1101 x 1010
-----------------
1101 (= 1 x 1101)
0000 (= 0 x 1101)
1101 (= 1 x 1101)
0000 (= 0 x 1101)
-----------------
= 10000010
Kontrolle: 13 mal 10 ist tatsächlich 130. An dem Beispiel wird übrigens
klar, daß die binäre Multiplikation noch einfacher ist als
die dezimale, denn die Zwischen-Berechnung mit einer einstelligen Dezimalzahl
(wie oben z.B. 3 x 4206)
fällt quasi weg: entweder wird als Summand eine Kopie des linken Faktors genommen
oder der Summand besteht nur aus 0'en. Dieser Effekt wurde schon in der
Übungsaufgabe 2.4 genutzt.
Anstatt mit beliebig großen Binärzahlen wird auf einem Computer tatsächlich nur mit Binärzahlen modulo einer Zahl 2m gerechnet. Das liegt daran, daß für Zahlen nur eine bestimmte Anzahl von Stellen (nämlich m viele) reserviert werden. Zum Beispiel kann man mit vier Stellen a4, a3, a2, und a1 nur bis 15 rechnen: 0000 beschreibt die Zahl 0, 0001 die Zahl 1, 0010 die Zahl 2, etc, und 1111 beschreibt die Zahl 15. Addition und Multiplikation ist ebenfalls modulo 2m definiert. Im Beispiel für m=4 ist also 15 + 1 = 0, 8 + 13 = 5, oder 7 x 5 = 3. Da meistens jedoch m = 32 oder größer ist, werden die Zahlen, die im Alltag auftauchen, korrekt verarbeitet. Außerdem kann man zum Beispiel zwei 32-bit-Zahlen als eine 64-bit-Zahl auffassen, man muß dann aber natürlich bei der Verarbeitung aufpassen (das kommt in einem späteren Abschnitt dran).
Bei einer Darstellung an...a3a2a1 modulo 2n heißt an das höchste bit oder auch einfach das linke bit, und a1 das niedrigste bit oder einfach das rechte bit.
Wie üblich in der Algebra wird das Element, das zu einem Element a hinzuaddiert das neutrale Element ergibt, als das zu a inverse Element -a bezeichnet. Modulo 2n bleibt die 0 das neutrale Element der Addition. Allerdings ergibt sich aus der allgemeinen Definition, daß modulo 2n die Zahl 2n - a genau das inverse Element zu einer Zahl a ist, also gleich -a modulo 2n . Z.B. ist 13 = -3 modulo 24, denn 13 + 3 = 16 = 0 modulo 24. Beim Aufschreiben von relativen Sprungaddressen in Abschnitt 4 wird diese Notation benutzt werden.
Diese Funktion soll durch ein Schaltnetz realisiert werden. Nach Korollar 1.6 wissen wir, daß ein solches Schaltnetz (nämlich die komponentenweise DNF-Formel) existiert. Die ist allerdings schon für n = 8 viel zu groß. Wir werden zuerst den Grundschul-Algorithmus für die Addition in ein Schaltnetz umsetzen. Dazu brauchen wir die folgende 2-wertige 3-stellige Funktion, die wir einen Volladdierer nennen.
a b c | ü r (Summe dezimal) ---------------------------------------------- 0 0 0 | 0 0 0 0 0 1 | 0 1 1 0 1 0 | 0 1 1 0 1 1 | 1 0 2 1 0 0 | 0 1 1 1 0 1 | 1 0 2 1 1 0 | 1 0 2 1 1 1 | 1 1 3Ein Volladdierer berechnet als Ausgabe die Binädarstellung der Summe der drei Eingabe-bits, das ü ist deren höchstes bit und steht für den Übertrag. Ein Volladdierer wird zum Beispiel durch folgendes Schaltnetz realisiert.
Mit einen Volladdierer können wir den Grundschul-Algorithmus für die Addition in einem Schaltnetz nachbauen:
Das Schaltnetz ist einfach zu verstehen und braucht relativ wenig Gatter. Allerdings ist das Schaltnetz sehr hoch, denn der Weg von Eingang a0 führt über n Volladdierer zum Ergebnisgatter rn, und jeder Volladdierer hat dabei selber Höhe 2 oder 3. Eine Idee dafür, das Schaltwerk zu verflachen, ist, die carry-bits flacher zu berechnen. In Übungsaufgabe 1.3 hatten Sie gesehen, daß man durch einen baum-artigen Aufbau eines Schaltkreises Höhe sparen kann. Diese Idee soll auch auf die carry-bit-Berechnung übertragen werden. Die folgende 2-wertige 4-stellige Boolesche Funktion wird carry-look-ahead "cla" genannt.
Die Funktion ist so zu verstehen: x (bzw. y oder z) steht für ein definitives carry, das sich im linken Teil der (im rechten Teil der, in der gesamten) Eingabe ergibt, während x' (bzw. y' oder z') für ein carry-bit steht, das sich ergeben würde, wenn noch ein zusätzliches carry-bit von jeweils ganz rechts in die Rechnung hineinkäme. Die folgende Schaltung macht diese vage Erklärung eventuell etwas klarer. Der Ausgang ü der Schaltung berechnet das letzte carry-bit (also das höchste bit) der Addition von zwei 4-bit Binärzahlen a3a2a1a0 und b3b2b1b0. Mit anderen Worten, ü zeigt an, ob die Summe der beiden Zahlen größer ist als 15.
Eine carry-look-ahead-Schaltung für längere Eingaben baut man dann in Baum-Form. Für Eingaben mit 2-mal 32 bit braucht man z.B. einen Baum von cla-Moduln der Höhe 5, wobei jedes cla-Modul Schaltnetz-Höhe 3 hat, d.h. die Gesamt-Schaltung hat Höhe (3x5)+1 = 16. Das ist besser als die Höhe 4 x 32 = 128 der Schaltung mit den Volladdieren (ein Volladdierer hat nach der angegebenen Realisierung Höhe 4 - das EXOR muß dort noch ersetzt werden).
Es wurde also gezeigt, wie man das letzte carry-bit (d.h. das höchste bit) einer Addition mit einem flachen Schaltkreis berechnen kann. Für die anderen carry-bits, z.B. das an der vorletzten Stelle, kann man im Prinzip die gleiche Methode verwenden und dabei - bei geschickter Anordnung - Schaltnetz-Teile gemeinsam nutzen, die Höhe wird dabei größer.
Die quasi-unäre Darstellung einer Zahl i modulo 2n ist die, die aus 2n 0'en besteht außer an der (i+1)-ten Stelle, wo anstattdessen eine 1 steht. (Die unäre Darstellung (ohne "quasi") einer Zahl i hat im Gegensatz dazu i hintereinanderstehende 1'en plus eventuell führende 0'en) Z.B. haben die Zahlen 0 bis 7 folgende quasi-unäre Darstellungen modulo 23 = 8:
Zahl binäre Darstellung quasi-unäre Darstellung (unäre Darstellung
modulo 8 modulo 8 modulo 8)
0 000 10000000 0000000
1 001 01000000 0000001
2 010 00100000 0000011
3 011 00010000 0000111
4 100 00001000 0001111
5 101 00000100 0011111
6 110 00000010 0111111
7 111 00000001 1111111
Ein n-bit-Decodierer verwandelt die binäre Darstellung einer Zahl modulo
2n in die quasi-unäre Darstellung um. D.h., ein n-bit-Decodierer
ist ein Schaltnetz mit n Eingängen und 2n Ausgängen:
Realisiert wird ein n-bit-Decodierer am einfachsten, indem für jeden Ausgang dessen DNF-Formel gebildet wird, denn die besteht jeweils nur aus einer Klausel.
Ein n-bit-Multiplexer ist ein Schaltkreis mit 2n + n Eingaben x0,...,x2n-1, an-1,...,a0.
Die Funktionalität ist folgende: Es sei a die durch an-1...a0 dargestellte binäre Zahl. Dann ist das Ergebnis des Schaltkreises identisch mit dem Wert am Eingang xa, mit anderen Worten: xa wird "durchgeschaltet". Ein 1-bit-Multiplexer mit Eingaben x0, x1, a0 stellt zum Beispiel die Funktion if-then-else(a0, x1,x0) dar. Ein n-bit-Multiplexer ist mit einem n-bit-Decodierer leicht zu realisieren:
Ein (n x m)-bit-Multiplexer hat sogar (2n x m) + n Eingänge x0,m-1, ..., x0,0, ..., x2n-1,m-1, ..., x2n-1,0, an-1, ..., a0, und und m Ausgänge rm-1, ..., r0. Er schaltet genau die durch die Binärzahl a = an-1...a0 bestimmten Eingänge xa,m-1,...,xa,0 gleichzeitig nach rm-1,...,r0 durch, d.h. rm-1 = xa,m-1, ..., und r0 = xa,0.
Realisiert wird der nxm-Multiplexer durch m verschiedene Multiplexer, die allen den gleichen Decodierer benutzen.
Mit einer Schreibmaschine (oder der Tastatur eines Computers) kann man ca. 90 verschiedene Zeichen schreiben. Mit sieben bits könnte man also die Zeichen einer Schreibmaschine kodieren, denn 27 = 128. Tatsächlich nimmt man aber für die Codierung von Buchstaben 8 bits, das achte bit wird entweder für Sonderzeichen benutzt oder es dient zum error-check, siehe unten. Eine solche Kombinationen von acht 0'en und 1'en nennt man eine Byte, mit anderen Worten: ein Byte sind acht bit. Die Vorsilben Kilo-, Mega-, Giga-, und Tera- haben bei Bytes (und bits) eine leicht andere Bedeutung als im metrischen System: Ein KiloByte (KB oder KByte) sind nicht 1000 sondern 1024 Bytes, d.h. 210 Bytes. Ebenso sind ein MegaByte (MB oder MByte), ein GigaByte (GB oder GByte) und ein TeraByte als 220 Bytes, 230 Bytes, bzw. 240 Bytes definiert, also nicht genau, sondern nur ungefähr als eine Million, als eine Milliarde bzw. als eine Billion Bytes. Der Grund für diese vom metrischen System (leicht) abweichende Definition ist folgender: Meistens sind es Speicherbausteine, deren Größ gemessen werden soll. Weil die meisten Speicherbausteine RAM's sind (siehe oben), sind ihre Zeilen mit einer bestimmten festen Anzahl von bits zu addressieren. Ein RAM mit Adressen der Länge 20 bit und Zeilen der Breite 8 bit hat, hat z.B. die Größe 1 MegaByte = 8 Mega-bit.
Von Bytes statt von bits zu sprechen hat den Vorteil, daß man die Größ einer Information in die bekannte Informationseinheit Buchstabe übersetzen kann. Wenn man davon ausgeht, daß eine Schreibmaschinen-Seite ca. 80 Spalten und 50 Zeilen hat, dann hat eine Schreibmaschinenseite ungefähr 4 KiloByte ( = 32 Kilo-bit) Information. Damit wären ein MegaByte ca. 250 Schreibmaschinen-Seiten, das ist schon eine dickere Diplomarbeit.
Darüberhinaus ist es aus verschiedenen Gründen üblich, innerhalb eines Computers Informationen in Bytes oder ganzen Vielfachen von Bytes darzustellen. In dieser Vorlesung werden wir z.B. den Beispiel-Rechner auf Informationen mit 32 bits (gleich 4 Bytes) rechnen lassen.
Die beiden Nachteile der obigen Codierung sind, daß (1) bei mehr als einem Fehler der Empfänger die Fehlerhaftigkeit eventuell nicht erkennt, und daß (2) er bei genau einem Fehler zwar weiß, daß ein bit falsch übertragen wurde, er aber nicht weiß, welches. Nachteil (1) könnte man durch weitere Zusatz-bits z.B. auf eine Fehlererkennung von 2 Fehlern hochschrauben. Darauf soll aber nicht weiter eingegangen werden. Anstattdessen soll eine Möglichkeit zur Fehler-Korrektur besprochen werden.
Wir haben folgendes Szenario: Es sollen 8 bit Information übertragen werden. Dabei hat die Übertragung ein solchen Grad von Zuverlässigkeit, daß es mit sehr geringer Wahrscheinlichkeit vorkommen kann, daß unter sagen wir 100 bits ein bit falsch übertragen wird, aber ein zweifacher Fehler praktisch ausgeschlossen werden kann (Wahrscheinlichkeiten multiplizieren sich). Durch eine Codierung der 8-bit Information mit zusätzlichen bits soll der Empfänger die Möglichkeit haben, nicht nur zu erkennen, daß es einen Fehler gegeben hat, sondern diesen auch zu korrigieren, d.h. an der richtigen Stelle eine 0 in eine 1 umzuschreiben bzw. eine 1 in eine 0.
Eine simple Lösung ist folgende: Sende die 8 bits dreimal hintereinander. Wenn alle 3 Bytes gleich sind, ist kein Fehler aufgetreten, ansonsten gibt es zweimal ein Byte B und einmal ein um ein bit davon verschiedenes Byte B'. Nimm B, denn B' ist falsch.
Diese simple Lösung braucht also 16 Zusatz-bits. Anstatt die simple Lösung noch hier und da zu verbessern, soll gleich eine optimale Lösung präsentiert werden, die sich ein Herr Hamming schon 1950 ausgedacht hat: Es sind nur 4 Zusatz-bits nötig, d.h. die Gesamt-Nachricht besteht aus 12 bits b1,...,b12. Die Zusatz-bits sind die bits b1, b2, b4 und b8, die Orginal-Information steht in der Original-Reihenfolge in den restlichen 8 bits. Die Zusatz-bits sind wieder (wie oben) parity-bits, d.h. sie ergänzen eine Menge von bits um eine 1, wenn es eine gerade Anzahl unter diesen bits gibt, die den Wert 1 haben. Hier soll das Zusatz-bit b1 die Original-bits b3, b5, b7, b9 und b11 ergänzen, das Zusatz-bit b2 die Original-bits b3, b6, b7, b10, b11, das Zusatz-bit b4 die Original-bits b5, b6, b7, b12, und das Zusatz-bit b8 die Original-bits b9, b10, b11, b12. Die Methode dabei ist: Zusatz-bit b2i ergänzt Original-bit bj, wenn j in der Binärdarstellung an der i-Stelle von rechts eine 1 hat.
Beispiel: aus der Original-Information 10011101 wird die Nachricht 111000111101:
1 001 1101 111000111101
Der Empfänger bekommt die Nachricht und schaut nach, ob die vier parity-bits b1, b2, b4, b8 richtig sind. Es wird jetzt eine vierstellige Binärzahl c = c8c4c2c1 gebildet: Falls bi das korrekte parity-bit ist, dann sei ci gleich 0, ansonsten sei ci gleich 1.
Es sei vorausgesetzt, daß höchstens ein bit falsch übertragen worden ist. 1. Behauptung: Die Übertragung war fehlerfrei genau dann wenn c = 0. Beweis: Wenn kein bit falsch übertragen wurde, bleiben die parity-bits korrekt und c = 0. Sei umgekehrt genau ein bit bj falsch übertragen worden: wenn bj eins der vier Zusatz-bits ist, dann ist die parity-Bedingung nicht mehr erfüllt, und c ist 1,2,4, oder 8, aber nicht 0. Wenn bj ein Original-bit ist, sind alle Zusatz-bits, zu deren parity-Berechnung bj beiträgt, falsch. Weil es mindestens eins (sogar mindestens zwei) davon gibt, ist c ungleich 0. 2. Behauptung: Wenn genau ein Fehler aufgetreten ist, dann in bit bc der Nachricht (mit anderen Worten: c zeigt auf das Fehler-bit). Beweis: Die Argumentation aus der ersten Behauptung wird verfeinert: Wenn ein Zusatz-bit bj falsch übertragen wurde, dann sind die Original-bits unverändert und damit sind die anderen drei Zusatz-bits korrekt. Das heißt, daß c in der Binärdarstellung genau ein 1 hat, und bei unserer Numerierung ist c = j. Wenn eins der Original-bits bj falsch übertragen wurde, so wird das genau die Zusatz-bits einen falschen parity-Wert berechnen lassen, zu deren Berechnung es beiträgt. Beispiele: Wenn b6 falsch übertragen wird, sind b2 und b4 als parity-Werte falsch, wenn b7 falsch übertragen wird, sind b1, b2, b4 als parity-Werte falsch. Bei unserer Festlegung (siehe Skizze) ergibt sich: c = j.
Der Empfänger liest also die Nachricht, berechnet c und dreht den Wert in bit bc um (b0 existiert nicht!). Unter der Annahme, daß maximal ein Fehler aufgetreten ist, hat er die korrekte Nachricht.
Generell kann man mit dieser Methode mit log(n) vielen Zusatz-bits n bit lange Nachrichten gegen maximal einen Übertragungsfehler sichern. Es gibt natürlich auch Methoden zur Korrektur von mehr Fehlern, das ist ein eigenes mathematisches Forschungsgebiet geworden.
Die Funktionalität des flip-flop's ist von ganz anderer Art als die der anderen Grundbausteine: die Aufgabe eines flip-flops ist, die Information (also entweder eine 0 oder eine 1), die am Eingang anliegt, für genau einen Takt zu speichern und dabei an seinen Ausgang abzugeben.
Ein Schaltwerk ist definiert wie ein Schaltkreis, nur daß jetzt zusätzlich die flip-flops wie die NOT-Gatter als 1-stellige Bausteine benutzt werden können und daß die Bedingung, daß keine Zyklen auftreten dürfen, abgeschwächt wird zu der Bedingung, daß jetzt zwar Zyklen auftreten dürfen aber jeder Zyklus ein flip-flop enthalten muß. Bei den folgenden Beispielen überprüfe man, daß jeder Zyklus ein flip-flop enthält.
Ein flip-flop ist immer in einem Zustand 0 oder 1 und dieser Zustand ist als Boolescher Wert am Ausgang des flip-flops für die nachfolgenden Bausteine ablesbar. Bei einem neuen Takt wird der Boolesche Wert, der am Eingang des flip-flop anlag, zum neuen Zustandswert des flip-flop's. Der Takt ist für alle flip-flops in einem Schaltwerk der gleiche. Die Verbindung zu dem Taktgeber ist durch das kleine Dreieck im flip-flop Symbol angedeutet, die Verbindung und der Taktgeber sind aber nicht eingezeichnet, weil das ja keine zusätzlich Information liefert.
Ein Beispiel eines Schaltwerks mit einem flip-flop und ohne Eingänge ist folgender sogenannter 1-bit-Zähler:
Angenommen, das flip-flop hat beim Takt n den Wert 0. Wegen des Negationsgatters liegt (noch in dem gleichen Takt) am Eingang des flips-flops eine 1 an. Beim nächten Takt t+1 wird also dieser Wert am Eingang zum Wert des flip-flop's: das flip-flop hat also im Takt n+1 den Wert 1, und in dem gleichen Takt wird noch der Wert am Eingang des flip-flop's zu 0. Beim Takt n+2 hat also das flip-flop wieder den Wert 0, beim Takt n+3 den Wert 1, usw.
Wem das Beispiel wegen seiner Einfachheit zu irritierend ist, hier ist ein 2-bit-Zaehler mit zwei flip-flops.
Angenommen, beide flip-flops f1 und f0 haben beim Takt n den Wert 0. In dem Takt bleibt der Wert am Eingang von f1 EXOR(0,0)=0 auf 0. In dem Takt wird bekommt allerdings wie oben der Eingang von f0 den Wert 1. Also haben die beiden flop-flops f1 und f0 im Takt n+1 die Werte 0 bzw. 1. Man rechne aus, daß im Takt n+2 f1 unf f2 die Werte 1 bzw. 0 haben, im Takt n+3 beide den Wert 1 haben, und beide in Takt n+4 wieder den Wert 0 haben, wie in der Ausgangsposition. Die Zustände der flip-flops als Vektoren ohne Klammern geschrieben rotieren also in der Reihenfolge ..., 00, 01, 10, 11, 00,... usw. Als Dualzahlen gesehen wird also genau modulo 4 gezählt: ..., 0, 1, 2, 3, 0, ... usw.. Deshalb heiß die Schaltung auch 2-bit-Zähler (die 2 steht für die Anzahl der beteiligten flip-flops oder anders ausgedückt: die 2 ist das n, so daß 2n = 4).
Nach diesen Überlegungen sollte klar sein, was ein n-bit-Zähler ist: es ist ein Schaltwerk mit n flip-flops fn-1, ..., f0, so daß die Vektoren der flip-flops-Zustände hintereinander geschrieben als W(fn-1) ... W(f0) nacheinander die Binärzahlen modulo 2n darstellen. Mit anderen Worten: Wenn die n flip-flops im Takt n die Binärzahl i modulo 2n darstellen, dann sollen sie im Takt n+1 die Binärzahl i+1 modulo 2n darstellen. Damit haben wir auch schon die Realisierung eines n-bit-Zählers: man nimmt die n-bit-Increment Schaltung aus Übungsaufgabe 2.3:
Ein Beispiel für ein Schaltwerk mit Ein- und Ausgängen ist das 1-bit-Register, das durch ein einfaches Rechteck symbolisiert wird. Es hat 2 Eingänge x und load und einen Ausgang y, der den Zustand des 1-bit-Registers wiederspiegelt. Wenn load auf 0 ist, ändert sich der Zustand der Registers nicht. Wenn load auf 1 liegt, bekommt das Register den Wert, der an Eingang x anliegt. Ein Register ändert also im Gegensatz zum flip-flop also seinen Wert im Normalfall (load = 0) nicht, sondern nur, wenn eine Zustands-Änderung explizit durch load = 1 befohlen wird.
Ein n-bit-Register hat n+1 Eingänge und n Ausgänge. Es ist eine Reihe von 1-bit-Registern, die alle den gleichen load-Eingang habe. Ein n-bit-Register ändert seinen Wert im Normalfall (load = 0) nicht, und wenn eine Zustands-Änderung explizit durch load = 1 befohlen wird, wird die n-bit-Information als Ganzes ersetzt.
Ein weiteres Beispiel für ein einfaches Schaltwerk ist ein n-bit-Schieberegister: Es hat einen Eingang und einen Ausgang und n flip-flops f1, ..., fn, so daß bei jedem neuen Takt f1 seinen Wert aus dem Eingang erhält und seinen alten Wert an f2 weitergibt Ebenso gibt f2 seinen Wert an f3 weiter, usw., und der Wert von fn ist am Ausgang abzulesen.
Bei einem Ring-Schieberegister ist der Ausgang mit dem Eingang kurzgeschlossen:
Es werden für ein Schieberegister übrigens gar keine logischen Gatter gebraucht.
Durch einfache graphische Umordnung aller flip-flops eines Schaltwerks in eine Reihe erhält man folgende Ansicht eines Schaltwerks:
Man mache sich klar, daß die Bedingung, daß jeder Zyklus ein flip-flop enthalten muß, garantiert, daß der obere Teil wirklich ein zyklenfreies Schaltnetz ist.
Ein Schaltwerk ist also im Prinzip ein Schaltnetz mit einer Teilmenge von Eingangsvariablen, die rückgekoppelt sind. Diese alternative Sicht eines Schaltwerks bringt auch sofort die mathematische Definition dessen, was ein Schaltwerk "tut":
Eine Schrittfunktion ist ein Paar (f,g), so daß f eine n+k-stellige, n-wertige und g eine n+k-stellige, m-wertige Boolesche Funktion ist . Die von einem Schaltwerk mit n flip-flops, k Eingängen, und m Ausgängen berechnete Schrittfunktion ist das Paar (f,g), wobei f die (n+k)-stellige, n-wertige Boolesche Funktion ist, die von dem Schaltnetz an den Ausgängen y1,...,yn in der obigen Darstellung berechnet wird, und g die (n+k)-stellige, m-wertige Boolesche Funktion ist, die an den Ausgängen yn+1,...,ym.
Wenn ein Schaltwerk keine Eingänge hat (d.h., k=0), ist die Defintion der r-ten Iteration (fr,gr) einer Schrittfunktion (f,g) einfach: f1 = f, g1 = g, und fr+1 (x1,...,xn) = f(fr (x1,...,xn)), und gr+1 (x1,...,xn) = g(fr (x1,...,xn)). Wenn das Schaltwerk Eingänge hat, muß bei der Definition der iterierten Schrittfunktion die ganze Liste von Eingaben beachtet werden, die jemals während der verschiedenen Iterationen eingegeben worden sind. Das macht die Definition so aufwendig, daß sie hier weggelassen wird.
Als abschließendes Beispiel für ein Schaltwerk wird der Grundschul-Algorithmus für die Addition von Binärzahlen implementiert: Es sei das folgende Schaltwerk (keine Ein- und Ausgänge) mit 3n+1 flip-flops an-1, ..., a0, bn-1, au, rn, ..., r1 gegeben (VA ist ein Volladdierer, siehe voriger Abschnitt):
In den flip-flops ai, bi seien zwei n-stellige Binärzahlen a und b als Werte kodiert (wie bei den Zählern oben). Dann steht in den flip-flops ri nach genau n Taktschlägen die Kodierung der Summe a+b. Die Schaltung hat gegenüber den zwei Additions-Schaltnetzen aus dem letzten Abschnitt den Vorteil, daß die Größe und die Höhe ihres Schaltnetzes sehr klein ist; das ist praktisch nur der eine Volladddierer. Allerdings braucht sie n Taktschläge, während das Schaltnetz keinen braucht. Außerdem muß noch ein Zähler eingebaut werden, der nach genau n Takten das Ergebnis abliest.
Die Funktionalität ist die folgende. An den Ausgaben rm-1,...,rm-1 ist der Inhalt der durch die Binärzahl a = an-1,...,an-1 bestimmten Zeile des RAM. Die Information in den 2n Zeilen des RAM ändert sich beim Taktschlag normalerweise nicht, es sein denn, enable hat den Wert 1: in dem Fall wird die Information in der durch a bestimmten Zeile zu wm-1,...,w0. Die folgende Realisierung eines RAM macht die Funktionalität noch einmal deutlich (der Decodierer, der implizit in der (n x m)-bit-Multiplexer Schaltung rechts enthalten ist, kann durch den Decodierer links ersetzt werden d.h. man braucht nur einen Decodierer).
Die obige Schaltung ist kein Schaltkreis, denn es gibt einen Zyklus: vom oberen NOR-Gatter zum oberen Eingang des unteren NOR-gatters und dann von dessen Ausgang zum unteren Eingang des oberen NOR-Gatters.
Die genaue Funktionsweise eines solches asynchronen Schaltnetzes ist mathematisch schwer zu definieren. Trotzdem soll einmal intuitiv argumentiert werden, daß das asynchrone Schaltnetz die Funktionsweise des flip-flops realisiert:
Der Takt-Eingang c sei auf 0. 1.Fall: x habe den Wert 0. Jetzt geht für eine kurze Zeit (Taktschlag) der Wert t auf 1. Dadurch schaltet das untere AND-Gatter auf 1, denn jetzt liegt von c eine 1 an und von x über die Negation auch eine 1. Das untere NOR-Gatter schaltet also unabhängig von seinen oberen Eingang auf 0, denn die eine 1 am unteren Eingang genügt bei einem NOR-Gatter für eine 0. durch diese hat das obere NOR-Gatter zwei Eingänge auf 0, der obere ist wegen x=0 auf 0. Also hat das obere NOR-Gatter den Wert 1. Diese 1 destabilisiert das untere NOR-gatter nicht, denn sein Wert war unabhängig von diesem Eingang. Es liegt also ein stabiler Zustand der Gatter vor. Wenn jetzt c wieder auf 0 zurückschaltet, geht zwar das untere UND-Gatter auf 0zurück, aber das untere NOR-Gatter bleibt auf 0, diesmal wegen der 1 am oberen Eingang. Der Zusatnd der NOR-Gatter bleibt also stabil. Und am Ausgang y steht genau der Wert, den x vor dem Taktschlag hatte. 2. Fall: x habe den Wert 1. Jetzt wird quasi spiegel-symmetrisch argumentiert, daß sich der Zustand der beiden NOR-Gatter während und auch nach dem taktschlag auf folgende Kombination stabilisiert: oberes NOR-gatter auf 1, uneteres auf 1. In beiden Fällen hat der Auzsgang nach dem Taktschalg genau den Wert, den x vorm Taktschlag hatte. D.h., die Schaltung realisiert ein flip-flop.
In diesem Abschnitt wird das sogenannte von-Neumannsche Rechner-Model vorgestellt, das schon ca. 1950 entwickelt wurde, aber trotzdem auch heutzutage noch das Grundprinzip der Architektur fast aller Computer beschreibt.
In der Praxis wird über die gleichen Leitungen (Schreib-/Lese-Bus genannt) gelesen und geschrieben. Das passt allerdings nicht in das hier vorgestellte mathmatische Konzept (denn eine Verbindung kann nur in eine Richtung Information weitergeben), und auß werden so zwei Prinzipien (Lesen und Schreiben) formal getrennt, die auch inhaltlich verschieden sind.
| Befehl | Parameter | Funktion | Code |
| ALU-Befehle: | |||
| ASSIGN | Ri Rj | Ri := Rj | 00000 |
| CLEAR | Ri | Ri := 0...0 | 00001 |
| ADD | Ri Rj Rk | Ri := Rj + Rk und F0:=carry | 00010 |
| INCREMENT | Ri | Ri := Ri + 1 | 00011 |
| DECREMENT | Ri | Ri := Ri - 1 | 00100 |
| COMPLEMENT | Ri | Ri := - Ri modulo 232 und F0 := carry | 00101 |
| NEGATE | Ri Rj | Ri := NOT(Rj) (bit-weise) | 00110 |
| AND | Ri Rj Rk | Ri := Rj AND Rk (bit-weise) | 00111 |
| OR | Ri Rj Rk | Ri := Rj OR Rk (bit-weise) | 01000 |
| RINGSHIFT-LEFT | Ri | Ri := ringweises Schieben von Ri nach links | 01001 |
| RINGSHIFT-RIGHT | Ri | Ri := ringweises Schieben von Ri nach rechts | 01010 |
| SET-RIGHT-BIT-0 | Ri | setze rechtes bit von Ri auf 0 | 01011 |
| SET-RIGHT-BIT-1 | Ri | setze rechtes bit von Ri auf 1 | 01100 |
| Sprung-Befehle: | |||
| JUMP | W | springe W Zeilen weiter | 01101 |
| IF-ZERO-JUMP | Ri W | springe W Zeilen weiter falls Ri = 0...0 | 01110 |
| IF-EQUAL-JUMP | Ri Rj W | springe W Zeilen weiter falls Ri = Rj | 01111 |
| IF-SMALLER-JUMP | Ri Rj W | springe W Zeilen weiter falls Ri kleiner als Rj | 10000 |
| IF-R-BIT-JUMP | Ri W | springe W Zeilen weiter falls rechtes bit von Ri = 1 | 10001 |
| IF-FLAG-JUMP | W | springe W Zeilen weiter falls F0 = 1 | 10010 |
| READ-PC | Ri | Ri := PC | 10011 |
| JUMP-ABSOLUTE | Ri | springe in Zeile Ri | 10100 |
| Hauptspeicher-Befehle: | |||
| LOAD | Ri W | Ri := W | 10101 |
| READ | Ri Rj | Ri := RAM(Rj) | 10110 |
| WRITE | Ri Rj | RAM(Rj) := Ri | 10111 |
| RELATIVE-READ | Ri W | Ri := RAM(W Stellen weiter) | 11000 |
| RELATIVE-WRITE | Ri W | RAM(W Stellen weiter) := Ri | 11001 |
| Sonstige Befehle: | |||
| STOP | stoppe Programmausführung | 11010 | |
| IDLE | tue nichts | 11011 bis 11111 |
Die Kurz-Beschriebungen der Befehle sind eigentlich schon eindeutig, hier werden sie noch weiter erläutert:
Zu den relativen Sprung-, Lese-, und Schreib-Befehlen, die ja jeweils aus zwei Wörtern bestehen: gezählt wird ab der Zeile mit dem Befehl, und nicht ab der darauffolgenden Zeile mit dem Parameter.
Ein Programm ist eine Folge von Befehlen. Weil Programme im Hauptspeicher des SIMPLE-Computers abgespeichert werden sollen, müssen die Befehle einschließlich Parameter also in 32-Wörter kodiert werden. Es werden alle Befehle ohne einen Parameter W in ein 32-bit-Wort kodieren werden, und die Befehle mit einem Parameter W in zwei 32-bit-Wörter. (Einen Befehl mit Parameter W kann man nicht in ein 32-bit-Wort kodieren, denn W hat ja selber schon diese Länge.) Die Kodierung ist folgendermaßen festgelegt. Die linken 5 bits eines 32-bit-Wortes codieren den Befehlstyp, in der Tabelle oben ist dieser willkürlich gewählte 5-bit-Code rechts eingetragen. Die nächsten 3 bits (also von rechts gezählt die bits Nr. 26,25,24) spielen keine Rolle. Wenn der Befehl einen Parameter Ri hat, dann codieren die nächsten 4 bits (also die bits Nr. 23,22,21,20) binär das Register i. Die nächsten 4 bits (also die bits Nr. 19,18,17,16) spielen keine Rolle. Wenn der Befehl einen Parameter Rj hat, dann codieren die nächsten 4 bits (also die bits Nr. 15,14,13,12) binär das Register j. Die nächsten 4 bits (also die bits Nr. 11,10,9,8) spielen keine Rolle. Wenn der Befehl einen Parameter Rk hat, dann codieren die nächsten 4 bits (also die bits Nr. 7,6,5,4) binär das Register k. Die letzten 4 bits (also die bits Nr. 3,2,1,0) spielen keine Rolle.
Beispiel: Das Wort 0001110011010100010101000000010 kodiert den Befehl ADD R13 R5 R0:
00011100110101000101011000000010
xxxxx xxxx xxxx xxxx
ADD R13 R5 R0
Wenn der Befehl noch zusätzlich einen Parameter W hat,
ist W durch das gesamte nächste Wort
gegeben.
Beispiel: Die beiden Wörter 10100100001101110101101001100010 00000000000000000000000000000011 kodieren zusammen untereinandergeschrieben den 2-Wort-Befehl IF-ZERO-JUMP R4 3:
10100100010001110101101001100010
xxxxx xxxx
IF- R4
ZERO-
JUMP
00000000000000000000000000000011
= 3
Die Kodierung ignoriert viele bits, es sollte z.B. klar sein, daß man
auch 256 Register durch diese Kodierung ansprechen könnte - die existieren
in unserem Modell allerdings nicht.
In dieser Kodierung steckt ein wenig Methode, wie wir später sehen werden,
allerdings sind die meisten Festlegungen willkürlich.
Programme sind also Folgen von 32-bit-Wörtern (genaugenommen können Programme auch aus verschiedenen jeweils zusammenhängenden Teilen bestehen, die über Sprung-Befehle verbunden sind). Beim Aufschreiben von und für Menschen werden aber die unkodierten Mnemos (wie z.B. ADD R13 R5 R0, oder noch lesbarer: R13 := R5 + R0) der Befehle benutzt.
Dabei wird noch zusätzlich die folgende Abkürzung benutzt: Bei den relativen Sprung- und den beiden relativen Schreib- und Lese-Befehlen wird bei einer großen Zahl 232 - x anstatt z.B. JUMP 232 - 5 gleich JUMP -5 geschrieben, denn das ist ja auch genau das, was man meint: Springe 5 Befehlszeilen zurück.
Zum Ausführen eines Maschinenprogramms wird dieses als zusammenhängender Block in den Hauptspeicher geschrieben. Das Register PC wird mit der Adresse des ersten Befehls geladen. Alle anderen Register und flags in der CPU werden auf 0 gesetzt. Für die anderen Zellen im Hauptspeicher wird diese Festlegung nicht getroffen, d.h. hier wird nicht vorausgesetzt, daß sie den Wert 0 haben.
Dann wird das Programm ausgeführt, d.h. die Befehle werden Schritt um Schritt ausgeführt. Außer bei den Sprung-Befehlen ist der nächste Befehl immer durch den nächsten Befehl im Hauptspeicher gegeben. Bei 1-Wort-Befehlen wird also eine Zeile im Hauptspeicher weitergegangen, und 2-Wort-Befehlen wird zwei Zeilen weitergegangen. Genauso verhält es sich bei bedingten Sprungbefehlen, wenn die Bedingung negativ ausfällt. Nur bei den unbedingten Sprungbefehlen und bei den bedingten Sprungbefehlen, bei denen die Bedingung positiv ausgewertet wird, wird in eine ganz andere Zeile gesprungen, nämlich in die jeweils spezifizierte. Wenn der STOP Befehl erreicht wird, wird die Ausführung des Programms abgebrochen (diesen STOP Befehl gibt es in realen Rechnern nicht).
LOAD R0 % gehe zur Zeile 256 im Hauptspeicher 256 READ R1 R0 % lese Zeile 256 INCREMENT R0 % gehe zur Zeile 257 READ R2 R0 % lese Zeile 257 WRITE R1 R0 % schreibe in Zeile 257 DECREMENT R0 % gehe zur Zeile 256 zurück WRITE R1 R0 % schreibe in Zeile 256 STOP2. Beispiel. Das folgende Programm schreibt die Summe der beiden Zeilen nach ihm in die dritte Zeile nach ihm. Auf diese Weise funktioniert das Programm unabhängig von der Stelle des Hauptspeichers, in die es geschrieben wird. Beim Beispiel 1 gab es ja eine Einschränkung.
READ-RELATIVE R1
8
READ-RELATIVE R2
7
ADD R3 R1 R2
WRITE-RELATIVE R3
5
STOP
% hier steht der erste Summand
% hier steht der zweite Summand
% hier ist der Platz für das Ergebnis
3. Beispiel. Hier ist ein Programm, das trotz STOP-Befehl nie abbricht (und nichts leistet).
JUMP 0 STOP4. Beispiel. Hier ist ein Programm, das den Inhalt W der Zeile nach ihm daraufhin untersucht, ob in W eine ungerade Anzahl von 1'en vorkommt. Im dem Fall soll die übernächste Zeile nach ihm den Wert 1, ansonsten den Wert 0 bekommen.
READ-RELATIVE R1 % lese W in R1 ein
32
LOAD R2 % setze einen Zaehler auf die Anzahl der bits
32
IF-R-BIT-JUMP %
10
IF-ZERO-JUMP R2 % Fall A: gerade Anzahl
16
RINGSHIFT RIGHT R1
DECREMENT R2
IF-R-BIT-JUMP
4
JUMP
-6
IF-ZERO-JUMP R2 % Fall B: ungerade Anzahl
13
RINGSHIFT RIGHT R1
DECREMENT R2
IF-R-BIT-JUMP
-12
JUMP
-6
CLEAR R3 % Ergebnis: gerade
WRITE-RELATIVE R3
10
JUMP
6
CLEAR R3 % Ergebnis: ungerade
INCREMENT R3
WRITE-RELATIVE R3
3
STOP
% hier steht W
% hier ist der Platz für das Ergebnis
5. Beispiel. Ein Programm, das seine ersten beiden Zeilen löscht.
READ-PC R0 CLEAR R1 WRITE R1 R0 INCREMENT R0 WRITE R1 R0 STOPDas Beispiel zeigt, daß man mit der Maschinensprache eine Menge "anstellen" kann, was man mit höheren Sprachen wie Pascal nicht machen kann.
Wie jedes Maschinenprogramm ist natürlich der folgende Programm-Text trotz Kommentaren schwer zu verstehen. An dem folgenden Beispiel für die Multiplikation von zwei 4-bit-Binärzahlen wird der genaue Algorithmus etwas klarer. Es sei 1001 x 1011 zu berechnen:
1101 x 1011
-----------------
1101 4. Addition
0000 3. Addition
1101 2. Addition
1101 1. Addition
-----------------
= 10001111
Die beiden Faktoren 1001 und 1011 werden in die Register R1 bzw. R2 geladen.
Die Register R3 und R4 werden beide auf 0000 gesetzt.
Dann wird wegen der 1 ganz rechts in R2 das Register R1 zu R3 inzuaddiert.
Dieses Ergebnis wird um eine Stelle in R3 nach rechts geschoben, das herausfallende
bit 1 wird in R4 geschoben, die anderen bits in R4 werden nach rechts geschoben.
Es kommt links in R3 eine 0 hinein, denn bei der Addition gab es keinen Übertrag.
Die Inhalte von R3 und R4 hintereinandergeschrieben nach der 1. Schleife sind also
also 0110 1000. Jetzt wird wieder R1 zu R3 hinzuaddiert,
denn auch das zweit-rechteste bit
von R2 ist 1. Hier entsteht tatsächlich ein Übertrag, und
nach dem Verschieben sind die Inhalte von R3 und R4 nach der
zweiten Schleife also 1101 1100. In der nächsten Schleife wird nicht addiert, denn
das dritt-niedrigste bit von R2 ist 0. Also wird nur verschoben und die Inhalte von
R3 und R4 sind nach dem 3. Schleifendurchlauf 0110 1110.
Im vierten und letzten
Schleifendurchlauf wird addiert, und es entsteht dabei ein Übertrag,
d.h. die Inhalte von
R3 und R4 sind nach dem 4. Schleifendurchlauf 1000 1111. Das ist das Ergebnis.
READ-RELATIVE R1
46
READ-RELATIVE R2
45
CLEAR R3
CLEAR R4
LOAD R5 % setze einen Zaehler fuer die Anzahl der bits
32
IF-R-BIT-JUMP R2 % hier ist der Anfang der Hauptschleife
4
JUMP
17
ADD R3 R3 R1
IF-R-BIT-JUMP R3
5
SET-RIGHT-BIT-0 R4 % rechte 0 in R3 nach R4 schieben
JUMP
3
SET-RIGHT-BIT-1 R4 % rechte 1 in R3 nach R4 schieben
IF-FLAG-JUMP
5
SET-RIGHT-BIT-0 R4 % Abschluss des Falls: carry = 0
JUMP
13
SET-RIGHT-BIT-1 R4 % Abschluss des Falls: carry = 1
JUMP
10
IF-R-BIT-JUMP R3 % Hier wird hingesprungen, falls gar nicht addiert wird
5
SET-RIGHT-BIT-0 R4
JUMP % Abschluss des Falls: keine Addition, 0 nach R4 schieben
5
SET-RIGHT-BIT-1 R4 % Abschluss des Falls: keine Addition, 1 nach R4 schieben
RINGSHIFT-RIGHT R4 % hier springen alle Faelle in jeder der 32 Runden hin
RINGSHIFT-RIGHT R3
RINGSHIFT RIGHT R2
DECREMENT R5
IF-ZERO-JUMP R5
4
JUMP % zurueck zum Anfang der Hauptschleife
-31
WRITE-RELATIVE R3
7
WRITE-RELATIVE R4
6
STOP
% hier steht der erste Faktor
% hier steht der zweite Faktor
% hier soll der linke Teil des Ergebnisses stehen
% hier soll der rechte Teil des Ergebnisses stehen
Die einfachste Datenstruktur, die das Zeigerkonzept verwendet, ist die einfach verkettete Liste.
Eine einfach verkettete Liste für Zahlen auf dem SIMPLE ist eine Folge von Paaren (a1, s1), (a2,s2), (a3 s1), ..., (an, sn) von 32-bit-Binärzahlen mit folgenden Eigenschaften: in Zeile a1 des RAM steht die Zahl a2, in Zeile a2 des RAM steht die Zahl a3, usw., und in Zeile an steht die erste 0 unter den ai (d.h. die 0 codiert sozusagen den Schluß der Liste, sie entspricht dem "nil" in Pascal). Die Binärzahl si ist der Inhalt der Zeile (ai + 1). Die si sind die eigentliche Information, die codiert werden soll: Die von der einfach verketteten Liste kodierte Folge von Zahlen ist die Folge s1, s2, ..., sn-1. Die Zahl sn (das ist also der Inhalt von Zeile 1) spielt keine Rolle. Beispiel. Die von der folgenden einfach verketteten Liste kodierte Folge von Zahlen ist die Folge 9, 5, 100, 8.
Beispielprogramm. Das folgende Programm berechnet die Summe modulo 232 aller Folgenelemente der einfach verkettete Liste von Zahlen, die durch die Adresse des ersten Elements in der Zeile hinter dem Programm angegeben ist, und schreibt diese Summe in die übernächste Zeile hinter dem Programm. (Dabei wird angenommen, daß wirklich eine einfach verkettete Liste vorliegt: es könnte auch sein, daß die abschließende 0 nie auftaucht - das nennt man eine einfach verkettete Ringliste.)
CLEAR R1
READ-RELATIVE R0
14
IF-ZERO-JUMP R0 % hier ist der Anfang der Schleife, bei R0 = 0 abbrechen
9
INCREMENT R0
READ R2 R0 $ lese si
ADD R1 R1 R2
DECREMENT R0
READ R0 R0 % hier ist der Punkt "Adressen = Daten"
JUMP
-7
WRITE-RELATIVE R1
4
STOP
% hier steht a1
% hier soll die Summe stehen
Listen sind das einfachste Beispiel für die Verwendung von Zeigern, Bäume sind ein etwas komplizierteres Beispiel: Im dem folgenden Beispiel hat ein binärer Baum 5 Knoten, die jeweils eine Zhal speichern. Jeder Knoten besteht aus 4 Hauptspeicher-Zeilen. In der ersten Zeile steht der Zeiger zum linken Unterbaum, in der zweiten der zum rechten Unterbaum, und in der dritten der Zeiger zum übergeordneten Baum. In der vierten Zeile steht die gepeicherte Zahl.
Die Blöcke mit den jeweils 4 Zeilen stehen im Hauptspeicher. Was hier als Zeiger dargestellt ist, ist letztendlich die 32-bit Adresse der ersten Zeile des Blocks, auf den gezeigt wird, ein nil entspricht der Adresse 0.
Für den im vorigen Abschnitt angegebenen Rechner wissen wir, wie er programmmiert wird. Ein wesentlicher Punkt dieser Vorlesung soll es aber sein, daß zusätzlich erklärt wird, wie er es schafft, die Maschinenbefehle so auszuführen, wie der Programmierer es sich vorstellt. Mit anderen Worten: der Rechner soll als Schaltwerk realisiert werden. Wie der RAM als Schaltwerk realisiert ist, ist schon bekannt, es bleibt also übrig, die CPU zu realisieren.
Die CPU für den Rechner SIMPLE ist in folgende Module unterteilt.
Das Register-Modul ist so ähnlich aufgebaut wie der RAM, allerdings kann es gleichzeitig an drei anzugebenden Registern unabhängig voneinander zwei Wörter lesen und eins schreiben, während im RAM nur an einer Adresse gelesen und geschrieben werden kann. Die drei Adressen werden durch die 3 mal 4 Eingänge i3, ..., i0, j3, ..., j0 und k3, ..., k0 binär beschrieben. Dabei stellt i3... i0 die Nummer des Registers dar, das überschrieben werden soll. Das Register wird nur überschrieben, falls der Eingang Ri-load auf 1 ist. In dem Fall wird die Information an den Eingängen Ri31, ..., Ri0 im darauffolgenden Takt in das angegebene Register geladen. Für das Lesen von Register-Inhalten können an den Eingängen j3, ..., j0 und k3, ..., k0 gleichzeitig zwei Register-Nummern festgelgt werden. An den Ausgängen Rj31, ..., Rj0 bzw. Rk31, ..., Rk0 kann dann der Inhalt der zwei Register gelesen werden. Dabei ist zu beachten, daß wie beim RAM das Lesen von Register-Inhalten noch im gleichen Takt erfolgt, während man natürlich für das Schreiben auf den nächsten Takt warten muß.
Noch ein Beispiel zur Funktionsweise des Register-Moduls: And den vier i-Eingänge steht die Binärzahl 7, an den j- und k-Eingängen stehen die Binärzahlen 2 bzw 0. Dann kann man im gleichen Takt t an den Ausgängen Rj31, ..., Rj0 und Rk31, ..., Rk0 die Werte des 2-ten bzw. 0-ten Registers lesen, und wenn Ri-load auf 1 ist, wird im nächsten Takt t+1 im Register 7 die Information stehen, die im Takt t an den Eingängen Ri31, ..., Ri0 anliegt.
Realisiert wird das Register-Modul ähnlich wie der RAM, und zwar mit Hilfe von einem 4-bit-Decodierer und zwei (4x32)-bit-Multiplexern, deren Adressierung unabhängig voneinander ist.
Die Bevor wir zum Steuer-Modul kommen, legen wir noch Folgendes fest: An die Eingängen der Module sollen Ausgänge von verschiedenen anderen Modulen geschaltet werden. Diese Eingänge sind die folgenden: i3, ..., i0, j3, ..., j0, k3, ..., k0, Ri-load, Ri31, ..., Ri0, w31, ..., w0, RAM-load, PC-in31, ..., PC-in0, PC-load, CB-in31, ..., CB-in0, CB-load, AR-in31, ..., AR-in0, AR-load, F0-in, F0-load, stop-in, stop-load. Jeder dieser Eingänge e soll ein mehrstelliges OR vorgeschaltet haben. An dieses OR werden dann alle Ausgänge gelegt, die in den folgenden Schaltungen mit e verbunden sind. Es wird garantiert werden, daß immer nur eine dieser verschiedenen Modul-Ausgänge a überhaupt auf 1 sein kann, und die anderen garantiert auf 0 sind. Damit hängt e zu dem Zeitpunkt nur von diesem einen Ausgang a ab, d.h. e ist auf 1 genau dann wenn dieser Ausgang a auf 1 ist.
Das Steuermodul ist das Kernstück der CPU, es ist folgendermaßen aufgebaut:
Die Funktionsweise des Steuermoduls ist folgende. Die Abarbeitung von Programmen wird unterteilt in den Modus "fetch", in dem der nächste auszuführende Befehl vom Hauptspeicher in die CPU geholt wird, und der Modus "execution", in dem der geholte Befehl ausgeführt wird. In welchem der beiden Modi sich die Steuereinheit befindet, wird durch das flip-flop exec verwaltet und angezeigt: Wenn das flip-flop exec auf 1 ist, dann ist die Steuereinheit im execution Modus, ansonsten im fetch Modus. Vereinbarungsgemäß haben in der CPU anfangs alle flip-flops den Wert 0, d.h. anfangs ist die Steuereinheit im fetch-Modus. Im fetch-Modus bekommt das fetch-Modul im oberen Teil der Zeichnung eine 1 an ihrem Eingang. Dadurch können die AND-Gatter die Information an den Eingängen r31,...,r0, PC-out31, ..., PC-out0 an die Ausgänge CB-in31,CB-in0, a31, a0 "durchschalten", und der Command Buffer wird durch CB-load=1 auf Laden geschaltet. Was passiert ist also, daß die Adresse im Register PC an die Adress-Ausgänge der CPU geht und somit eine Zeile im RAM ansteuert, deren Inhalt dann (in unserem Modell noch im gleichen Takt) an den Eingängen ri anliegt und von da über das fetch-Modul in das Register CB weitergegeben wird, das auf Laden gesetzt ist. Mit anderen Worten: tatsächlich wird der nächste Befehl in das Register CB geladen. Gleichzeitig kommen die rechten 5 r-Eingänge nicht nur in das register CB, sondern auch in den Decoder ganz links in der Zeichnung. Der Decoder finbdet noch im gleiche Takt heraus, um welchen der 32 SIMPLE-Befehle es sich bei dem neuen Befehl handelt. Der entsprechende Ausgang di wird auf 1 gesetzt (alle anderen auf 0) und gibt diese 1 an das erste flip-flop des Befehl-i-Moduls weiter, das AND davor schaltet durch, denn auch dessen oberer Eingang ist wegen exec = 0 auf 1.
In nächsten Takt wird also dieses flip-flop im Befehl-i-Modul und das flip-flop exec auf 1 sein, denn die NOR-Schaltung an dessen Eingang wird von den ihr vorausgehenden flip-flops an allen 31 Eingängen eine 0 empfangen. Tatsächlich sind die in der obigen Steuereinheit angedeuteten flip-flops so geschaltet, daß sie im fetch-Modus für einen Takt alle auf 0 sind, und dann für eine gewisse Anzahl von Takten nur das exec-flip-flop und ein weiteres flip-flop den Wert 1 haben und alle anderen den Wert 0. Diese zweite 1 wird sozusagen innerhalb eines Befehls-Moduls von einem flip-flop auf nächste weitergereicht bis sie in das NOR-Gatter vor dem exec-flip-flop einmündet. Änlich wie schon beim fetch-Modul werden durch diese zweite 1 (neben der 1 im exec flip-flop) Leitungen innerhalb der CPU durchgeschaltet, das werden wir noch sehen. Doch zunächst wissen wir nur, daß das flip-flop exec und das erste flip-flop in Befehl-i-Modul auf 1 sind.
Dabei haben die Befehls-Module folgenden Aufbau. Wir sehen uns zuerst einmal das Befehls-Modul für den ASSIGN-Befehl an.
Die Funktionsweise ist ähnlich wie beim fetch-Modul: durch eine 1 am Eingang unten werden die Ausgänge Rj31,...,Rj31 des Register-Moduls mit dessen Eingängen Rj31,...,Rj31 "kurzgeschaltet", wobei Ri-load auf "Laden" gesetzt wird. Welches i und welches j genommen werden sollen, steht an festgelegten Stellen im Befehl, der ja im Moment im register CB steht. Das folgende "Parameter"-Modul liest diese Parameter aus dem Befehl und steuert das Register-Modul korrekt an.
Das folgende PC+1-Modul incrementiert das Register PC, denn nach einem ASSIGN-Befehl soll ja der nächste im Hauptspeicher stehende Befehl abgearbeitet werden.
Das Parameter-Modul und das PC+1-Modul werden noch von anderen Befehelen benutzt werden. Auch diese mehrfach benutzten Teil-Module der Steuereinheit haben (wie die Module der CPU) vor ihren Eingängen jeweils ein mehrstelliges OR. Es werden auch gleich die zum PC+1-Modul analogen Schaltungen "PC+2" und "PC+AR" für die 2-Wort-Befehle bzw. die relativen Sprünge angegeben: Hier sind die Module für den ADD-Befehl und den RINGSHTIFT-LEFT-Befehl.
Und hier sind die Module für die 2-Takt-Befehle LOAD und JUMP-IF-ZERO. Beim JUMP-IF-ZERO-Befehl sind die flip-flops nicht mehr eingezeichnet.
Der Teil "LESE-W-Modul", der die Aufgabe hat, den zweiten Teil W des 2-Wort-Befehls in das Register AR einzulesen, ist durch folgende Schaltung realisiert:
Außerdem sollten noch die beiden Module PC+2 und PC+AR genau spezifizeirt werden:
Diese Beispiele machen klar, wie die Befehls-Module aussehen. Die weiteren Module zu lesen ist wohl genauso langweilig, wie sie zu schreiben. Weil aber angekündigt wurde, daß der SIMPLE bis auf Bauelement-Ebene hinunter realisiert wird, sind hier die links auf die Skizzen für die weiteren Module.
Der Rechner SIMPLE bekommt 9 weitere Eingänge in7,...,in0, und 'in', die den gleichnamigen Ausgängen des Input-Buffers entsprechen, siehe Übungsaufgabe 5.3. Der Input-Buffer wird mit dem CPU-Ausgang 'next-in' um das vorderste Byte verkürzt. Die Information 'in' vom Eingabe-Puffer, die anzeigt, ob überhaupt eine sinnvolle Eingabe vorliegt, ist innerhalb der CPU als flag F1 ansprechbar (dieses flag ist also kein Register, es ändert sich bei jedem Takt). Für die Ausgabe auf einen Bildschirm hat die CPU 9 Ausgänge out7,...,out0 und 'out'. Der Ausgang 'out'=1 zeigt dabei dem Bildschirm an, daß er das an den Ausgängen out7,...,out0 liegende Byte wirklich drucken soll. Die Ausgabe wird nicht gepuffert.
Der Befehls-Satz für den Rechners SIMPLE wird durch folgende 7 Befehle zum Befehls-Satz SIMPLE+I/O erweitert.
| Befehl | Parameter | Funktion |
| READ-INPUT | Ri | Schreibe das Byte an den in-Eingängen in die 8 rechten bits von Ri |
| WRITE-OUTPUT | Ri | Schreibe die 8 rechten bits von Ri auf den Bildschirm |
| IF-F1-JUMP | W | Falls ein Eingabe-Byte im Puffer ist, springe W Stellen weiter |
| BYTE-RING-SHIFT-LEFT | Ri | Schiebe ringweise die bits in Ri um 8 Stellen nach links |
| ASSIGN-BYTE | Ri Rj | Kopiere die rechten 8 bits von Rj in die rechten 8 bits von Ri |
| LOAD-BYTE | Ri B | Kopiere B in die rechten 8 bits von Ri |
| IF-BYTE-EQUAL-JUMP | Ri Rj | Springe W Stellen weiter, falls die rechten 8 bits von Ri mit den rechten 8 bits von Rj übereinstimmen |
Zu den Befehlen:
Bytes sind Folgen von 8 bits und entspechen den Buchstaben der Tastatur. Dabei wird hier der sogenannte ASCII Code verwendet: die Buchstaben 'a', ..., 'z' werden z.B. durch die Bytes kodiert, die die Zahlen 97, ..., 122 binär darstellen, also 'a' wird zum Beispiel durch 01100001 dargestellt. Buchstaben 'A', ..., 'Z' werden durch die Bytes kodiert, die die Zahlen 65, ..., 90 binär darstellen, die Ziffern '0', ..., '9' werden durch die Bytes dargestellt, die die Zahlen 48, ..., 57 binär kodieren. Das Komma ',' hat z.B. den Code 44 = 00101100 und das Leerzeichen ' ' hat den Code 32 = 00100000. Diese Code-Darstellung soll im Einzelnen weiter nicht interessieren, denn eine Codierung eines Tastatur-Buchstabens wird immer durch den in Hochkommata eingechlosssenen Buchstaben beschrieben. Z.B. steht 'a' für das Byte 01100001. Siehe vielleicht auch die Programmbeispiele unten. Einen besonderes Byte wird öfter benutzt werden: das Byte heißt newline und wird wie ein Buchstabe durch '\n' dargestellt. Er soll ein Return auf der Tastatur bzw. ein neue Zeile fü,r den Bildschirm representieren. Er hat einen von den normalen Tastatur-Zeichen verschiedenen festen Code, der aber nicht interessieren soll (ebensowenig wie die genauen Codes der normalen Buchstaben keine Rolle spielen). Bemerkung. Die hier beschriebene Notation für Bytes ist der Programmiersprache C entlehnt.
Realisiert werden die 7 neuen Befehle durch jeweils ein Befehlsmodul, siehe den vorherigen Abschnitt. Dabei gibt es keine neuen Techniken, es müssen einfach nur entprechend der Definition eines Befehls die richtigen Leitungen geschaltet werden. Hier sind zum Beispiel die Befehlsmodule für die Befehle READ-INPUT und WRITE-OUTPUT.
1. Beispiel-Programm. Das folgende Programm schreibt "Hallo Welt!" auf den Bildschirm .
LOAD-BYTE R0 'H' WRITE-OUTPUT R0 LOAD-BYTE R0 'a' WRITE-OUTPUT R0 LOAD-BYTE R0 'l' WRITE-OUTPUT R0 LOAD-BYTE R0 'l' WRITE-OUTPUT R0 LOAD-BYTE R0 'o' WRITE-OUTPUT R0 LOAD-BYTE R0 ' ' WRITE-OUTPUT R0 LOAD-BYTE R0 'W' WRITE-OUTPUT R0 LOAD-BYTE R0 'e' WRITE-OUTPUT R0 LOAD-BYTE R0 'l' WRITE-OUTPUT R0 LOAD-BYTE R0 't' WRITE-OUTPUT R0 LOAD-BYTE R0 '!' WRITE-OUTPUT R0 STOP
2. Beispiel-Programm. Das folgende Programm liest die Eingabe-Bytes aus der Tastatur und wiederholt die Buchstaben - getrennt durch Komma und Leerzeichen - auf dem Bildschirm, solange bis ein Eingabe-Byte '\n' kommt. Aus der Eingabe "Hallo\n" wird also "H, a, l, l, o, ". Das Zeichen '\n' steht wie in C für ein Return auf der Tastatur bzw. eine neue Zeile auf dem Bildschirm .
LOAD-BYTE R1 '\n' % Return-Zeichen LOAD-BYTE R2 ',' % Komma in R2 LOAD-BYTE R3 ' ' % Leerzeichen in R3 IF-F1-JUMP % Anfang der (Warte)-Schleife 4 JUMP % Warteschleife -2 READ-INPUT R0 IF-BYTE-EQUAL-JUMP R0 R1 % springe zum STOP falls das Return-Zeichen da ist. 7 WRITE-OUTPUT R0 WRITE-OUTPUT R2 WRITE-OUTPUT R3 JUMP % zurueck zum Schleifenanfang -10 STOP %
Ein stack ist eine Speicherkonzept, das nach dem Prinzip last-in-first-out arbeitet. Im Gegensatz dazu arbeitet zum Beispiel der Input-Puffer nach dem Prinzip first-in-first-out, und der RAM hat zum Beispiel keine solchen Restriktionen bzgl. der Reihenfolge, deshalb heiß er ja auch random access memory. Ein Stack wird zur Realisierung des Unterprogramm-Konzepts benutzt, siehe weiter unten.
Der stack für den SIMPLE Rechner wird als Teil des Hauptpeichers angelegt. Dazu bekommt die CPU ein zusätzliches 32-bit-Register SP (für stack pointer).
Der Befehls-Satz für den Rechners SIMPLE wird durch folgende 8 Befehle zum Befehls-Satz SIMPLE+STACK erweitert.
| Befehl | Parameter | Funktion |
| LOAD-SP | W | SP := PC+W |
| LOAD-SP-ABSOLUTE | W | SP := W |
| READ-SP | Ri | Ri := SP |
| PUSH | Ri | SP := SP+1; RAM(SP) := Ri |
| POP | Ri | Ri := RAM(SP); SP := SP-1 |
| CALL | W | SP := SP+1; RAM(SP) := PC+2; PC := PC+W |
| CALL-ABSOLUTE | W | SP := SP+1; RAM(SP)= PC+2; PC := W |
| CALL-VIA-REGISTER | Ri | SP := SP+1; RAM(SP)= PC+1; PC := Ri |
| RETURN | PC := RAM(SP); SP := SP-1 |
Zu den Befehlen:
Daran, daß man alle neuen Befehlen mit Hilfe der bekannten ursprünglichen Befehle beschreiben kann, sieht man, daß durch die neuen Befehle theoretisch keine neuen Möglichkeiten entstehen: Man kann jedes SIMPLE+STACK-Programm in ein äquivalentes SIMPLE-Programm umschreiben.
Der Grund, warum die neuen Befehle dennoch eingeführt wurden, ist, daß man jetzt ein sehr natürliches Konzept direkt programmieren kann, nämlich das Konzept "Unterprogramm", und sogar das Konzept "rekursives Unterprogramm", wie im Folgenden beschrieben wird.
Beispiel. Die Fakultätsfunktion f(n) ist definiert durch f(1) = 1, und f(i+1) = (i+1) mal f(i). Das folgende rekursive SIMPLE+STACK-Programm berechnet die Fakultätsfunktion (natürlich nur modulo 232):
LOAD-SP-RELATIVE % lasse den stack hinter der Zeile fuer f(n) anfangen
25
READ-RELATIVE R3 % lese n
22
ASSIGN R0 R3
IF-ZERO-JUMP R0 % Anfangzeile der Rekursion
13
PUSH R0 % schiebe i+1 in den stack
DECREMENT R0
CALL % hier ist die Rekursion: rufe die Berechnung f(i) auf
-4
ASSIGN R2 R0 % kopiere das Ergebnis f(i) in R2
POP R1 % lese stack-Inhalt i+1 in R1 ein
CALL-ABSOLUTE % Multiplikations-Programm aufrufen: R0 = (i+1) mal f(i)
address MULT
IF-EQUAL-JUMP R1 R3 % Ende der Rekursion falls i+1 = n
6
RETURN % Ende des Aufrufs fuer i ungleich 0
LOAD R0 % f(0) = 1
1
RETURN % Ende des Aufrufs fuer i gleich 0
WRITE-RELATIVE R0 % f(n) steht in R0
4
STOP
% Zeile fuer n
% Zeile fuer f(n)
% hier fängt der stack an.
Der stack dient in dem Programm also dazu, den Wert i+1
zu speichern, bevor die Funktion für f(i) aufgerufen wird. Dieser Wert i+1
wird dann später wieder eingelesen. Der stack hat zum Beispiel
für die Eingabe n = 4 die folgenden Zustände, wobei angenommen
wird, daß das Programm im Hauptspeicher in der Zeile
100 anfängt. Ganz links stehen die Nummern der RAM-Zeilen, in denen sich der
stack befindet.
124 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
125 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109
126 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 113
127 109 109 109 109 109 109 109 109 109 109 109 109 109
128 2 2 2 2 2 2 2 2 2 113
129 109 109 109 109 109 109 109
130 1 1 1 113
131 109
Einen nicht-überschreibbaren Abschnitt des Hauptspeichers nennt man read-only-memory (ROM). Die Realisierung ist einfach: ganz einfach ein 32-bit-Register durch eine 32er-Kombination von Konstanten 0,1 ersetzen. Die ROM-Abschnitte des RAM zählen immer noch zum Hauptspeicher, das von-Neumann-Konzept bleibt. Wo die ROM-Teile des RAM liegen, muß der Programmierer wissen, die CPU meldet z.B. auch bei einem Schreib-Befehl auf eine ROM-Zeile keinen Fehler (es passiert dann einfach nichts).
Hier ist ein Programm von oben in Assembler statt in Maschinensprache:
pr-anfang LOAD-BYTE R1 '\n' % Return-Zeichen
LOAD-BYTE R2 ',' % Komma in R2
LOAD-BYTE R3 ' ' % Leerzeichen in R3
marke2 IF-F1-JUMP % Anfang der (Warte)-Schleife
marke1
JUMP % Warteschleife
marke2
marke1 READ-INPUT R0
IF-BYTE-EQUAL-JUMP R0 R1 % springe zum STOP falls das Return-Zeichen da ist.
schluss
WRITE-OUTPUT R0
WRITE-OUTPUT R2
WRITE-OUTPUT R3
JUMP % zurueck zum Schleifenanfang
marke2
schluss STOP %
Reelle Zahlen werden folgendermaßen im sogenannten 1-23-8-Format dargestellt. Das erste bit b31 der 32 bits stellt ein Minuszeichen dar. Die nächsten 23 werden zur Darstellung einer Rellen Zahl r = 0,1b30...b8 zwischen 0 und 1 verwandt, r wird Mantisse genannt. Die letzten 8 bits dienen zur Darstellung eines integers n für den Faktor 2n, mit dem r noch multipliziert wird, n wird Exponent genannt. Dargestellt wird also die Zahl plus/minus r mal 2n.
Bislang hatten wir als Benutzer-sichtbare Speicherelemente nur die Register und flags der CPU und den RAM. Jetzt wird dieses Bild etwas erweitert werden, und zwar um externe Speicher wie sie jeder zum Beispiel als Festplatte oder Diskettenlaufwerk kennt. Außerdem wird das Konzept des caches eingeführt, der zur performance-Verbesserung zwischen CPU und RAM geschaltet wird.
| Befehl | Parameter | Funktion |
| READ-DISK-BLOCK | Ri | DISK-BUFFER =: DISK(Ri) |
| WRITE-DISK-BLOCK | Ri | DISK(Ri) := DISK-BUFFER |
| EXCHANGE-DISK-BLOCK | Ri | vertausche DISK(Ri) und DISK-BUFFER |
| WRITE-DISK-BUFFER | Ri | DISK-BUFFER(n+1) := DISK-BUFFER(n), DISK-BUFFER(0) := Ri |
| READ-DISK-BUFFER | Ri | Ri := DISK-BUFFER(127) |
| IF-F2-JUMP | W | Falls letzter READ/WRITE-DISK-BLOCK-Befehl abgeschlossen ist, springe W Stellen weiter |
Die konzeptionell einfachste Form eines caches ist der vollassoziative cache. Der RAM habe einen Adressen der Länge a und Inhalte der Länge d (beim SIMPLE war a = d = 32). Ein n-Zeilen cache besteht aus n Registern mit jeweils a+d+1 bits. In den ersten a bits steht eine Adresse des RAM und in den folgenden d bits deren vom Programm vorgesehener Inhalt, das letzte bit indiziert, ob der cache-Eintrag überhaupt gültig ist (am Anfang ist der cache zum Beispiel leer und deshalb haben am Anfang alle Zeilen eine 0 als letztes bit).
Alle Anfragen des CPU gehen über den cache. Wenn die nachgefragte RAM-Zeile im cache abgespeichert ist, wird sie dort abgefragt bzw. upgedatet. Wenn sie dort nicht steht, wird die nachgefragte RAM-Adresse und deren Inhalt in den cache geladen.
Anfangs ist der cache leer, und solange leere (d.h. mit 0 markierte) Zeilen existieren, gibt es keine Probleme. Wenn aber alle Zeilen beschrieben sind, muß natürlich jedesmal, wenn eine Zeile neu in den cache gespeichert werden soll, eine andere Zeile herausfallen und in den RAM zurückgeschrieben werden. Welche Zeile dabei gewählt wird, muß man festlegen. Die üblichste Strategie ist first-in-first-out. Dabei hat man einen Zähler modulo Zeilenanzahl, der anfangs auf 0 gesetzt wird und dann bei jedem Neueintrag um 1 incrementiert wird. In die Zeile, auf die dieser Zaehler zeigt, wird der nächste Neueintrag geschrieben. D.h., wenn diese Zeile schon beschrieben war, dann ist sie es, die in den RAM zurückgeschrieben wird (noch bevor der Neueintrag hineingeschrieben wird). Eine effektiver arbeitende, aber aufwendiger zu implementierende Ersetzungs-Strategie ist least-frequently-used: Es wird die Zeile ersetzt, bei der es am längsten her ist, daß sie von der CPU nachgefragt wurde.
Ein 1-Weg-assoziativer cache bestehe aus 2n-Zeilen. Der RAM habe einen Adressen der Länge a und Inhalte der Länge d (beim SIMPLE war a = d = 32). Der Hauptspeicher wird in 2a-n Blöcke der Größe 2n eingeteilt. Jeder dieser Blöcke läßt sich also durch eine (a-n)-stellige binäre Zahl beschreiben. Eine Zeile des cache läßt sich durch eine n-stellige Zahl beschreiben. Wenn also in Zeile i des cache's die Nummer j eines Blocks steht, ist durch i und j eindeutig eine Adresse i+j*2ndes RAM bestimmt. Es ergibt sich daraus, daß eine Zeile des RAM nur in höchstens einer Zeile im cache gepeichert werden kann (beim vollassoziativen cache konnte jede RAM-Zeile in jeder cache-Zeile stehen).
Ein 2-Weg-assoziativer cache bestehe aus 2n-Zeilen. Der RAM habe einen Adressen der Länge a und Inhalte der Länge d (beim SIMPLE war a = d = 32). Der Hauptspeicher wird in 2a-n+1 Blöcke der Größe 2n-1 eingeteilt. Jeder dieser Blöcke läßt sich also durch eine (a-n+1)-stellige binäre Zahl beschreiben. Der cache wird in Blöcke der Größe 2 eingeteilt. Wenn also in Zweier-Block i des cache's die Nummer j eines Blocks steht, ist durch i und j eindeutig eine Adresse i+j*2ndes RAM bestimmt.
Bei der Turing-Maschine stehen Programme und Daten in zwei verschiedenen Speichern (damit ist sie kein reinrassiger von-Neumann-Rechner, der wurde ja auch erst 15 Jahre später konzipiert). Der Programm-Speicher habe 210 Zeilen mit jeweils 27 bit, und der Daten-Speicher habe 216 Zeilen mit jeweils nur 1 bit.
Die Befehle für die Turing-Maschine sind folgende: Entweder ein Befehl ist der STOP-Befehl, oder er ist von der folgenden Form:
if (Band(a) = 0) then {SCHREIBEN; KOPF; goto s} else {SCHREIBEN; KOPF; goto s'}
wobei SCHREIBEN jeweils für eine der beiden Möglichkeiten
"Band(a) := 0" oder "Band(a) := 1" steht. Und KOPF steht
jeweils für eine der drei Möglichkeiten
oder "a := a", "a := a-1 mod 216" oder "a := a+1 mod 216"
steht. s und s' sind Adressen im Programmspeicher.
Man kann die Befehle durch 27 bit b26...b0 kodieren: b26> = 1 steht für den STOP-Befehl. Für die zwei Möglichkeiten von SCHREIBEN braucht man jeweils 1 bit, und für die drei Möglichkeiten von KOPF braucht man jeweils 2 bits. Für die Adressen s und s' braucht man jeweils 10 bits.
Am Beginn der Rechnung steht der Kopf auf der Zeile 0 des Daten-Speichers, d.h. a = 0. Als erstes liest die Maschine den Befehl in Zeile 0 des Programm-Speichers. Den Befehl führt sie in der offensichtlichen Weise aus und springt dann zum entsprechenden Befehl im Programm-Speicher (also entweder zu s oder zu s', je nach Inhalt von Band(0)). Dann führt sie diesen Befehl aus, usw.. Beim STOP-Befehl hält sie an. Im Programm kann also wie gewohnt beliebig gesprungen werden, auf dem Band (Daten-Speicher) kann maximal um eine Zeile vor- oder zurückgegangen werden.
Beispiel: das folgende Programm stoppt genau dann, wenn in Zeile 1 des Daten-Speichers eine 1 steht (und geht andernfalls in eine unendliche Schleife)
0 if (Band(a)=0) then {Band(a) = 0; a=a+1; goto 1} else {Band(a) = 1; a=a+1; goto 1}
1 if (Band(a)=0) then {Band(a) = 0; a=a; goto 1} else {Band(a) = 1; a=a; goto 2}
2 STOP
Der 8086 hat 14 16-bit-Register. Mit Datengröße 8 bit, Registergröe 16 bit und Adressgrö223;e 20 bit ist der 8086 wesentlich inhomogener als der SIMPLE, der ja jeweils Größe 32 hat. Die Adressierung des Hauptspeichers wird beim 8086 folgendermaßen gelöst: Es werden zwei der 16-bit Register genommen, z.B. DS und AX, und diese zwei Registerinhalte beschreiben die Adresse ((DS mal 16) plus AX) modulo 220 im Hauptspeicher. Das erste Register beschreibt quasi ein zusammenhängendes 216-zeilen großes 16-tel des Hauptspeichers, anfangend mit der Adresse DS mal 16. In diesem Segment zeigt dann AX auf die gemeinte Zeile.
Die Register mit einem S als zweiten Buchstaben sind fü die Segment-Addressierung vorgesehen. Es gibt auch Standard-Segmente, zum Beispiel beziehen sich das stack pointer Register SP und das stack base pointer Register BP immer auf das stack Segment SS. Die Adresse CS:IP (für command segment bzw. instruction pointer) zeigt auf das erste Byte des als nächstes auszuführenden Befehls (beim Simple hieß das program counter). Alle diese Festlegungen usw. sollen hier nicht interessieren, sondern nur das Prinzip, das durch zwei 16-bit Informationen A und B auf die oben angegebene Weise eine 20-bit-Adresse A:B spezifiziert ist.
Es gibt vier Adressierungsarten: immediate, direct, register, und indirect. Am Beispiel des Zuweisungs-Befehls MOV wird das klar:
MOV AX 22 lädt die Konstante 22 (in 16-bit-binär natürlich) in das Register AX. Das ist die Adressierung immediate.
MOV AX [22] lädt den Inhalt der Zeilen 22 und 23 (das sind jeweils 8 bits) in das Register AX. Das ist die Adressierung direct.
MOV AX DS:CX lädt den Inhalt der Zeilen DS:CX und DS:CX + 1 in das Register AX. Das ist die Adressierung register.
Insgesamt hat die Assembler-Sprache des 8086 mehr als 100 Befehle, die folgenden sind die wichtigsten (bei Parametern x oder y kann auf alle vier Arten addressiert werden):
| Befehl | Parameter | Funktion |
| MOV | x y | x =: y |
| INC | x | x =: x+1 |
| DEC | x y | x =: x-1 |
| ADD | x y | x =: x+y |
| JMP | marke | jump to marke |
| CMP | x y | falls x = y setze flag ZF:=1, sonst ZF:=0
falls x < y setze flag SF:=1, sonst SF:=1 |
| JZ | marke | jump to marke falls ZF = 1 |
| JNZ | marke | jump to marke falls ZF = 0 |
| JLE | marke | jump to marke falls SF = 1 |
| CALL | marke | Prozedur-Aufruf |
| RETURN | Prozedur-Ende |
Die bisher vorgestellten Rechner haben in einem Schritt (oder mehr) immer nur eine Aufgabe erledigt. Bei Parallel-Rechnern werden Aufgaben teilweise gleichzeitig ausgeführt. Das Problem ist dabei natürlich die Koordination.
Parallel-Rechner werden unterschieden in SIMD-Rechner (für Single-Instruction-Multiple-Data) und MIMD-Rechner (für Multiple-Instruction-Multiple-Data). Das Unterscheidungskriterium ist folgendes: Wenn es in der ganzen Schaltung nur eine Steuereinheit gibt und damit nur ein Programm abgearbeitet wird, dann handelt es sich um einen SIMD-Rechner. Bei mehreren Steuereinheiten, die Programme abarbeiten (selbst wenn es für alle das selbe ist), handelt es sich um einen MIMD-Rechner.
Exemplarisch soll der SIMPLE-Rechner zu einem Vektor-Rechner VEKTOR-SIMPLE erweitert werden. Dazu bekommt er zunächst einmal noch 48 weitere Register, also hat er insgesamt 64. Auf diesen Registern kann das gleiche gemacht werden wie vorher auf den 16. Es muß also der Befehlscode bei Register-Angaben um zwei bit erhöht werden - das ist kein Problem, denn es ist ja noch Platz da. Natürlich muß auch die CPU dann entsprechend auf 64 Register und den Zugriff darauf erweitert werden - im Prinzip bleibt aber die CPU wie vorher.
Jetzt kommt das Neue: die 64 Register werden in 4 Vektoren eingeteilt: V0 besteht aus den Registern R0,...,R15, V1 aus den Registern R16,...,R31, und V2 und V3 entsprechend. Jetzt wird für alle Befehle des SIMPLE, die nur auf den Registern arbeiten, eine Parallel-Version für Vektoren dazugenommen. Das sind die folgenden Befehle, die Vektor-Parameter Vi, Vj, Vk stehen für jeweils einen der 4 Vektoren V0,V1,V2 und V3, jede Kombination ist erlaubt.
| Befehl | Parameter |
| PARALLEL-ASSIGN | Vi Vj |
| PARALLEL-INCREMENT | Vi |
| PARALLEL-DECREMENT | Vi |
| PARALLEL-ADD | Vi Vj Vk |
| PARALLEL-CLEAR | Vi |
| PARALLEL-COMPLEMENT | Vi |
| PARALLEL-NEGATE | Vi Vj |
| PARALLEL-AND | Vi Vj Vk |
| PARALLEL-OR | Vi Vj Vk |
| PARALLEL-RINGSHIFT-LEFT | Vi |
| PARALLEL-RINGSHIFT-RIGHT | Vi |
| PARALLEL-SET-RIGHT-BIT-0 | Vi |
| PARALLEL-SET-RIGHT-BIT-1 | Vi |
Die Bedeutung eines solchen Befehls soll sein: nimm jeweils die jeweils 16 Register der angegebenen Vektoren und f&uum;hre 16 mal den angegebenen Befehl aus: zuerst auf den obersten Registern der angegeben Vektoren, dann auf den zweitobersten Registern der angegeben Vektoren usw.. Beispiel: PARALLEL-ADD V0 V2 V3 macht das gleiche wie die 16 Befehle R0 := R32 + R48; R1 := R33 + R49,..., R15 := R47 + R63. Wenn man also 16 Addierschaltungen in der CPU hätte, könnte man den Befehl in einem Schritt abarbeiten, denn bei den 16 angegebenen Einzelbefehlen kommt es auf die Reihenfolge der Ausführung nicht an.
Diese Annahme soll nun gelten: wir nehmen an, das die CPU tatsächlich für alle oben vorkommmenden Operationen die entsprechenden Schaltkreise 16-fach zur Verfügung hat (für Befehle wie ASSIGN oder RINGSHIFT-LEFT braucht man ja z.B. gar keine Gatter, nur INCREMENT, DECREMENT, ADD, und COMPLEMENT sind richtig aufwendig). Das kostet natürlich Hardware-Aufwand, aber beschleunigt die Rechnungen, falls die Parallel-Befehle sinnvoll genutzt werden können (das ist der typische trade-off bei Parallel-Rechnern versus Sequentiellen Rechnern).
Es bleibt noch das Problem, wie man einen solchen Parallel-Befehl, z.B. PARALLEL-ADD V1 V1 V2, dekodiert, so daß tatsächlich die die 16 Paare von Eingabe-Wörter aus den Registern der Vektoren V1 und V2 in die 16 Addierer geleitet werden und dann die 16 Ergebnisse in die 16 Register von Vektor V1 kommen. Dies Problem wird aber ganz straightforward mithilfe von Multiplexern und Dekodierern geloest, so wie wir es schon z.B. von der Register-Ansteuerung beim SIMPLE kennen.
Exemplarisch wird der SIMPLE-Rechner mit 64 Registern von oben zu einem Feld-Rechner FELD-SIMPLE gemacht. Die Aufteilung in die vier Vektoren bleibt dabei. Jetzt wird ein Befehl DO-PARALLEL eingeführt, der drei Vektoren Vi, Vj, Vk plus 16 SIMPLE-Befehle als Parameter hat. Die SIMPLE-Befehle sind dabei genau die, für die oben beim VEKTOR-SIMPLE die PARALLEL-Version eingeführt wurde, also ASSIGN, INCREMENT, usw.. Ein Befehl DO_PARALLEL Vi, Vj, Vk, COMMAND0, ..., COMMAND15 soll bedeuten: Führe den Befehl COMMANDi, auf den i-ten Registern (von oben) der drei angegebenen Vektoren aus. Beispiel: DO-PARALLEL V1, V2, V3, ADD, INCREMENT, INCREMENT, ASSIGN, ..., ADD führt folgende Befehle parallel aus: R16 := R32 + R48; R17 := R17 + 1, R18 := R18 + 1; R19 := R35; ..., R31 = R47 + R63. Es ist klar, daß jeder Befehl des VEKTOR-SIMPLE durch einen Befehl des FELD-SIMPLE Ersetzt werden kann, z.B. machen PARALLEL-ADD V0 V1 V2 und DO-PARALLEL V0 V1 V2 ADD, ADD,..., ADD das gleiche.
Der Rechner FELD-SIMPLE hat im Vergleich zum 64-Register-SIMPLE also nur einen zusätzlichen Befehl DO-PARALLEL. Der Befehlscode soll folgendermaß definiert sein: der Befehl besteht aus drei 32-bit-Worten, die ersten 32 bit kodieren DO-PARALLEL und die drei involvierten Vektoren, und die nächsten 64 bit kodieren in 4-er-Blocks die 16 parallel auszuführenden Befehle - es reichen ja 4 bits zur Kodierung der 12 möglichen Befehle.
Der FELD-SIMPLE braucht so wie der VEKTOR-RECHNER fü alle 12 möglichen Befehle die 16-fache Ausführung der entsprechenden Booleschen Schaltkreise, also 16 Addierschaltungen usw.. Weil wir jetzt einen 3-Wort-Befehl haben, braucht die Steuereinheit 2 zusä,liche 32-bit-Register, um die letzten 64 bit des Befehls speichern zu können. Wenn alle 96 bits des Befehls aus dem Hauptspeicher gelesen sind, geschieht die Befehlsausführung wie gewohnt in einem Schritt, es müssen nur wieder durch eine Multiplexer/Dekodierer-Schaltung die richtigen Informationen an die richtigen Stellen geschickt werden.
Warum sind der VEKTOR- und der FELD-SIMPLE SIMD-Rechner? - weil es zwar jetzt eine Menge Addierschaltungen usw. gibt, aber immer noch nur eine Steuereinheit, die genau ein Programm abarbeitet.
In der Skizze ist der Bus einfach als langer Strich gezeichnet, in Wirklichkeit verbirgt sich ein Schaltwerk dahinter. Dazu nehmen wir an, daß 4 Prozessoren (wie beim SIMPLE) mit jeweils 32 bits a0,...,a31 eine Adresse spezifizieren, um mit jeweils 32 bit r0,...,r31 zu lesen bzw. mit jeweils 32 bit w0,...,w31 zu schreiben. Zusätzlich zu diesen 32+32 Ausg&aum;ngen und 32 Eingängen hat jeder Prozessor zwei Ausgänge request und write-enable , und einen Eingang done: der Ausgang request=1 zeigt an, daß der Prozessor tatsächlich eine Hauptspeicher-Anfrage stellen möchte, dabei zeigt write = 0 an, daß er lesen möchte,, und write=1, daß er schreiben mö,chte. Die Rückleitung done=1 zeigt ihm an, daß seine Hauptspeicher-Anfrage beantwortet worden ist, bei done=1 hat er entweder gar keine Anfrage gestellt, oder ein anderer Prozessor ist vorgelassen worden. Der Hauptspeicher mit 232 Zeilen der Breite 32 hat die gewohnten Leitungen und die gewohnte Funktionalität (wie beim SIMPLE). Jetzt soll also der Bus diese 4 Prozessoren mit dem Hauptspeicher vernünftig zusammenschalten. Dabei tritt das Problem auf, daß verschiedene Prozessoren gleichzeitig den Bus nachfragen können, aber natürlich kann nur einer durchgelassen werden. Ein arbiter löst dieses Problem und schaltet nur maximal eine Anfrage - codiert durch eine 2-bit-Zahl - an den Hauptspeicher durch. Wenn der arbiter die Anfrage eines Prozessors an den Hauptspeicher geschickt hat, schreibt er in dessen Rückleitung done eine 1, alle anderen Rückleitungen bekommen den Wert 0. Bei einer durchgeschalteten Lese-Anfrage stehen zusätzlich die richtigen 32 bit in den Lese-Leitungen des entsprechenden Prozessors.
Hier ist der arbiter so gebaut, daß er Prozessor 0 immer den Vorrang vor Prozessor 1,2 und 3, dem Prozessor immer den Vorrang vor Prozessor 2 und 3, und dem Prozessor 3 immer den Vorrang vor Prozessor 4 gibt. Der Ausgang any zeigt an, daß überhaupt ein Prozessor eine Zuteilung anfordert. Die binäre Zahl p1p0 kodiert den zugeteilten Prozessor.
Hauptspeicheranfragen kommen sehr häfig vor, allein schon wegen der Programme, die im Hauptspeicher stehen. Deshalb treten schon bei ein paar Prozessoren Warte-Probleme auf, und je mehr Prozessor es werden, desto kleiner wir der Vorteil gegenüber der 1-Prozessor-Schaltung, die Prozessoren werden die meiste Zeit Däumchen drehen, d.h. auf den Bus warten. Der Bus stellt quasi ein zu enges Nadelöhr für diese Mengen von Hauptspeicher-Zugriffen dar.
Eine Lösung für dieses Nadelöhr-Problem ist die Einführung von caches Ci zwischen jedem Prozessor Pi und dem Bus. Dabei hofft man, daß die meisten Hauptspeicher-Anfragen gar nicht über den Bus an den tatsächlichen Hauptspeicher weitergeleitet werden müssen, sondern schon im cache bearbeitet werden können, weil die entsprechende Zeile dort zwischengespeichert ist. Die Nützlichkeit der caches wird vor allem dadurch gesteigert, daß statistisch gesehen von den meisten Programmen immer wieder die gleichen Hauptspeicher-Zeilen bearbeitet werden.
Das Problem mit den caches ist das sogenannte cache-coherence Problem: Angenommen, in Zeile 20 ist die Zahl 150 abgespeichert. Prozessor 1 will Zeile 20 mit der Zahl 160 beschreiben: er holt die Zeile in seinen cache C1 und schreibt dort 160 hinein. Im Hauptspeicher steht aber immer noch die Zahl 150 in Zeile 20, jeder andere Prozessor bekommt also eine falsche (ein sogenannte abgestandene) Information zu lesen, falls er auf Zeile 20 lesend zugreift. Auch wenn bei Schreib-Befehlen nicht nur der cache sondern auch der Hauptspeicher neu geschrieben werden, entsteht ein Problem: Prozessor 1 will Zeile 20 mit der Zahl 160 beschreiben: er holt die Zeile in seinen cache C1 und schreibt dort ebenso wie in Zeile 20 des Hauptspeichers 160 hinein. Danach will Prozessor 2 die Zeile 20 mit der Zahl 170 beschreiben: er holt die Zeile in seinen cache C2 und schreibt dort ebenso wie in Zeile 20 des Hauptspeichers 170 hinein. Jetzt ist das Problem die Information im cache C1: das Datum 160 für Zeile 20 ist abgestanden, es sollte 170 dort stehen.
Die einfachste Lösung ist das folgende, sogenannte Lösch-Protokoll: Bei Lese-Zugriffen eines Prozessors Pi wird zuerst im cache Ci nachgeschaut, und wenn das Datum dort nicht zu finden ist, über den Bus im Hauptspeicher gelesen und in den cache Ci geladen. Bei einem Schreib-Zugriff eines Prozessors Pi auf Zeile a wird in allen caches einschließlich Ci der Eintrag auf Zeile a als invalid (falls vorhanden) markiert, und im Hauptspeicher wird Zeile a dann entprechend dem Schreib-Befehl beschrieben. Ein besseres Protokoll ist das Ersetzen-Protokoll: anstatt in allen caches einen Eintrag als ungültig zu markieren, ersetzt man in allen caches das Datum in der zu beschreibenden Zeile durch das neue. Der kleine Nachteil dieses Protokolls ist, daß die caches nicht nur nach der Adresse der zu beschreibenden Zeile wissen müssen, sondern auch über weitere Datenleitungen auch das neue Datum für diese Zeile. Die caches müssen bei beiden Protokollen den Bus beobachten, man nennt sie deshalb auch snooping (schnüffelnde) caches.
Die Prozessoren P1 bis P8 stellen Anfragen an den Hauptspeicher, der in die Teile M1 bis M8 aufgeteilt ist. Die Gitterpunkte können ein- oder ausgeschaltet werden. Wenn der Gitterpunkt zwischen Pi und Mj eingeschaltet ist, bedeutet das, das Pi auf Mj zugreifen kann. Es darf also in jeder Spalte h&oum;chstens 1 Gitterpunkt eingeschaltet sein, und es sollte pro Zeile auch nur ein Gitterpunkt eingeschaltet sein (d.h. es gibt soviel erlaubte Einschalt-Kombinationen wie es nichtschlagende Positionen von 8 Türmen auf dem Schachbrett gibt). Realisiert wird das Gitter als Boolesche Schaltung. Das Gitter nennt man auch crossbar switch, es war schon vor der Erfindung von Computern für das Stecken von Telefon-Verbindungen bekannt.
Den Vorteil gegenüber der Bus-Koppelung ist der, daß möglicherweise jetzt bis zu 8 (anstatt 1) Hauptspeicher-Zugriffe gleichzeitig möglich sind, der Idealfall tritt ein, wenn alle Prozessoren auf verschiedene Speicherteile zugreifen wollen.
Das crossbar switch wächst quadratisch: bei 1000 Prozessoren und 1000 Speicherteilen braucht es ein Million Gitterpunkte, die ja letztendlich Schaltkreise sind. Eine Verbesserung hinsichtlich der Größe sind die sogenannten Omega-Netzwerke.
Hier geht wieder darum, die vorhandenen Prozessoren direkt auf die vorhanden Speicherteile zugreifen zu lassen. Ein Schalter 1A, 1B, ..., 3C, 3D schaltet dabei eine der vier Möglichkeiten durch, eine der beiden Eingabeleitungen mit einer der beiden Ausgabeleitung zu verbinden. Welche der vier Möglichkeiten durchgeschaltet wird, bestimmen die Informationen in den beiden Eingabeleitungen. In dem obigen 8x8 Omega-Netzwerk kann potentiell jeder Prozessor mit jedem Speicherteil verbunden werden. Wenn kein anderer Prozessor aktiv ist, ist das kein Problem. Wenn andere Prozessoren schon aktiv sind, ist es nicht garantiert, aber es besteht die Möglichkeit, da&#ss; die zusäzliche Verbindung offen ist. Maximal können in dem obigen Omega-Netzwerk 4 Verbindungen parallel bestehen, z.B. P000-1A-2A-3A-M000, P001-1B-2C-3B-M010, P010-1C-2B-3C-M100, und P011-1D-2D-2D-3D-M110.
Die Grö eines Omega-Netzwerks wächst nur mit der Ordnung n mal log(n) statt n2 wie das crossbar switch. Der Nachteil ist, das weniger Kombination von Prozessor-Speicherteil-Kombinationen parallel durchzuführen sind: Beim crossbar-switch kann jede Verbindung Pi-Mj und Pk-Ml mit Pi ungleich Pk und Mj ungleich Ml geschaltet werden, bei dem obigen Omega-netzwerk ist das z.B. für die zwei Kombinationen P000-M000, P100-M111 nicht möglich (scheitert an Schalter 1A).
Andere Topologien sind das array, bei dem die Rechner in eine Kette geschaltet sind. Das kann zu einem Ring erweitert werden, indem die beiden End-Rechner verbunden werden.
Beliebt ist es auch, die Rechner als 2-dimensionales Gitter zusammenzuschalten, die Einzel-Rechner nennet man in dem Fall Transputer. Die Rechner sind dabei auf einer Ebene wie in einem Gitter angeordnet, jeder ist mit seinen 4 Nachbarn verbunden, bis auf die Rechner am Rand, die nur zwei bzw. drei Nachbarn haben. Man kann die Rechner natürlich auch als dreidimensionales Gitter anordnen.
Als letztes Beispiel - es gibt natürlich noch mehr Topologien, der Phantasie sind keine Grenzen gesetzt - soll der Hypercube genannt werden: 2n Rechner werden durch jeweils n bits kodiert, und zwei Rechner sollen verbunden sein, wenn sich die Codes nur um 1 bit unterscheiden. Der 2-dimensionale Hypercube und das zweidimensionale Gitter mit 2x2 Rechnern und auch der 3-dimensionale Hypercube und das dreidimensionale Gitter mit 2x2x2 Rechnern sind identisch.
Es seinen n Rechner zusammengeschaltet, und zwar jeweils durch Datenleitungen in beide Richtungen (das ist mathematisch gesehen ein ungerichteter Graph). Dabei wird angenommen werden, daß jeder Rechner mit jedem anderen indirekt verbunden ist (mathematisch formuliert: der Graph ist zusammenhängend). Der Abstand von zwei Rechnern ist der kürzeste Weg über diese Verbindungen von einem zum anderen. Dabei wird die Länge eines Weges gemessen als die Anzahl von direkten Datenleitungen zwischen zwei Rechnern, die man benutzt. Der Durchmesser des Topologie ist definiert als der größte Abstand von zwei Rechnern in der ganzen Toplogie. Das array mit 6 Rechnern hat also den Durchmesser 5, der Ring mit 6 Rechner hat den Durchmesser 3, der 4D-Hypercube hat den Durchmesser 4. Der Verzweigungsgrad eines einzelnen Rechners in einer Topologie ist die Anzahl der Rechner, mit denen er verbunden ist. Der Verzweigungsgrad der ganzen Topologie ist der größte Verzweigungsgrad eines Rechners darin. Die Bandbreite ist die Anzahl aller Verbindungen in der ganzen Topologie, z.B. hat der 4D-hypercube die Bandbreite 32.
Diese Begriffe sind Meßzahlen, um die Funktionalität einer Topologie zu beurteilen. Der Durchmesser gibt z.B. an, wie weit der Weg einer Nachricht in der Topologie sein kann. Der Verzweigungsgrad gibt an, wieviele physikalische Anschlüsse ein einzelner Rechner haben muß. Die Bandbreite gibt an, wieviel Information in einem Zeitpunkt maximal übermittelt werden kann.
8 der 9 Eingangsleitungen übertragen ein Byte und die neunte Leitung zeigt durch den Wert 1 an, daß wirklich ein Byte übertragen werden soll. Wenn dies neunte bit auf 1 ist, wird das Byte plus diese neunte bit in einem 9-bit Register gespeichert. Der Wert des 9-ten bits wird durch eine Ausgangsleitung an den Nachbar-Transputer übertragen. Wenn nämlich der Transputer das übertragene neue Byte in ein Register einliest, wird das neunte Anzeigebit auf 0 gesetzt und der Nachbar-Transputer weiß, daß das Byte gelesen wurde und er eventuell das nächste schicken kann.
Die folgenden vier Befehle müßten reichen, um einigermaßen vernünftige Kommunikation auf den Transputern zu erreichen.
| Befehl | Parameter |
| TR-OUTPUT | Di Rj |
| TR-INPUT | Di Rj |
| IF-TR-INPUT-JUMP | Di W |
| IF-TR-OUTPUT-JUMP | Di W |
Das Betriebssystem hat die Aufgabe, dem Benutzer das Arbeiten mit dem Rechner zu erleichtern. Das beinhaltet vor allem die Realisierung von zwei Konzepten, die jeder Computer-Benutzer kennt, die aber bisher (bei der Besprechung der reinen Hardware) noch gar nicht vorkamen: Die beiden Konzepte
Aktuelles Beispiel: Ein Verzeichnis namens "Informatik2" enthät eine Datei "www.html" und zwei Verzeichnisse "Script" und "Uebungen", die beide wiederum verschiedene Dateien, aber keine weiteren Verzeichnisse enthalten. Das Verzeichnis "Script"enthält dabei die Datei "Script-10.html", die Sie gerade per Internet und Browser lesen. Die Möglichkeit der Kurzbeschreibung mit (relativen) Pfad-Namen der Form "Informatik2/Script/Script-10.html" ist übrigens keine Angelegenheit des Dateisystems sondern eine der Benutzeroberfläche.
So ein Datei-System soll nun auf der bekannten, riesigen Platte mit 232 Blöcken zu je 4096 bits = 512 Bytes = 128 32-bit-Wörter implementiert werden. Für eine Datei wird die Information folgendermaßen in Folgen von 32-bit-Wörtern codiert: Im ersten Wort stehen Basis-Informationen, dabei soll hier nur das ganz rechte bit interessieren: die 0 zeigt an, daß es sich um eine Datei und nicht um ein Verzeichnis handelt. In den folgenden 32-Wörtern bis zum ersten 32-bit-Wort 0 steht der Name der Datei. Dabei sollen hier nur jeweils die rechten 8 der 32 bits interessieren - das ist natürlich Verschwendung, aber es geht ja nur um's Prinzip. Nach der 0 fängt der eigentliche Teil der Datei-Beschreibung an: es werden mithilfe von 32-bit-Wörtern die Blöcke aufgelistet, in denen die Datei steht. Die 32 bit reichen genau aus, um einen Block zu bezeichnen, dabei stehen in jedem Block 512 Buchstaben. Nach dieser Liste von Block-Adressen folgt ein 32-bit-Wort 0. Dabei wird die 0 nicht als Adresse für den Block 0 interpretiert, denn es wird festgelegt werden, daß im Block 0 die Beschreibung des Datei-Systems anfängt. Das genaue Ende der Datei im letzten Block wird durch das Sonderzeichen EOF (end of file) festgelegt. Die Beschreibung für ein Verzeichnis sieht ähnlich aus: Im ersten Wort steht ganz rechts eine 1, in den restlichen bits kann zusätzliche Basis-Information über das Verzeichnis stehen. Dann folgt wieder bis zum ersten 32-bit-Wort 0 der Name der Datei, kodiert in den nur jeweils rechten 8 bits. Nach der 0 folgen dann Paare von 32-bit-Wörtern: das erste Wort gibt einen Block an, und die rechten 7 bits des zweiten Wortes geben eins der 128 Wörter in diesem Block an. In diesem so addressierten 32-bit-Wort fängt die Beschreibung einer neuen Datei oder eines neuen (Unter-) Verzeichnisses an.
Damit ist die Beschreibung der Kodierung eines hierarchischen Datei-Systems fast abgeschlossen. Es wird jetzt nur noch festgelegt, daß die Beschreibung des gesamten Datei-Systems auf der Platte im 0-ten 32-bit-Wort des Blocks 0 anfängt, und daß eine Beschreibung einer Datei oder eines Verzeichnisses, die in Wort 127 eines Blocks noch nicht abgeschlossen ist, im folgenden Block weitergeht. Die Festlegung ist natürlich in großem Maße willkürlich und auch unrealistisch (was man schon an der Plattengröße erkennt), aber die Problemstellung sollte an dem Beispiel klar geworden sein. Bemerkung: Wer schon öfter programmiert hat, sieht auch, daß eigentlich nur das Zeiger-Konzept auf diesen speziellen Fall der Darstellung eines Baumes angewandt wurde.
Beispiel: Das Hauptverzeichnis "Pl" habe eine Datei "p" und ein Verzeichnis "d", das leer ist. Die folgende Information in Block 0 beschreibt dieses Datei-System:
Typische Aufgaben eines Betriebssystems in Bezug auf das Datei-System sind z.B.. Kopiere die Datei x in eine Datei namens y. Dabei muß natürlich ein Platz für y auf der Platte gefunden werden. Über die noch freien Blöcke sollte Buch geführt werden. Günstig ist es dabei, immer große Intervalle von freien Blöcke zu halten. Auch das Kopieren einer Maschinenprogramm-Datei in den Hauptspeicher zur Vorbereitung auf das Laufenlassen ist Aufgabe des Betriebssystems.
Der rechnende Prozeß verliert diesen Status, indem er entweder selber aufhört (weil er fertig ist, oder aus Fairnis den anderen Prozessen gegenüber, oder weil er auf etwas warten muß) oder er wird vom Prozeß-System mithilfe eines interrupts abgebrochen, z.B. nach einer gewissen Anzahl von Rechenschritten. Mit diesem Prozeß passiert dann folgendes (nachdem sich sein CPU-Zustand gemerkt worden ist): wenn er fertig ist, wird er aus der Prozess-Verwaltung gestrichen; wenn er auf etwas wartet, wird er in die Liste der wartenden Prozesse eingereiht; ansonsten wird er in die Liste der bereiten Prozesse einreiht.
Es wird wie beim Datei-System ein simples Beispiel für den Aufbau eines Prozeß-Systems gegeben.
Vier an einer festen Stelle namens PV (= Prozeß-Verwaltung) im Hauptspeicher hintereinanderstehende Zeilen stellen die Hauptinformation für das Prozeß-System dar. Die erste Zeile zeigt auf eine Liste aller aktuellen Prozesse in einer beliebigen Reihenfolge, zum Beispiel in der Reihenfolge der Generierung. Die zweite Zeile zeigt auf den gerade rechnenden Prozeß. Die dritte und vierte Zeile zeigen auf die Liste der bereiten bzw. wartenden Prozesse. Dabei wird ein Prozeß durch 26 im Hauptspeicher hintereinanderstehende Zeilen beschrieben: Die erste zeile hat eine eindeutige Identifikations-Nr., die jeder Prozeß bei seiner Generierung bekommt. In der zweiten Zeile stehen weitere Information, z.B., ob der Prozß rechnend, wartend oder bereit ist. In den folgenden zwei Zeilen stehen zwei Zeiger, die den Prozeß in die doppelt verkettete Liste aller aktuellen Proßsse einbinden. Die darauffolgenden zwei Zeilen binden ihn in die Liste der bereiten oder der wartenden prozesse ein (ein Prozeß kann höchstens in einer dieser beiden Listen stehen). In den letzten 20 Zeilen der Prozeß-Information stehen die Daten der CPU, mit der der Prozeß weitermachen wird, wenn er wieder zum Rechnen dran kommen wird (im Normalfall steht dort also der Zustand der CPU zu dem Zeitpunkt, als er zum letzten Mal rechnend war).
In dem Prozeß-Modell sollen P0 und P1 unabhängig arbeiten, insbesondere soll Abarbeitungsgeschwindigkeit nicht synchronisiert sein, d.h. man weiß nicht, wie schnell ein Prozeß im Vergleich zum anderen ist, auch der Zeitabstand zwischen zwei Befehlsausführungen im gleichen Prozeß kann variieren. Die Prozesse können nur über gemeinsame Daten (wie z.B. d), die sie lesen und beschreiben, kommunizieren. Befehle in verschiedenen Prozessen werden hintereinander ausgeführt, aber wegen der verschiedenen Verarbeitungsgeschwindigkeiten weiß man im Allgemeinen nicht, in welcher Reihenfolge, und die Reihenfolge ist für das Ergebnis natürlich entscheidend. Beispiel 1: wenn P0 d := 0 befiehlt und P1 d := 1, dann ist in der Ausführungsreihenfolge d := 0; d := 1 die Variable d hinterher 1, und bei d := 1; d := 0 ist sie 0. Bei dem Beispiel d := d+1 und d:=d-1 scheint die Ausfürungsreihenfolge keine Rolle zu spielen, aber das ist bei genauem Hinsehen falsch: Es sei d = 5. Bei
R0 := d; R0 =: R0+1; R1 := d; R1 =: R1-1; d:= R0; d:= R1ist hinterher d = 4, bei
R0 := d; R0 =: R0+1; R1 := d; R1 =: R1-1; d:= R1; d:= R0ist hinterher d = 6.
Dieses Szenario vorausgesetzt, ist der einfache Zugriff der beiden Prozesse auf d zu gefährlich: Wenn quasi gleichzeitig durch P0 d:=d+1 und durch P1 d:=d-1 befohlen wird, ist möglicherweise nachher der Wert in d falsch. Für den Algorithmus (in diesem Fall: Datentransfer vom Band zur Platte) bedeutet das Unkorrektheit bzw. Absturz. Es stellt sich also das Problem, den gleichzeitigen Zugriff auf d auszuschließen.
Die erste Idee ist, eine weitere Variable t zu reservieren, die den Wert 0 oder 1 annehmen kann (t ist also ein flag) und worauf beide Prozesse Zugriff haben. t soll anzeigen, welcher Prozeß die Schreibrechte auf die Information d hat. Der Algorithmus 1 sieht dann so aus: Wenn Prozeß Pi d beschreiben will, reserviert er sich diese Rechte, indem er die Variable t auf i setzt. Dann beschreibt er d mit seinem entsprechenden Befehl. Wenn die Prozesse hintereinander d beschreiben, funktioniert der Algorithmus 1 natürlich. Das Problem ist aber, daß die Prozesse verschiedene Arbeitsgeschwindigkeiten haben können: Angenommen, P0 setzt t auf 0. Jetzt kann es sein, daß noch bevor P0 d beschreibt, P1 t auf 1 setzt und dann beide Prozesse gleichzeitig Zugriff auf d bekommen - das wollten wir vermeiden.
Hier ist Algorithmus 2: Anstatt vorm Beschreiben von d das flag t zu setzen, fragt der Prozeß es ab: wenn es die eigene ID ist, darf er schreiben, sonst muß, er warten. Wenn er geschrieben hat, dann ändert er t zum anderen Wert um. Dieser Algorithmus vermeidet tatsächlich das gleichzeitige Schreiben. Aber er hat den Nachteil, daß die beiden Prozesse immer nur abwechselnd d beschreiben können. Das ist aber natürlich nicht so gedacht, im konkreten Beispiel hieße das, daß die Warteschlange höchstens die Länge 1 haben kann. Auch durch weiteres Abfragen und Setzen der Variablen t in der Zwischenzeit kann man Algorithmen 1 und 2 nicht korrigieren.
Hier ist Algorithmus 3: Nimm zwei flags f0 und f1, wobei fi anzeigen sol, daß Pi auf d schreiben wird. Jeder der beiden Prozesse Pi macht folgendes: wenn Pi schreiben will, fragt er ab, ob das flag fj anderen Prozesses Pj auf 1 ist. Wenn ja, fragt er weiter ab, solange bis fj auf 0 ist. Dann setzt Pi fi auf 1, schreibt d, und setzt danach fi wieder auf 0. Das Problem ist aber wieder: Wenn beide Prozesse gleichzeitig schreiben wollen, sehen sie, daß das flag des anderen Prozesses auf 0 ist, und setzen ihre beiden flag auf 1 und schreiben - wenn man Pech hat - gleichzeitig auf d. Aber gerade das soll ja vermieden werden.
Hier ist Algorithmus 4: Nimm zwei flags f0 und f1, wobei fi anzeigen sol, daß Pi auf d schreiben möchte. Jeder der beiden Prozesse Pi macht folgendes: Pi setzt fi auf 1, wenn er d schreiben will. Solange auch das flag fj des anderen Prozesses auf 1 ist, wartet Pi. Wenn man feststellt, daß fj auf 0 ist, schreibt man und setzt anschließend fi auf 0. Das Problem mit diesem Algorithmus ist: Wenn beide ihr flag setzen, noch bevor einer das flag des anderen liest, kommen sie beide in ein sogenanntes deadlock: sie blockieren sich gegenseitig (sie laufen beide in eine endlose Schleife).
Hier ist eine korrekte Lösung, die quasi eine Kombination aus Algorithmus 1 und 4 ist. Benötigt werden drei flags t, f0, und f1. fi soll anzeigen, daß Pi d beschreiben möchte. Jeder der beiden Prozesse Pi macht folgendes: Wenn er d beschreiben möchte, setzt er erst einmal sein flag fi auf 1. Dann gibt er höflicherweise dem anderen Prozeß Pj den Vortritt, indem er die Variable t auf j setzt. Dann liest er in einer Schleife solange abwechselnd t und das flag fj bis entweder t = i oder fj = 0 ist. Wenn einer dieser beiden Fälle auftritt, beschreibt er d und setzt danach fi auf 0.
Warum funktioniert dieser Algorithmus? Erstens ist garantiert, daß immer nur einer der Prozesse d beschreibt: Wenn nur eins der flags fi 1 ist, dann ist es der Prozeß dessen flag fi 1 ist, der d beschreibt; wenn beide flags fi auf 1 sind, dann ist es der durch t gegebene Prozeß, der d beschreibt, ohne vom anderen gestört zu werden. Andererseits werden sich die beiden Prozesse nicht wie bei Algoithmus 4 blockieren: wenn beide flags fi auf 1 sind, wird der Prozeß, der sein flag als erster auf 1 gesetzt hat, irgendwann t befragen und sehen daß t seine Prozeß-Nummer hat, und dann d beschreiben.
Es ist klar, daß die Aktion "schreibe d" in den beiden Prozessen unwesentlich ist, es könnte genausogut jedes andere Programmteil dort stehen, das für die Zeit seines Ablaufens exklusiven Zugriff auf gewisse Daten (wie z.B. d oben) verlangt. Dieser Teil eines Prozesses heißt kritischer Bereich.
Es wird ein vollassoziativer cache mit 8192 Zeilen mit jeweils 25+2 bits Zeilenlänge eingebaut. Die ersten 25 bits addressieren eine Seite des virtuellen Hauptpeichers, der im realen Hauptspeicher steht, allerdings nur, wenn das folgende tag-bit t gleich 1 ist. Das letzte bit d zeigt an, ob der Block dirty ist, d.h., ob die Seite im realen Hauptspeicher schon verändert wurde, seitdem sie in den realen Hauptspeicher eingelagert wurde.
Der cache enthält also die Nummern der im realen Speicher sich befindlichen Seiten. Wenn die CPU eine Zeile des Hauptspeichers (32 bit) nachfragt, stellen die ersten 25 bit die Nummer der Seite dar, in der sich die Zeile im virtuellen Hauptspeicher befindet. Nach dieser Nummer wird in dem cache gesucht. Weil das auf Hardware-Ebene geschieht, geht das in unserem Modell in einem Schritt. Wird die Seiten-Nummer in Zeile i des cache gefunden, dann steht die nachgefragte Hauptspeicher-Adresse in Zeile i*128 + a des realen Hauptspeichers, wobei a die Zahl ist, die die rechten 7 bits der 32-bit-Adresse darstellen, a heißt der offset. Durch einen einfachen Addierer kann also die 20-bit-Adresse der nachgefragten Zeile gefunden werden. Wenn die nachgefagte Seiten-Nummer nicht im cache steht, nennt man diese Situation traditionellerweise Seitenfehler. In dem Fall wird die nachgefragte Seite von der Platte in einen freien Seitenrahmen im Hauptspeicher geladen, was natürlich lange dauert. Bei einem Seitenfehler stellt sich ebenso wie beim cache das Problem, welche Seite aus dem realen Hauptspeicher raus muß. Da bieten sich wieder die vom cache bekannte Algorithmen first-come-first-out oder least-recently-used an. Wenn die Seite nicht dirty ist, kann man sich das Zurückschreiben auf die Platte ersparen.
Es sollte klar sein, daß man mit diesem cache und der Platte dem Benutzer und der CPU vorgaukeln kann, daß der Hauptspeicher 232 Zeilen hat.
Auf der Platte müssen nicht notwendigerweise 225 Blöcke = 232 Zeilen reserviert werden. Es reicht ja, alle Seiten, die überhaupt jemals beschrieben wurden, zu speichern. Dazu kann man ein effezientes Verwaltungsystem für linear geordnete Daten benutzen (die Seiten können ja nach ihren Nummern geordnet werde), z.B. AVL-Bäme. Diese Verwaltungssysteme wurden in der Vorlesung Informatik 1 behandelt. So ein Verwaltungssystem ist dann ein Teil des Betriebssystems.
Die obige Lösung macht vielleicht klar, was das Prinzip des virtuellen Speichers ist und wie man sich eine Lösung vorstellen kann, aber sie hat den Nachteil, daß sie eine Hardware-Lösung ist: der cache ist ziemlich aufwendig. Es soll eine Lösung gefunden werden, die kaum zusätzliche Hardware braucht. Die erste Idee wäre, die Information, die der cache enthält, in den Hauptspeicher zu schreiben. Das gibt aber erstens Selbstbezüglichkeits-Probleme, siehe unten. Schlimmer ist aber, daß jetzt die Suche nach einer Seiten-Nummer im cache nicht mehr einen, sondern schlimmstenfalls 8192 Schritte (bei einem Seitenfehler) braucht, denn die Information im Hauptspeicher kann man nur sequentiell durchlaufen. Auch durch bessere Aufteilung der Information des cache kann man lange Durchlauf-Zeiten nicht verhindern.
Hier ist eine Lösung, die sogenannte einstufige Seitentabelle. In der folgenden vorläufigen Form hat sie immer noch einen riesigen zusätzlichen Hardware-Aufwand: Anstatt eines assoziativen cache's wird ein RAM-Speicher mit 225 Zeilen und Breite 20+1 gebaut. In Zeile i dieses RAM's steht die Nummer des Seitenrahmens, in dem die Seite i sich befindet, falls sie eingelagert ist. Ob sie das überhaupt ist, wird durch das rechte bit angezeigt. Mit dieser Hardware ist die Seitenverwaltung ein Kinderspiel, aber natürlich ist der Aufwand viel zu groß: Der neue Verwaltungs-RAM ist größer als der Hauptspeicher. Hier ist die Verbesserung, die diese Lösung praktikabel macht: Baue nicht einen RAM, der die Seitentabellen-Information speichert, sondern speichere diese 225 Zeilen in den ersten 218 Blöcken des im virtuellen Hauptspeicher ab (das ist ein 128-stel des virtuellen Hauptspeichers).
Das hört sich zuerst an, wie ein logischer Zirkel: Dort soll etwas stehen, zu dessen Verwaltung man die Information desselben braucht. Es funktioniert aber: Wir nehmen dazu an, daß die Seite 0 immer in einem bestimmten bekannten Seitenrahmen im Hauptspeicher steht. Wenn jetzt die CPU eine 32-bit-Hauptspeicheradresse a anfragt, wird zuerst berechnet, in welcher Seite s' der Teil der Seitentabelle steht, die für die Seite s zuständig ist, in der die Zeile a steht. Dann wird die Nummer s'' der Seite berechnet, in der die Zeile a' steht, die für die Seite s' zuständig ist. Ebenso werden s''' und s'''' aus der bit-Darstellung von a berechnet. Man mache sich klar, daß s'''' gleich 0 ist. Dann wird bei Seite 0 geschaut, ob Seite s''' im Hauptspeicher ist. Wenn ja, liest man dort die Information für s'', wenn nein, holt man s''' in den Hauptspeicher und liest die Information für s''. Dann bekommt man bei s'' die Information für s', und mit s' die Information für s. Wenn man s dann im Hauptspeicher stehen hat, kann man die CPU-Anforderung für Zeile a bearbeiten. Dieser einfache Algoritmus heißt tablewalk, das sukzessive Lesen der Zeilen a''', a'', a' wird Auflösen der Adresse a genannt.
Der Algorithmus ist eindeutig und er funktioniert, es bleibt nur die Frage, wer ihn durchführt: Die konzeptuell einfachste Lösung wäre eine zusätzliche Hardware-Schaltung, die die entsprechenden Schritte durchführt. Weil aber bei Seitenfehlern letztendlich doch das Betriebssystem für die Einlagerung der neuen Seiten aufgerufen werden muß, sollte der Algortihmus in Software implementiert sein, d.h. in Maschinencode. Weil aber die Abarbeitung eines Maschinenprogramms selber Hauptspeicher-Zugriffe braucht, wird hier ein Teufelskreis auftreten: zum Auflösen der virtuellen Adresse für das Programm braucht man das Programm: das ergibt eine Endlosschleife. Die Lösung ist, daß man im Hauptspeicher Seitenrahmen-Bereiche festlegt, in denen Seiten fest eingelagert werden und deren virtuelle Adressen damit nicht aufgelöst werden brauchen, die Seite 0 war ja schon ein Beispiel dafür. Man kann im tablewalk-Agorithmus diese Anfragen sofort herausfiltern. Das tablewalk-Programm selber lagert man dann in diesem Bereich des realen Hauptspeichers ein.