|
GRUNDLAGEN DER INFORMATIK WS 0203 - Vorlesung
|
Nachdem nun gezeigt wurde, wie sich au der Basis von 'Bits' einfache logische Schaltungen realisieren kann, mit denen man z.B. bestimmte Leitungen selektieren oder mit denen man addieren kann, soll heute das Grundprinzip eines Mikroprozessors erklärt werden.
Zu diesem Zweck wird eine einfache Hardwarearchitektur vorgestellt, die alle Eigenschaften enthält, die man benötigt, um einen Mikroprozessor zu realisieren. Zusätzlich wird eine einfache Assemblersprache eingeführt, mit der man dem Mikroprozessor 'Befehle erteilen' kann. Es bleibt dann das Problem zu lösen, wie der Mikrokode des Mikroprozessors aussehen müsste, um diese Assembler-Befehle im Bereich der Hardware umzusetzen.
Um zu wissen, was ein Mikroprozessor (auch 'Central Processing Unit' [CPU]) tut, wollen wir uns der Fragestellung von dem Programm aus nähern, das ein Mikroprozessor abarbeiten soll.
Vom Programmieren her wissen wir, dass ein Programm in einer Hochsprache (wie z.B. C) durch den Compiler in eine Assemblersprache übersetzt wird. Die Assemblersprache wiederum wird durch einen Assembler weiter übersetzt in sogenannten Binärcode. Der Binärcode kann in 8-Bit, 16-Bit oder anderen Grössen organisiert sein. Wir nehmen für die folgende Darstellung an, dass der Binärcode im 8-Bit-Format, also als Bytecode, organisiert ist (prominentes Beispiel ist die Java Virtual Machine; diese verarbeitet Bytecode).
Um das Problem anschaulicher zu machen, benutzen wir hier eine einfache Assemblersprache AL1. Hier eine kurze Liste von Assemblerbefehlen von AL1, die eine vereinfachte Untermenge der IJVM-Assembler-Befehle darstellen, wie sie im mic1sim-Simulator benutzt werden (siehe [TANENBAUM/GOODMAN]). In der ersten Spalte steht der Hex-Code, in der zweiten Spalte sogenannte Mnemonics (symbolische Abkürzungen) und in der dritten Spalte eine kurze Erklärung dessen, was dieser Code tut.
0x10 PUSH byte // Push byte onto stack 0x59 DUP // Copy top word on stack; push onto stack 0x60 ADD // Pop two words from stack; push their sum 0x7E AND // Pop two words from stack; push Boolean AND 0x99 IFEQ label // Pop word from stack; branch if it is zero 0x9F IF_ICMPEQ label // Pop two words from stack; branch if equal 0x84 INC varnum const // Add a constant to a local variable 0x15 LOAD varnum // Push local variable onto stack 0xB0 OR // Pop two words from stack; push Boolean OR 0xAC RETURN // Return from method with integer value 0x36 STORE varnum // Pop word from stack; store in local variable 0x64 SUB // Pop two words from stack; push their difference 0x13 LDC 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 0xFF HALT // halt the simulator 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
Will man mit diesen Befehlen ein Programm schreiben, dann muss man die folgende 'Form' einhalten:
.const
...
const_name value
...
.end-const
.main
.var
...
var_name
...
.end-var
...
program contents
...
label: commands
...
.end-main
Hier ein einfaches Beispiel für ein Assemblerprogram in der Sprache AL1 mit kurzen Erläuterungen.
/****************************** * * demo.al1 * * author: gdh * first: nov-28, 02 * last:- * * idea: simple demonstration of a small program * for the CPU-project * * 1 constant and 3 local variable * enter values for two variables * add the calues and then add the constant * output * ******************************************/ .const incr 10 .end-const .main .var a b c .end-var start: push x0 // Schiebe Byte=x0 auf Stapel dup // Dupliziere oberstes Element des Stapels dup store a //Kopiere oberstes Element vom Stapel nach a store b store c in // Lese Zeichen von Tastatur und schiebe auf Stapel store a // Schiebe Variable a auf den Stapel in store b load a load b add // Hole die zwei ersten Elemente vom Stapel // Addiere die Elemente; schiebe Ergebnis auf den Stapel store c ldc incr // Schiebe Konstante auf den Stapel load c add store c out // Schreibe oberstes Element vom Stapel auf Bildschirm push x1 return // Kehre zum aufrufenden Programm zurueck; // Dabei wird das oberste Element vom Stapel auf den Stapel des // aufrufenden Programms kopiert .end-main
Bevor jetzt die Frage geklärt werden kann, wie die CPU dieses Programm verarbeitet, muss noch geklärt werden, wie der Assembler die Assemlersprache in Bytecode übersetzt und wie dieser Bytecode im Speicher abgelegt wird.
Wir gehen hier in mehreren Schritten vor. Als erstes übersetzen wir das Assemblerprogramm in Bytecode und dann ordnen wir es im Speicher an.
/****************************** * * demo.al1 * * author: gdh * first: nov-28, 02 * last:- * * idea: simple demonstration of a small program * for the CPU-project * * 1 constant and 3 local variable * enter values for two variables * add the calues and then add the constant * output * ******************************************/ .const incr 10 .end-const .main .var a b c .end-var start: push x0 // x10,x0 dup // x59 dup // x59 store a // x36,0 store b // x36,1 store c // x36,2 in // xfc store a // x36,0 in // xfc store b // x36,1 load a // x15,0 load b // x15,1 add // x60 store c // x36,2 ldc incr // x13,0 load c // x15,2 add // x60 store c // x36,2 out // xfd push x1 // x10,x1 return // ac .end-main
Organisation des Speichers
Wie man sieht, werden die Bytes im Speicher nicht wahllos abgelegt, sondern folgen einem bestimmten Plan. Dieser ist für jde CPU verschieden. Unsere Demo-CPU setzt voraus, dass der eigentliche Programmcode ab der Speicherzelle '00' abgelegt wird, ein Byte hinter dem anderen. Im Anschluss werden die Konstanten gespeichert, dann die Variablen, und schliesslich der Stapel. Der Stapel ist zu Beginn leer; er kann während des Programmlaufs dynamisch wachsen oder wieder abnehmen.
Zu beachten ist allerdings, dass die ersten 3 Bytes des Programmkodes nicht direkt das Programm enthalten, sondern spezielle Informationen darüber, wo sich die Konstanten, die Variablen und der Stapel im Speicher befinden: Byte 0 := Länge des Programmcodes, Byte 1 := Anzahl Konstanten; Byte 2 := Anzahl Variablen. Damit ergibt sich für unser Beispielprogramm folgende Speicherbelegung:
/****************************** * * Anordnung der Bytes im Speicher: * *********************************/ ADDR MNEMONIC HEXCODE ------------------------------- PROGRAMM ------------------------------- 0000 // x22 Anzahl Bytes des Programms ab Byte 3 0001 // x1 Anzahl Konstanten (im Anschluss an Programm) 0002 // x3 Anzahl Variablen (Im Anschluss an Konstanten) 0003 push x0 // x10,x0 0005 dup // x59 0006 dup // x59 0007 store a // x36,0 0009 store b // x36,1 000b store c // x36,2 000d in // xfc 000e store a // x36,0 0010 in // xfc 0011 store b // x36,1 0013 load a // x15,0 0015 load b // x15,1 0017 add // x60 0018 store c // x36,2 001a ldc incr // x13,0 001c load c // x15,2 001e add // x60 001f store c // x36,2 0021 out // xfd 0022 push x10 // x10,x1 0024 return // ac --------------------------- KONSTANTEN --------------------------- 0025 incr 10 ( x3 + x22 = x25) --------------------------- VARIABLEN --------------------------- 0026 a (x25 + x1 = x26) 0027 b 0028 c --------------------------- STACK --------------------------- 0029 (x26 + x3 = x29)
Nachdem nun geklärt ist, wie unser Beispielprogramm vom Assembler übersetzt und dann vom Ladeprogramm im Speicher (d.h. im RAM := Random Access Memory) angeordnet worden ist, stellt sich nun die Frage, wie dieses Programm von der CPU abgearbeitet werden kann. Um diese Frage beantworten zu können, müssen wir uns die Hardware näher anschauen, die der CPU zur Verfügung steht, und müssen klären, was genau die einzelnen Oprationen sind, die vollzogen werden müssen, um zu einem Ergebis zu kommen.
Das folgende Bild zeigt die Hardwarearchitektur, die wir für unsere CPU annehmen (eine etwas ausführlichere Version findet sich im Buch von [TANENBAUM/GOODMAN 2001]).
Hardwarearchitektur für CPU
Als erstes wird ein kurzer Überblick über die gesamte Hardware gegeben, dann wird in einzelnen Schritten die Frage beantwortet auf welche Weise die CPU das Programm im Speicher verarbeiten kann.
Generell soll gelten, dass alle Einheiten mit 8-Bit (= 1 Byte) arbeiten, ausgenommen der Speicher für den Microcode; dieser hat eine Breite von 8+2+8+3+8+3 = 32 Bit, die benutzt werden.
RAM (Random Access Memory): Der Arbeitsspeicher, in den das Demoprogramm ab der Adresse 00 abgelegt worden ist (Anordnung siehe oben).
AR (Adress Register): Das Adressregister kann eine 8-Bit Zahl aufnehmen und über einen Adressbus mit 8 Leitungen die Speicherzellen im RAM adressieren. Normalerweise wird es nur für die Speicherbereiche benutzt, die oberhalb des Programmkodes liegen.
DR (Data Register): Das Datenregister ist ebenfalls über einen Datenbus mit 8 Leitungen mit dem RAM verbunden. Es kann über diese Leitungen entweder das 8-Bit-Wort lesen ('read', rd) oder schreiben ('write', wr), das aktuell vom Adressregister selektiert wird.
PC (Program Counter): Der Programmzähler ist ähnlich wie das Adressregister auch über 8 Adressleitungen mit dem RAM verbunden und kann einzelne Speicherzellen im RAM adressieren. Normalerweise beschränkt sich der PC auf jene Speicherzellen, die Programmkode enthalten. Im Unterschied zum Adressregister, das beliebige Adressen laden kann, ist der Programmzähler auf die Abarbeitung des Programmcodes im RAM fixiert. Unsere Demo-CPU nimmt an, dass das Programm ab Speicheradresse 00 abgelegt ist, und zwar sequentiell, ein Byte hinter dem anderen. Erst kommt immer das Byte, das einen Befehl repräsentiert (z.B. store mit wert x36), dann kommen möglicherweise Argumente des Befehls (z.B. der Name einer Variablen a als Offset zu der Adresse, ab der die Variablen im Speicher liegen), dann wieder der nächste Befehl, usw. Der Programmzähler PC beginnt also mit der Adresse 00, und nach jedem Zyklus erhöht sich der Wert von PC um 1. Diese starre Abfolge kann nur durch Befehle durchbrochen werden, die 'Sprünge' ermöglichen, wie z.B. die beiden Befehle 'IFEQ label' und 'IF_CMPEQ label'. Bei diesen Befehlen wird in Abhängigkeit vom Ergebnis der Operation an die Stelle im Programm 'gesprungen', die durch 'label' markiert ist. In diesem Fall wird also der PC nicht einfach um 1 erhöht, sondern er bekommt den Wert der Speicherzelle, die mit dem 'label' verknüpft ist. Zu beachten ist, dass zu Beginn eines Programms die ersten 3 Bytes Informationen über die Anordnung des Programms, der Konstanten, der Variablen und des Stapels im Speicher enthalten (Würde man noch Unterprogramme benutzen, was hier nicht getan wird, würde der Programmkode für Unterprogramme zu Begin auch Informationen über Programmlänge und Variablen enthalten).
BR (Byte Register): Das Byteregister ist ebenfalls über 8 Leitungen mit dem RAM verbunden. Es kann den Inhalt jener Speicherzelle lesen ('fetch'), die gerade vom PC selektiert wird. Das Byteregister enthält also jeweils ein Byte aus dem auszuführenden Programm.
SP (Stack Pointer): Der Stapelzeiger enthält die Adresse des aktuell obersten Elementes von jenem Speicherbereich, der als Stapel dienen soll. Sobald ein Wert auf den Stapel geschoben wurde, wird die Adresse des Stapels automatisch um 1 erhöht. Wird umgekehrt ein Element vom Stapel gelesen, dann wird die Adresse automatisch um 1 vermindert.
LV (Local Variables): Analog wie der Stapelzeiger die Adresse des ersten Bytes in jenem Speicherbereich, in dem die lokalen Variablen abgelegt sind.
CP (Constant Pointer): Analog zu SP und LV die aktuelle Adresse des ersten Feldes des Konstantenbereiches.
H (Universal Register) H ist ein Allzweckregister, das vor allem dann benutzt wird, wenn die ALU Operationen mit zwei Argumenten ausführen muss.
ALU (Arithmetical and Logical Unit) und Carry: Die arithmetische und logische Einheit kann folgende
Operationen ausführen:
Partielles Freischalten von zwei Eingängen A und B (ENA := Enable A und ENB := Enable B)
Stellenkomplement von A (INVA)
Übernahme des Carry-Bits in das niederwertigste Bit (INC, wie Addition von 1)(Die Kombination von INVA und INC erzeugt ein 2er-Komplement, so dass auf diese Weise die Subtraktion möglich ist)
AND von A und B
OR von A und B
NOT von B
A + B (arithmetische Addition)
In der Schaltung entspricht dem Eingang A der Wert aus dem H-Register und dem Eingang B der Wert vom B-Bus.
SHIFT: das Shift-Register bekommt die Ausgabe von der ALU und kann diese Bits entweder um 1 Bit nach links schieben (das 'neue' Bit rechts erhält den Wert 0) oder um 1 Bit nach rechts, wobei das höchstwertige Bit ('most significant Bit') aber erhalten bleibt.
C-BUS: die Datenleitungen des C-BUS verbinden den Ausgang des Shiftregisters mit allen anderen Registern. Dies bedeutet, dass die Ausgabe der ALU in alle Register geschoben werden kann.
B-BUS: ähnlich verbindet der B-Bus alle Register (ausser AR) mit dem B-Eingang der ALU, d.h. der Inhalt von jedem der Register kann in die ALU geschoben werden.
3-zu-8 Dekodierer: Da nur immer ein Register zur gleichen Zeit auf den B-Bus schreiben darf, muss es eine Schaltung geben, die dasjenige Register auswählt, das schreiben soll. Dazu dient die 3-zu-8 Dekodierschaltung. Sie wird angesteuert von 3 Bits aus dem Microkode-Ausgaberegister. Nur dasjenige Register, das selektiert ist, kann auf den B-Bus schreiben.
MPC (Microcode Program Counter): so ähnlich, wie der Programmzähler PC die Bytes aus dem Programm im RAM auswählt, so wählt der Microprogrammzähler MPC im Mikrokode-Speicher diejenige Speicheradresse aus, deren Microbefehl jetzt ausgeführt werden soll. Im Beispiel wird angenommen, dass der MPC aus 1+8 Bit besteht. Die 8 niederwertigen Bits bekommen ihren Wert entweder aus dem Byteregister BR oder aus den Adress-Bits des Microkode-Ausgaberegisters. Wenn das Byteregister BR einen Befehl aus dem RAM liest (eine 8-Bit-Zahl), dann ist diese Zahl identisch mit der Adresse dieses Befehls im Microkode-Speicher. Dies bedeutet nicht notwendigerweise, dass der Microkode-Befehl nur eine Adresse umfasst, sondern nur, dass er an dieser Stelle im Microkode-Speicher beginnt. Wenn der Microkode-Befehl mehr als eine Stelle im Microkode-Speicher umfasst, dann wird die nachfolgende Stelle über die Adressbits im Microkode-Ausgaberegister aktiviert und von dort in den MPC zurückgeladen.
Microkode: Der Microcode hat die Aufgabe, die Befehle aus dem Assemblerprogramm, das im Byteformat im
RAM vorliegt, in entsprechende Aktionen im Bereich der Hardware umzusetzen. Physikalisch wird dies dadurch erreicht, dass
jeder Microkode-Befehl aus einem 32-Bit-Muster besteht, das in das Microkode-Ausgaberegister übertragen werden kann. Die
einzelnen Bits in diesem Microkode-Ausgaberegister können dann unterschiedliche Bausteine steuern.
Nach diesen Vorbereitungen kann man nun prinzipiell verstehen, wie die CPU das Programm, das im RAM als Bytecode ab Adresse 00 vorliegt, abarbeitet, ohne dass hier auf die Details des Microkodes eingegangen werden muss (dies wird später in speziellen Vorlesungen geleistet. Für diejenigen, die es 'jetzt' schon wissen wollen, sei nochmals auf das gut verständliche Buch von [TANENBAUM/GOODMAN] hingewiesen.).
Die erste Frage, die man klären muss, ist die, woher die CPU 'weiss', 'was sie tun soll'? Anhand der vorausgehenden Erklärungen ist klar, dass der Einstiegspunkt für alles weitere der Programmzähler PC ist. Dieser ist so eingestellt, dass er zu Beginn die Adresse 00 enthält; dies ist die erste Speicherzelle im RAM und diese enthält (nach Vereinbarung) das erste Byte des auszuführenden Programms. Ferner ist bekannt, dass nach Vereinbarung die ersten 3 Bytes Informationen über die Anordnung der Bytes im RAM enthalten.
Zuerst werden die Register CP, LV und SP gesetzt. Mit PC=x00 kann das Byteregister BR den Wert x22 (Länge des Programms ab x3)lesen, BR=x22. Der Inhalt von BR kann über den B-Bus in die ALU und von dort in das Register H gebracht werden. Dann kann man H um den Wert 3 erhöhen, indem man rechnet: H = H + 1 +1 +1; CP = H; d.h.zum Wert von H wird dreimal der Wert 1 addiert. Dies ergibt die Startadresse x25 für die Konstanten. Dieses Ergebnis wird dann von der ALU auch in das Konstantenregister CP kopiert. Dann wird PC+1 erhöht, also PC=x1; der Inhalt von x1 kann nach BR geholt werden: BR=x1 (Anzahl der Konstanten). Der Inhalt von BR kann in die ALU (Eingang B) gebracht werden. Mit H = H+1; LV = H; wird die Startadresse der Variablen berechnet (x26) und in das Register LV gebracht. Dann wird wieder PC+1 erhöht und PC=x2. Der Inhalt von x2 (Anzahl Variablen) kann nach BR=x2 geholt werden. Mit H = H + BR; SP = H; bekommt man die Startadresse des Stapelzeigers, also x26 + x3 = x29.
Nach diesen Vorbereitungen kann nun die eigentliche Abarbeitung des Programms beginnen. Dies sei hier in Kurzform für die ersten Befehle beschrieben:
PC+1; fetch; BR=x10; MPC=BR; x10 ist die Adresse des Befehls push im Microkode-Speicher. Der Befehl wird aktiviert. Er soll das nächste Byte im RAM auf den Stapel schieben. D.h. Das Adressregister muss auf die Adresse des Stapels eingestellt werden, dann muss der Inhalt von Speicherzelle x4 auf den Stapel geschoben werden. Also AR = SP
PC+1; fetch; BR=x0; DR = BR (Inhalt von BR über die ALU nach DR); wr (schreibe Inhalt von DR an die Adresse von AR).
PC+1; fetch; BR=x59; MPC=BR; x59 ist die Adresse des Befehls dup im Microkode-Speicher. Der Befehl wird aktiviert. Er soll den obersten Wert des Stapels verdoppeln. D.h. Das Adressregister muss auf die Adresse des Stapels eingestellt werden, dann muss der Inhalt des Stapels gesichert werden. Die Adresse des Stapels wird um 1 erhöht; dann wird der gesicherte Wert des Stapels an die neue Adresse geschrieben. Also: AR = SP; rd; (DR=x0); SP = SP+1; AR = SP; wr;
PC+1; fetch; BR=x59; MPC=BR; Abarbeitung wie zuvor.
PC+1; fetch; BR=x36; MPC=BR; x36 ist die Adresse des Befehls store im Microkode-Speicher. Der Befehl wird aktiviert. Er soll das oberste Element des Stapels in die Variable a kopieren. Dazu muss das Adressregister auf die Adresse des obersten Elementes gesetzt werden; das Element wird nach DR kopiert. Dann wird anhand des nächsten Bytes im RAM die Variable ermittelt und der Wert von DR dorthin kopiert; der Stapel wird um 1 vermindert. Also AR = SP; rd (BR=x0); SP = SP -1;
PC+1; fetch; BR=x0 (Offset der Variablen a von Startadresse in LV); H = LV + BR (Adresse von der Variablen a); AR = H; wr (der Inhalt von DR, das immer noch das oberste element des Stapels enthält, wird nach a geschrieben);
Bilden sie ein Team von 1-5 Mitgliedern
Erstellung Sie gemeinsam einen Texte mit Namen und Matr.Nr. der AutorenInnen. Abgabe einer Kopie des Textes an den Dozenten vor Beginn der nächsten Vorlesung.
Kurzpräsentation der Lösung als Team vor der gesamten Gruppe. Detailliertere Besprechung während der Übungsstunde (für Vergabe von Punkten an jedes Teammitglied Pflicht!).
Versuchen Sie in dem Text Antworten auf folgende Aufgaben zu formulieren:
Versuchen Sie für mindestens drei weitere Befehle des Demoprogramms herauszufinden, welche Operationen im Bereich der Hardware stattfinden müssten, damit die Befehle wie gewünscht ausgeführt würden. Formulieren sie dies als Text. Für diese Aufgabe kann es 1-3 Punkte geben.