Post on 20-Oct-2019
transcript
Wiederholungsklausur
Einführung in die RechnerarchitekturProf. Dr. Arndt Bode
Sommersemester 201711. April 2017
Name:
Vorname:
Matrikelnummer:
Geburtsdatum:
Hörsaal:
Platz:
Unterschrift:
Ergebnis:
Aufgabe 1 2 3 4 Ges. Note
Punkte
Korrektur
1
Hinweise zu den Aufgaben
• Die Bearbeitungszeit beträgt 120 Minuten.
• Es sind keinerlei Hilfsmittel zugelassen, auch keine Taschenrechner.
• Versehen Sie dieses Angabenblatt auf der Titelseite mit Ihrem Namen, Vornamenund Matrikelnummer, sowie Geburtsdatum, Hörsaal und Platznummer. VergessenSie nicht die Unterschrift!
• Diese Angabe umfasst 29 bedruckte Seiten (inklusive Deckblatt).
• Außerdem erhalten Sie die folgenden Merkblätter:
Anlage I: „Die wichtigsten 80386 Befehle und ihre Operanden“
Anlage II: „Mikroprogrammierung“
Anlage III: „Die wichtigsten VHDL Konstrukte“
• Alle Lösungen sind in dieses Heft einzutragen. Sollte der vorgesehene Platz nichtausreichen, so finden Sie am Ende mehrere leere Seiten. Sollten auch diese nichtausreichen, wenden Sie sich bitte an die Aufsichten.
• Notizpapier wird auf Ihre Anfrage ausgegeben. Die Verwendung von eigenem Pa-pier ist nicht gestattet.
Lösungen auf Notizpapier werden nicht gewertet!
2
Aufgabe 1 - Maschinennahe Programmierung
Sämtliche Aufgaben sind mit den aus Vorlesung und Zentralübung bekannten 80386-Befehlen zu lösen. Seiteneffekte sind zu vermeiden, sofern nicht anders angege-ben. Beschränken Sie sich auf notwendige Register-Sicherungen.
1.1 Programmverständnis
1.1.1 Statusregister
Geben Sie den Wert des Übertrag- (carry), des Überlauf- (overflow), des Vorzeichen-(sign) und des Null-Indikators (zero flag) im Statusregister zu jedem Schritt diesersequentiell ausgeführten Befehlsfolge an (Möglichkeiten sind „gesetzt“/1 und „ge-löscht“/0):
Befehlsfolge Carry Overflow Sign Zero
1: - 0 0 1 0
2: mov eax,-1
3: xor eax,0xff0000ff
4: sub al,240
5: adc ah,al
6: neg ah
1.2 Einzeloperationen
1.2.1 Modulo
Führen Sie an einer vorzeichenlosen Zahl (in AL) eine Modulo-Berechnung (Divisorin BL ist eine Zweierpotenz) durch. Das Ergebnis soll in CL liegen. Vermeiden Sie dieVerwendung von (I)DIV oder (I)MUL.
3
1.2.2 Multiplikation
Multiplizieren Sie zwei vorzeichenlose Festkommazahlen im Format 8.8 in den Re-gistern AX und BX. Das Ergebnis entspricht seinerseits wieder dem 8.8-Format undsoll in AX liegen. Seiteneffekte auf EAX oder EBX dürfen ignoriert werden.
4
1.3 Programmentwicklung
„Türme von Hanoi“ ist ein Knobelspiel,bei welchem verschieden große, geloch-te Scheiben auf drei Spindeln so umge-schichtet werden sollen, dass der Stapelvon der linken Spindel auf die rechte ver-schoben wird. Pro Schritt wird immer nureine einzelne Scheibe bewegt, die dabeiniemals auf eine kleinere Scheibe gelegtwerden darf.
Das Ziel ist das Schreiben eines Assembler-Programmes, welches ein „Türme vonHanoi“-Spiel mit bis zu acht Scheiben rekursiv löst. Gehen Sie der Einfachheit halberdavon aus, dass alle Eingaben korrekt sind.
Speicheraufbau:
Eine Scheibe wird durch ein Nibble (4 Bit) kodiert. Dabei entspricht der Wert 0x1 derkleinsten Scheibe, 0x2 der nächstgrößeren usw.
Die drei Türme werden im Hauptspeicher jeweils als ein 32-Bit-Doppelwort abgelegtund sind im Assembler mittels der Marken tower_left, tower_middle und tower_right
addressierbar. Dabei wird die jeweils oberste Scheibe in den Bits 0-3, die zweitobers-te in den Bits 4-7, usw. gespeichert. 0x0 entspricht dabei keiner Scheibe.
Beispiel nach 19 Zügen:
tower_left
0x60x70x8
0x10x20x5
tower_middle
0x30x4
tower_right
Adresse Wert
[tower_left] 0x00000876
[tower_middle] 0x00000521
[tower_right] 0x00000043
1.3.1 Scheibe verschieben
Entwickeln Sie ein per CALL aufrufbares Unterprogramm move_disc, welches dieoberste Scheibe eines gegebenen Turmes A auf einen weiteren gegebenen TurmC verschiebt.
Eingaben:
• Die Speicheradresse von Turm A wird in Register EAX übergeben.
• Die Speicheradresse von Turm C wird in Register ECX übergeben.
5
1.3.2 Rekursive Lösung
Entwickeln Sie ein per CALL aufrufbares Unterprogramm hanoi, welches zur Lösungder Türme von Hanoi den Randoffschen Algorithmus verwendet:
function hanoi( Iterationen i, Turm A, Turm B, Turm C )if i > 0 then
hanoi( i− 1, A, C, B )verschiebe oberste Scheibe von Turm A nach Turm Chanoi( i− 1, B, A, C )
end ifend function
Das in der vorherigen Aufgabe beschriebene Unterprogramm move_disc darf als ge-geben angenommen werden.
Die Parameter-Übergabe findet über den Stapelspeicher statt. Der erste ParameterIhres Unterprogrammes (Anzahl der Iterationen i) liegt dabei oben, der letzte Para-meter (Adresse von Turm C) unten auf dem Stapel.
Aufrufbeispiel von extern:
push dword tower_right ; Adresse des rechten Turmes
push dword tower_middle ; Adresse des mittleren Turmes
push dword tower_left ; Adresse des linken Turmes
push dword 8 ; Anzahl an Iterationen/Scheiben
call hanoi ; Aufruf Ihres Unterprogrammes
Hinweis: Berücksichtigen Sie die implizite Stapelspeicherverwendung.
7
Aufgabe 2 - Mikroprogrammierung
Sie haben ein Merkblatt mit einer Kurzbeschreibung der mikroprogrammierbaren Ma-schine erhalten, in welchem Sie alle zur Lösung der Aufgabe notwendigen Angabenfinden, z. B. die Beschreibung des Mikroinstruktionsformats und die Funktionstabel-len der Bausteine.
Das Mikroprogramm IFETCH, abgelegt ab Adresse 0x000 des Mikroprogrammspei-chers, kann als gegeben betrachtet werden. Es holt den nächsten Maschinenbefehlaus dem Hauptspeicher in das Instruktionsregister, inkrementiert den Befehlszäh-ler und springt das dem Befehls-Opcode zugehörige Mikroprogramm an. IFETCHbenötigt 3 Takte zur Ausführung. Mikroprogramme müssen am Ende wieder zum An-fang des Mikroprogramms IFETCH zurückspringen. Hexadezimale Zahlen werden inJava- bzw. C-Schreibweise dargestellt und beginnen mit der Buchstabenkombination0x, z.B: 0x1234, 0x011A oder 0xBEEF.
Im Folgenden werden Maschinenbefehle für schnelle Bereichsüberprüfungen einge-führt. Für einen Bereich, spezifiziert über zwei vorzeichenlose Randwerte (inklusiv),sollen intern die Register r8 und r9 benutzt werden, die nur für Mikroprogramme sicht-bar sind. Dabei wird in r8 der niedrigste mögliche Wert und r9 der höchste möglicheWert abgelegt. Ein leerer Bereich (kein Wert erfüllt dann eine Bereichsabfrage) istdadurch gegeben, dass der Inhalt von r8 größer als der Inhalt von r9 ist.
Gegeben sind die Maschinenbefehle in der folgenden Tabelle. Die Bezeichnung „RA“(bzw. „RB“) steht hier abkürzend für „das durch das A-Registeradressfeld (bzw. B-Registeradressfeld) des Maschinenbefehlswortes adressierte Register“.
10
Opc. Befehl Beschreibung0x03 MOV [RA],RB Kopiert den Inhalt der Speicherstelle, deren Adresse in
Register RA steht, in das Register RB.0x11 CMP RA, imm Führt eine Subtraktion des Inhalts von Register RA minus
imm durch. Die Flags des Maschinenstatusregisters wer-den entsprechend des Ergebnisses gesetzt. Das Ergebniswird verworfen.
0x21 INC RB Inkrementiert RB um 1 (RB = RB + 1). Die Flags des Ma-schinenstatusregisters werden entsprechend des Ergeb-nisses gesetzt.
0x22 DEC RB Vermindert RB um 1 (RB = RB - 1). Die Flags des Ma-schinenstatusregisters werden entsprechend des Ergeb-nisses gesetzt.
0x30 JMP adr Führt einen Sprung an die Adresse adr aus.0x31 JNZ adr Führt einen Sprung an die Adresse adr aus, wenn das
Zero-Flag des Maschinenstatusregisters nicht gesetzt ist.0x32 JNC adr Führt einen Sprung an die Adresse adr aus, wenn das
Carry-Flag des Maschinenstatusregisters nicht gesetzt ist.0x35 JLT adr Führt einen Sprung an die Adresse adr aus, wenn der
erste Operand eines vorausgehenden CMP-Befehls kleinerals („lower than“) dessen zweiter Operand ist. Dabei wirdvon vorzeichenlosen Operanden ausgegangen.
0x36 JGT adr Führt einen Sprung an die Adresse adr aus, wenn der ers-te Operand eines vorausgehenden CMP-Befehls größer als(„greater than“) dessen zweiter Operand ist. Dabei wirdvon vorzeichenlosen Operanden ausgegangen.
0x40 CLRC Löscht das Carry-Flag im Maschinenstatusregister. DerWert der anderen Flags ist nach Ausführung des Befehlsundefiniert.
0x41 SETC Setzt das Carry-Flag im Maschinenstatusregister. DerWert der anderen Flags ist nach Ausführung des Befehlsundefiniert.
0x71 LRNG imm1,imm2
Lädt den Bereich (RNG = “Range”), der im Maschinenbe-fehl CRNG verwendet wird, auf die Randwerte imm1 (nied-rigster Wert, inklusiv) und imm2 (höchster Wert, inklusiv).Eine Angabe von imm1 > imm2 bedeutet leerer Bereich.
0x75 CRNG [RA] Führt eine Bereichsüberprüfung durch für den Inhalt derSpeicherzelle, deren Adresse in Register RA steht. Dabeiwerden die in einem vorherigen Maschinenbefehl LRNG an-gegebenen Randwerte benutzt. Ist der Wert im Bereich,wird das Carry-Flag des Maschinenstatusregisters ge-setzt, anderenfalls gelöscht. Der Wert der anderen Flagsist nach Ausführung des Befehls undefiniert.
2.1 Welche der auf der vorherigen Seite angegebenen Befehle belegen 16, 32, bzw.48 Bit im Hauptspeicher? Bitte geben Sie die jeweiligen Opcodes an.
a) 16 Bit
b) 32 Bit
b) 48 Bit
2.2 Gegeben ist folgendes Maschinenprogramm.
weiter : MOV [r0], r2CMP r2, 0x100JLT aussenCMP r2, 0x200JGT aussenINC r0DEC r1JNZ weiterSETC
JMP fertigaussen: CLRC
fertig: ...
12
2.2.1 Die Inhalte ab Speicherstelle 0x0400 seien mit 0x100, 0x200, 0x300, 0x400vorbelegt, und die Register r0 = 0x400, r1 = 4. Welche Inhalte stehen nach Ablauf inden Registern r0 und r1, und ist das Carry-Flag gesetzt oder gelöscht?
r0 / r1 / Carry:
2.2.2 Wie viele Speicherzugriffe führt das gegebene Maschinenprogramm durch,wenn alle Befehle vom Start bis zu JMP fertig genau einmal ausgeführt werden? Neh-men Sie dabei an, dass die Implementierungen der bedingten Sprungbefehle immerdie Sprungadresse aus dem Speicher lesen. Hinweis: Berücksichtigen Sie IFETCH.
2.2.3 Beschreiben Sie die Aufgabe des Programms.
2.2.4 Geben Sie ein semantisch identisches Programm an, das anstatt der Maschi-nenbefehle CMP, JLT und JGT die Befehle LRNG imm1,imm2 und CRNG [RA] sowie JNC
benutzt.
13
2.2.5 Zeigen Sie, wie der Anfang des Maschinenprogramms in hexadezimaler Co-dierung aussieht.
Adresse Inhalt Befehl
0x0100 weiter : MOV [r0], r2
CMP r2, 0x100
JLT aussen
CMP r2, 0x200
JGT aussen
INC r0
DEC r1
JNZ weiter
aussen: SETC
...
14
2.3 Folgende Maschinenbefehle sollen nun durch ein Mikroprogramm realisiert wer-den:
• CLRC
• LRNG imm1, imm2
• CRNG [RA]
Hinweis: Die Implementierung von CRNG soll, wie im vorausgehenden Maschinen-programm, zunächst auf Einhaltung der Untergrenze (in Register r8) und daraufhinauf Einhaltung der Obergrenze (in Register r9) prüfen.
2.3.1 Die Implementierung von LRNG imm1, imm2 kann aus zwei einfachen Daten-transfers bestehen. Begründen Sie, warum dies auch für den Fall der Angabe einesleeren Bereichs korrekt ist!
2.3.2 Vervollständigen Sie die Tabellen auf den Seiten 17/18.
Bitte tragen Sie keine binären Werte ein, sondern verwenden Sie die Abkürzungenaus dem Merkblatt MI (in der Anlage).Die Tabelle ist doppelt abgedruckt für einen zweiten Lösungsversuch.Streichen Sie Lösungen, die nicht bewertet werden sollen, deutlich durch.
15
79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39
IE
I3
I2
I1
I0
KM
UX
K15
K14
K13
K12
K11
K10
K9
K8
K7
K6
K5
K4
K3
K2
K1
K0
I2
I1
I0
I5
I4
I3
I8
I7
I6
A3
A2
A1
A0
AS
EL
B3
B2
B1
B0
BS
EL
Adr.
DIS
DIS
DIS
DIS
DIS
DIS
DIS
DIS
DIS
DIS
Adr.
DIS
DIS
DIS
DIS
DIS
DIS
DIS
DIS
DIS
DIS
CRNG [RA]
X X
X X
CRNG [RA]X X
X X
X X
X X
X X
Dest RA Addr RB AddrInterrupt Konstante Src Func
X
X X
X X
LRNG imm1, imm2X
CLRC
X X
X
CLRCX
LRNG imm1, imm2
X X
X X
X X
X X
X X
X X
X X
17
38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
AB
US
*
DB
US
*
I12
I11
I9
I8
I7
I6
CE
MU
E*
CE
M*
I5
I4
I3
I2
I1
I0
CC
EN
*
I3
I2
I1
I0
D11
D10
D9
D8
D7
D6
D5
D4
D3
D2
D1
D0
BZ
_L
D*
BZ
_E
D*
BZ
_IN
C*
BZ
_E
A*
IR
_L
D*
MW
E*
H H H H H R
H H X
H H X
H H X
H H
H H X H H H H H R
H H X H H H H H R
H H H H H R
H H H H H R
H H H H H R
H H H H H R
H H X
H H X
H H X
H H
H H X H H H H H R
H H X H H H H H R
H H H H H R
H H H H H R
H H H H H R
X
X X
CONT X
X X CONT X
X X
X
XX X CONT
X X CONT X
XX X CONT
X X CONT
X
X
Befehle
Y- CIN Schiebe- Statusregister AM2910
X
DirektdatenMUX MUX steuerung Test
X
X
X
X
X X CONT X
X X CONT X
X X CONT X
X X CONT X
X
X
18
Aufgabe 3 - Rechnergestützter Schaltungsentwurf
3.1 Teilbarkeit
Im Folgenden soll ein Schaltkreis entwickelt werden, der den 4 Bit Eingang A aufTeilbarkeit durch fünf überprüft.
Dies ist wie folgt formal definiert:
x =
{1 für A mod 5 = 0
0 für A mod 5 ̸= 0
Dabei ist A = (a3, a2, a1, a0) der Eingang und x der Ausgang der Schaltung.
3.1.1 Ergänzen Sie die Wertetabelle der Schaltung.
Hinweis: Tragen Sie nur die Einser in die Wertetabelle ein.
a3 a2 a1 a0 x
0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 1
a3 a2 a1 a0 x
1 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1
3.1.2 Welche der beiden bekannten Normalformen für boolsche Ausdrücke ist fürdie Beschreibung von x besser geeignet? Begründen sie kurz!
3.1.3 Erstellen Sie die in der vorherigen Aufgabe gewählte Normalform für x.
19
3.1.4 Erstellen Sie eine VHDL-Architecture, die die Ausgänge entsprechend derWertetabelle berechnet.
Der Eingang ist A, der Ausgang ist x. Alle Ein- und Ausgänge sind entweder alsstd_logic_vector oder std_logic definiert.
3.1.5 Entwerfen Sie ein Schaltnetz, das x aus A berechnet.
Streichen Sie Lösungen, die nicht bewertet werden sollen, deutlich durch.
a0
a1
a2
a3
x
a0
a1
a2
a3
x
3.1.6 Wie viele binäre Gatter werden mindestens zur Lösung der vorigen Aufgabebenötigt? Begründen Sie kurz!
20
3.2 Bitstrom-Zähler
Der Bitstrom-Zähler bitcount ist ein Bauteil, das vier Eingänge CLK, SYN, DAT und CMP
sowie die zwei Ausgänge CNT und MAT besitzt.
Alle Eingänge werden ausschließlich zur steigenden Flanke von CLK evaluiert.
Das Bauteil zählt die Anzahl der Bits in einem Bitstrom DAT, die mit dem 16 Bit langenSuchmuster CMP übereinstimmen. Dabei wird mit dem höchstwertigsten Bit begonnen.
SYN wirkt ähnlich wie ein synchroner Reset: Falls SYN = 1, wird der interne Zustandzurück gesetzt.
Das Flag MAT gibt aus, ob der Bitstrom seit dem letzten SYN=1 gleich dem Suchmusterist. Sobald es eine Abweichung gibt, wird es bis zum nächsten SYN auf 0 gesetzt.
Der Zähler CNT gibt aus, wie viele Zeichen mit dem Suchmuster übereinstimmen oderbis zur Abweichung übereingestimmt haben.
CLK
SYN
DAT
CMP 1010 1011 0111 1000
MAT
CNT 1
Auf Seite 25 sind zwei identische Impulsdiagramme für weitere Versuche abgebildet.Streichen Sie Lösungen, die nicht bewertet werden sollen, deutlich durch.
3.2.1 Zeichnen Sie die Zeitpunkte, an denen der interne Zustand zurück gesetzt,wird als vertikale Linien im Impulsdiagramm ein.
3.2.2 Vervollständigen Sie das Impulsdiagramm.
1. Zeichnen Sie die Werte, die der Ausgang MAT annimmt, als Signalverlauf ein.
2. Tragen Sie die Werte, die der Ausgang CNT annimmt, als Zahl ein.
21
3.2.3 Erstellen Sie die VHDL-Entity des Bausteins bitcount. Halten Sie sich an dievorgegebenen Signalnamen.
Der Wertebereich des Zählers CNT soll mindestens 0 bis 16 umfassen, ohne dabeiSpeicherplatz zu verschwenden.
3.2.4 Realisieren Sie ein Schieberegister wie in der Abbildung in VHDL.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
input
output
22
3.2.5 Erstellen Sie die VHDL-Architecture des Bausteins bitcount.
• Achten Sie dabei auf das Verhalten von Prozessen beim Verändern von Werten.
• Verwenden Sie das Schieberegister an einer geeigneten Stelle im Code. FallsSie die vorige Aufgabe nicht lösen konnten, schreiben Sie verschieben(output,
input) an die gewünschte Stelle.
• Es kann davon ausgegangen werden, dass der Zähler niemals überlauft.
23
Weitere Vorlagen für das Impulsdiagramm
CLK
SYN
DAT
CMP 1010 1011 0111 1000
MAT
CNT 1
Streichen Sie Lösungen, die nicht bewertet werden sollen, deutlich durch.
CLK
SYN
DAT
CMP 1010 1011 0111 1000
MAT
CNT 1
Streichen Sie Lösungen, die nicht bewertet werden sollen, deutlich durch.
25
Zusätzlicher Platz für Lösungen - Bitte immer Aufgabennummer angeben und am Ursprung einen
Verweis mit Seitenangabe einfügen!
Lösung für Aufgabe . . .
26