|
|
RECHNERARCHITEKTUR WS 0203 - Vorlesung mit Übung
|
Der Ausgangspunkt war der Begriff der Berechenbarkeit, der im Begriff der Turingmaschine seine bislang konkreteste Ausprägung gefunden hat; ein stärkeres Konzept der Berechenbarkeit als jenes, das im Konzept der Turingmaschine konkretisiert wurde (samt den dazu äquivalenten Formalismen) wurde bislang nicht gefunden. Das Konzept der Turingmaschine ist jedoch ein rein logisches Konzept eines Automaten, keine real existierende Maschine. Es wurde aufgezeigt, wie man die Idee logischer Zustände umsetzen kann in physikalische Zustände. Es wurden Beispiele von physikalischen Gattern gezeigt, die man so anordnen kann, dass sich damit beliebig komplexe Schaltungen realisieren lassen, die den Konzepten der Aussagenlogik entsprechen. Zusätzlich wurde gezeigt, wie sich Signale speichern lassen und wie sich sequentielle Automaten (= endliche Automaten) physikalisch realisieren lassen. Damit rückte das Ziel greifbar nahe, das Konzept einer Turingmaschine vollständig in Hardware als konkrete Maschine realisieren zu können. Dieser letzte Schritt soll nun vollzogen werden. Anhand einer vergleichsweise einfachen -und doch schon recht komplexen- konkreten Schaltung eines einfachen Mikroprozessors soll gezeigt werden, wie sich mittels einer Assemblersprache eine Maschine steuern lässt, die formal den Fähigkeiten einer Turingmaschine (allerdings mit endlichem Band) entspricht. Der Kern dieser Maschine ist ein Mikroprogramm, das im Prinzip eine universelle Turingmaschine realisiert, die eine Anordnung von Gattern so steuern kann, dass sich die flexiblen Schreib-Lese-Operationen einer Turingmaschine nachbilden lassen.
Die erste Frage, die man sich stellen kann ist die, wie denn solch eine konkrete Maschine aussehen müsste, die die wesentlichen Eigenschaften einer universellen Turingmaschine physikalisch umsetzt.
Für die Umsetzung gilt die Annahme, dass uns die physikalischen Bausteine zur Verfügung stehen, die wir bislang kennengelernt haben.
Von der universellen Turingmaschine wissen wir, dass sie letztlich als Programm einen endlichen Automaten umfasst, der von einem Band die Beschreibung einer deterministischen Turingmaschine einlesen kann und das Verhalten dieser Maschine simuliert. Bei dieser Simulation kann der Schreib-Lese-Kopf frei auf dem restlichen Band hin- und herbewegt werden. Grundsätzlich kann auch das Programm der zu simulierenden Turingmaschine verändert werden.
Man muss also von einer physikalischen Realisierung einer universellen Turingmaschine erwarten können, dass es zu den eben geschilderten Charakteristika einer universellen Turingmaschine entsprechende Strukturmerkmale in der physikalischen Realisierung gibt. Das nachfolgende Schaubild, das die Vorlesungen der nächsten Wochen begleiten wird, zeigt, dass es solch eine physikalische Struktur geben kann. Das Bild ist dem schon mehrfach zitierten Buch von [TANENBAUM/GOODMAN 2001] entnommen, dessen Darstellung im Kap.4 wir hier im Wesentlichen folgen (u.a. deswegen, weil es begleitend zum Buch einen freien Simulator mic1 gibt, der der hier benutzte Mikroarchitektur entspricht).
Microarchitecture
Format of one Command of the Micro Code
1-Bit-ALU (x Anzahl Bits)
Von den vielen Details, die das erste Bild zeigt, interessiert uns zu Beginn nur, ob und wie sich eine prinzipielle Entsprechung zum Konzept der universellen Turingmaschine herstellen lässt.
Da ist zunächst mal der graue Block, der das Mikroprogramm ('microcode') enthält. Funktionell entspricht das Mikroprogramm dem endlichen Automaten der Turingmaschine, der das Programm darstellt. Genauso, wie sich ein Turingmaschinenprogramm aus einzelnen Produktionen der Form < q, a, q', b,m> zusammensetzte, so setzt sich auch das Mikroprogramm aus lauter einzelnen Mikroprogramm-Befehlen zusammen, die so aufgebaut sind, dass sie abhängig von den Signalen, die sie 'lesen', feste Nachfolgeoperationen auswählen.
Eine Produktion eines Turingmaschinenprogramms konnte im wesentlichen nur etwas in ein aktuelles Feld auf dem Band schreiben und ein neues Feld zum Lesen/ Schreibn festlegen. Dies kann auch ein Mikroprogramm-Befehl bewirken. Über ein Ausgaberegister ist es möglich, Register zum Adressieren eines Speichers (MAR) und zum Lesen/ Schreiben der Daten aus dieser Speicherzelle (MDR) zu steuern. Damit kann die Beschreibung einer zu simulierenden Turingmaschine in Form eines Objektkodes im Speicher gelesen werden. Der aktuelle Zustand der zu simulierenden Turingmaschine wird im Register PC ('programm counter') gespeichert.
Abhängig von dem Zustand, der vom Speicher für die zu simulierende Turingmaschine eingelesen wird, müssen bestimmte Operationen ausgeführt werden. Es ist Aufgabe des Mikroprogramms, festzulegen, welche konkreten Schaltzustände im Bereiich aller Schaltzustände herbeizuführen sind, um diese geforderten Aktionen umzusetzen.
Im Gegensatz zum abstrakten logischen Konzept der Turingmaschine, die nur Bandinhalte Lesen und Schreiben konnte und auf diese Weise indirekt komplexe Funktionen realisieren konnte, kann die vorliegende Struktur eines Mikroprozessors eine Reihe von elementaren arithmetischen und logischen Operationen direkt ausführen. Dies geschieht mit Hilfe der ALU (:= 'arithmetisch logische Einheit', 'arithmetical logical unit') und einer Reihe von unterstützenden Registern.
Um die genaue funktionsweise dieses Mikroprozessors verstehen zu können, werden wir uns Schritt für Schritt an die Abläufe heranarbeiten.
Wir beginnen damit, dass wir die Beschreibung der zu simulierenden Turingmaschine in Form eines Assemblerprogramms anschauen, dass dann vom Assembler in einen Binärcode übersetzt wird, der dann diejenige Beschreibung ist, die unser Mikrorpzessor direkt 'verstehen' kann.
Von der universellen Turingmaschine wissen wir, dass die zu simulierende Turingmaschine in einem vorher zu vereinbarenden Alphabet auf das Band zu schreiben ist. Für universelle Turingmaschinen unter den physikalischen Randbedingungen, die wir bislang angenommen haben, heisst dies, dass diese Beschreibung letztlich als Binärcode vorliegen muss, da nur ein solcher Code von den Schaltbausteinen verarbeitet werden kann. Und da solch ein Binärcode für ein durchschnittliches menschliches Gehirn recht unbequem ist, um komplexe Sachverhalte darin zu repräsentieren, vereinbart man abstraktere Darstellungsebenen, die dann von einer Maschine 'automatisch' in geeigneten Binärcode übersetzt werden. Eine solche vergleichsweise einfache Assemblersprache ist die folgende, die den Simulator mic1 steuert, der wiederum die oben geschilderte Mikrostruktur simuliert. Nebenbei sei bemerkt, dass dieser Assembler zugleich ein Assembler für die Java Virtual Machine (JVM) ist, beschränkt auf Integervariablen (I), also IJVM.
// configuration file for IJVM Assembler 0x10 BIPUSH byte // Push byte onto stack 0x59 DUP // Copy top word on stack; push onto stack 0xA7 GOTO label // Unconditional jump 0x60 IADD // Pop two words from stack; push their sum 0x7E IAND // Pop two words from stack; push Boolean AND 0x99 IFEQ label // Pop word from stack; branch if it is zero 0x9B IFLT label // Pop word from stack; branch if it is less than zero 0x9F IF_ICMPEQ label // Pop two words from stack; branch if equal 0x84 IINC varnum const // Add a constant to a local variable 0x15 ILOAD varnum // Push local variable onto stack 0xB6 INVOKEVIRTUAL offset // Invoke a method 0xB0 IOR // Pop two words from stack; push Boolean OR 0xAC IRETURN // Return from method with integer value 0x36 ISTORE varnum // Pop word from stack; store in local variable 0x64 ISUB // Pop two words from stack; push their difference 0x13 LDC_W index // Push constant from constant pool onto stack 0x00 NOP // Do nothing 0x57 POP // Delete word on top of stack 0x5F SWAP // Swap the two top words on the stack 0xC4 WIDE // Prefix instruction; next instruction has 16-bit index 0xFF HALT // halt the simulator 0xFE ERR // print ERROR and halt 0xFD OUT // Pop a word from the stack and use the low order 8-bits as an ASCI character to display on screen 0xFC IN // Read a character from standard input and put it in the low order 8-bits of a word pushed onto the stack
Operanden byte, const, varnum = 1 Byte, disp, index, offset = 2 Bytes
Die Gesamtheit dieser Assemblerbefehle setzt eine bestimmte Umgebung voraus. Im folgenden Bild ist diese skizziert.
Outline of Physical UTM
Dem Band der universellen Turingmaschine entspricht der Speicher und dem Programm die konkrete Maschine mit den Komponenten Mikroprogramm, Register und ALU.
Der Speicher ist in vier Bereiche aufgeteilt:
Im Bereich Methods steht der Programmtext, eine feste Folge von Befehlen. Unter anderem gibt es auch den Sprungbefehl GOTO Label, durch den die Fortsetzung der Abarbeitung zu der Stelle im Programm geschickt wird, die durch Label markiert ist. Ferner kann man mit dem Befehl INVOKEVIRTUAL offset ein Unterprogramm aufrufen, aus dem man mittels IRETURN wieder zurückkehren kann.
Der Bereich Konstanten enthält Konstanten, die zu Beginn der Abarbeitung festliegen.
Der Bereich Variablen enthält die Speicherbereiche der Variablen, die auch fest liegen.
Variabel ist nur der Bereich Stack. Dem Stack kann beständig ein Element hinzugefügt oder, falls vorhanden, weggenommen werden.
So, wie die universelle Turingmaschine sich auf dem Band spezielle Bereiche reserviert hatte, um sich den aktuellen Zustand und das aktuelle Symbol 'zu merken', so hat auch die konkrete Maschine vier Register, in denen sich Zeiger auf die vier Speicherbereiche befinden.
PC: der Programmzähler ('program counter') speichert die Byteadresse des aktuell auszuführenden Befehls aus dem Bereich Methods.
CPP: speichert die Wortadresse des ersten Wortes aus dem Konstantenpool.
LV: speichert die Wortadresse des ersten Wortes aus dem Variablen-Rahmen.
SP: speichert die Wortadresse des ersten Wortes aus dem Operandenstapels.
Während der Übung.