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

6

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

8

9

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

24

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

Lösung für Aufgabe . . .

27

Lösung für Aufgabe . . .

28

Lösung für Aufgabe . . .

29