Rechnerarchitektur und Eingebettete Systeme - Informatik

Prof. Rolf Drechsler & Jannis Stoppe M.Sc., drechsle/[email protected], MZH 4330/1362
Dipl.-Math.techn. Oliver Keszöcze, [email protected], MZH 4300
3. Übungsblatt zur Vorlesung
Rechnerarchitektur und Eingebettete Systeme
Der Y86-Prozessor
Im Rahmen der nächsten Aufgaben wird ein abstraktes Modell einer Variante des Y86-Prozessors [?, ?]
in Software entworfen und zu implementiert. Das abstrakte Modell des Y86-Prozessors entspricht einem
Simulator für den Befehlssatz (engl. Instruction Set Simulator ISS) des Prozessors.
Architektur
Der Y86-Prozessor entspricht einer vereinfachten 32-Bit Intel Architektur (IA), die von R. Bryant und
O’Hallaron für Lehrzwecke entwickelt wurde. Der Name „Y86“ ist von der gängigen Abkürzung „X86“
für Intel-Prozessoren abgeleitet. Eine Variante des ursprünglichen Y86-Prozessors ist in Biere et al. [?]
beschrieben. Diese Variante des Prozessors dient als Grundlage für die praktische übungsaufgabe.
Der Y86-Prozessor verfügt über acht Datenregister: eax, ecx, edx, ebx, eex, efx, esi, edi. Jedes
Register kann ein Datenwort (8-Bit) speichern. Die Register esi und edi speichern nicht nur Daten,
sondern sind zusätzlich für die Indizierung von Datenfeldern gedacht (siehe Erläuterung zu ea weiter
unten).
Zusätzlich zu den Datenregistern verfügt der Y86-Prozessor über ein Register Instruction Pointer IP,
welches die Adresse des nächsten auszuführenden Befehls im Speicher beeinhaltet, und ein Flag-Register
Zero-Flag ZF. Flag-Register speichern Informationen über den letzten durch einen Prozessor ausgeführten Befehl. Das Flag-Register ZF ist genau ein Bit breit und wird gesetzt, wenn das Ergebnis der
letzten arithmetischen Operation null war.
Index
Name
0
eax
1
ecx
2
edx
3
ebx
4
eex
5
efx
6
esi
7
edi
Befehlssatz
Der Y86-Prozessor besitzt eine von-Neumann-Architektur, d.h. Befehle und Daten sind in einem gemeinsamen Speicher abgelegt. Jede Speicherstelle fasst genau 1 Byte (8 Bit). Um den Inhalt einer Speicherstelle mit Adresse ea zu bezeichnen, schreiben wir Mem[ea].
Der Befehlssatz des Y86-Prozessors besteht aus nur acht verschiedenen Befehlstypen. Die Länge der Instruktionsworte variiert zwischen einem und drei Byte. Die Befehle sind in Tabelle 1 zusammengefasst.
In der Tabelle sind die Kürzel (Mnemonics) der Instruktionen des Y86-Prozessors aufgeführt, gefolgt
von einer Beschreibung der Instruktion in Pseudocode, und dem Maschinencode. Jeder Kasten in der
Spalte Maschinencode entspricht einem Byte. Die Abkürzungen RS und RD bezeichnen das Quell- (engl.
register source) und das Zielregister (engl. register destination).
Mit den Befehlen add und sub werden zwei arithmetische Operationen unterstützt. Der Befehl jnz ist
eine bedingte Sprunginstruktion: Der Sprung wird ausgeführt, wenn die letzte Berechnung keine 0 als
Ergebnis hatte (also ZF auf 0 gesetzt ist). Der Befehl RRmov kopiert den Inhalt eines Registers in ein
anderes Register, während der Befehl RMmov den Inhalt eines Registers in den Speicher schreibt, und
der Befehl MRmov einen Wert aus dem Speicher liest. Der Befehl hlt hält den Prozessor an.
1
Mnemonic
Bedeutung
RD := RD + RS
Maschinencode
01hex
add
11|RS|RD
sub
RD := RD - RS
29hex
11|RS|RD
jnz
if !ZF then IP := IP + dist
75hex
dist
RRmov
RD := RS
89hex
11|RS|RD
RMmov
MEM[ea] := RS
89hex
01|RS|110
Displacement
MRmov
RD := MEM[ea]
8bhex
01|RD|110
Displacement
hlt
Prozessor anhalten
f4hex
Table 1: Befehlssatz Y86
Bei acht adressierbaren Registern sind drei Bit zur eindeutigen Adressierung ausreichend. Um z.B. den
Wert von ecx (Register 1) nach edx (Register 2) zu kopieren, würde man die Instruktion RRmov edx,
ecx mit dem Opcode 89hex und dem weiteren Byte (11 001 010)2 = CAhex verwenden.
Der Wert dist für die Instruktionen jnz ist eine im Zweierkomplement kodierte ganze Zahl, die die
Sprungweite angibt. Beispiel:
01110101 00001111 // if !ZF then IP := IP + 15
Der Wert Displacement bei RMmov und MRmov ist eine Zahl im Zweierkomplement, die zur Berechnung
der Adressen für Speicherzugriffe verwendet wird. Die effektive Adresse (ea) wird als Summe des Registers esi (falls aus dem Speicher gelesen wird) oder edi (falls in den Speicher geschrieben wird) und
des Displacement aus dem Instruktionswort berechnet. Beispiel:
10001001 01100110 11110000 // MEM[edi + -16] := eex
Aufgabe 1
(5 Punkte)
Der Speicher, der dem Y86-Prozessor zur Verfügung steht, soll für die Implementierung auf 80 Byte
begrenzt werden. Beim Ausführen des ISS soll der Speicher aus einer Datei eingelesen werden, wobei
der Dateiname als Parameter über die Kommandozeile an den ISS übergeben wird. In dieser Aufgabe
sollen die Befehle im Speicher der Reihe nach eingelesen und wie in Tabelle 1 unter Bedeutung ausgegeben werden. Hierbei sollen die Variablen des Befehls soweit wie möglich ausgefüllt werden, z.B.
eax := eax + ebx oder MEM[edi + 7] := ebx. Es ist zu beachten, dass die Befehle je nach Befehl
durch Maschinencode von 1 bis 3 Bits dargestellt werden kann. Sollte ein Bit nicht dem Maschinencode
eines Befehls zuweisbar sein, so soll für dieses Bit Error ausgegeben werden und das Einlesen ab dem
nächsten Bit fortgesetzt werden. Ein Bit soll auch als nicht zuweisbar gewertet werden, wenn es selbst
zwar korrekt ist, aber folgende Bits nicht dem Muster entsprechen, z.B. auf ein 01hex welches einem add
entspricht folgt ein Bit, welches nicht mit 11 beginnt.
Das Modell ist in Java zu entwickeln. Zu der Implementierung soll ein Übersichtstext beschrieben werden. Dieser Text soll die Charakteristika der Implementierung (Eingabe, Ausgabe, Besonderheiten der
Implementierung) beschreiben und den Programmablauf verdeutlichen. Es soll kein Quellcode ausgedruckt werden; dieser ist an den Tutor zu schicken.
In Stud.IP werden eine Speicherdatei mit zugehöriger Ausgabe bereitgestellt. Zusätzlich befindet sich
dort ein Programm, mit dem entsprechender Speicherdateien erstellt werden können.
Aufgabe 2
(10 Punkte)
Die Implementierung des ISS eines Y86-Prozessors soll in dieser Aufgabe fortgesetzt werden.
Entsprechend der Definitionen sollen die Befehle im mitgegebenen Speicher nun ausgeführt werden.
Hierbei soll für jeden Befehl eine Ausgabe gemacht werden, die den aktuellen Speicher und den Inhalt
der Register nach Ausführung des Befehls sowie den Befehl selbst darstellt. Diese Ausgabe soll im folgenden Format sein, wobei der Befehl wie in der letzten Aufgabe ausgegeben werden soll. Alle Bytes
werden als Hexzahl dargestellt. Der Speicher soll in 5 Zeilen à 16 Byte dargestellt werden, wobei nach
je 4 Bytes ein größerer Abstand stehen soll.
2
MRmov edx, [ESI+0x17]
IP:
9
EAX:
EEX:
ZF: 0
MEM: 29
56
00
00
00
9 ECX:
0 EFX:
f6
1b
00
00
00
20
29
00
00
00
c0
d1
00
00
00
ff EDX:
0 ESI:
29
75
00
00
00
db
f0
00
00
00
8b
f4
00
00
00
56
01
00
00
00
17
00
00
00
00
1 EBX:
0 EDI:
01
00
00
00
00
d0
00
00
00
00
01
0a
00
00
00
c3
00
00
00
00
2d
0
89
00
00
00
00
c1
00
00
00
00
8b
00
00
00
00
Nach erfolgreicher Abarbeitung eines Befehls wird der PC um eins erhöht. Die Ausnahme bildet hier
offenbar der JNZ Befehl. Beachtet, dass Fälle wie PC = PC + 255 auftreten können. In diesem Fall
sollte Simulator mit einer Fehlermeldung abbrechen.
Zu Beginn der Ausführung ist der Inhalt aller Register sowie des Befehlszeigers 0. Für die Aufgabe kann
die eigene Lösung oder die Musterlösung der Veranstaltung verwendet werden, welche auf Anfrage
herausgegeben wird.
Auch zu dieser Aufgabe ist ein Übersichtstext anzufertigen, der die Charakteristika der Implementierung beschreibt und den Programmablauf verdeutlicht. Auch hier wird bitte kein Quellcode ausgedruckt, sondern nur an den Tutor geschickt.
Aufgabe 3
(5 Punkte)
Nun soll auf dem Y86 progammiert werden. Die Aufgabe besteht darin, die n-te verallgemeinerte
Fibonacci-Zahl zu berechnen1 . Wenn die Berechnung ausgeführt wurde, soll der Rechner angehalten
werden. “Verallgemeinert” bedeutet in diesem Kontext, dass die Startwerte f1 und f2 frei wählbar sind
(auch negativ!). Die berechnet Zahl soll in die letzte Speicheradresse (also mit Index 79) gespeichert
werden.
Über- und Unterläufe der Zahlen sollen wie üblich behandelt werden (also wie java das halt macht; bei
geschickter Programmierung ist also nichts zu tun).
Während ihr das Programm erstellt, könnt ihr von einem beliebigen Speicherzustand des Rechners ausgehen2 . Die einzige Ausnahme ist, dass sich der Wert für n an der an der vierten Speicheradresse (also
mit Index 3) befindet.
Die Abgabe dieser Aufgabe erfolgt derart, dass in der Abgabe die Mnemonics abgedruckt werden und
zusätzlich die Memory-Datei (siehe Aufgabe 1) an den Tutor geschickt wird.
Beachtet, dass zur Bearbeitung dieser Aufgabe eine erfolgreiche Bearbeitung der vorherigen beiden
Aufgaben nicht nötig ist. Es hilft aber natürlich ungemein, einen laufenden Simulator zur Hand zu
haben, der es einem erlaubt, seinen Code zu verifizieren.
References
[1] Armin Biere, Daniel Kroening, Georg Weissenbacher, and Christoph M. Wintersteiger. Digitaltechnik
— Eine praxisnahe Einführung. Springer-Verlag Berlin Heidelberg, 2008.
[2] Randal E. Bryant and David R. O’Hallaron. Computer Systems, A Programmer’s Perspective. Prentice
Hall, 2003.
1 https://de.wikipedia.org/wiki/Fibonacci-Folge
2 Das
liegt einfach daran, dass wir keinerlei Möglichkeit definiert haben, Werte in den Rechner zu bekommen. Die Register sind,
wie in Aufgabe 2, im Zustand 0. Der PC startet ebenfalls mit 0.
3

Download Report