Klausur zur Vorlesung
Grundlagen der Rechnerarchitektur / Technische Informatik (GRA/TI)
Prof. Marco Platzner Fachgebiet Technische Informatik Universita ̈t Paderborn
22.09.2015
• Die Bearbeitungsdauer betra ̈gt fu ̈r alle Studenten 90 Minuten. Es sind alle 5 Aufgaben zu bearbeiten.
• Es sind keine Hilfsmittel zugelassen.
• Schreiben Sie nicht mit Bleistift oder Rotstift.
• Verwenden Sie kein eigenes Papier. Bei Bedarf bekommen Sie Papier bei der Klau- suraufsicht.
• Schreiben Sie auf jedes Blatt (auch auf das Konzeptpapier) in Blockschrift Ihren Namen und Ihre Matrikelnummer.
• Bei mehreren pra ̈sentierten Lo ̈sungen wird die Aufgabe nicht gewertet! Streichen Sie daher bei Angabe mehrerer Lo ̈sungsansa ̈tze die nicht zu bewertenden Lo ̈sungen durch! Verwenden Sie kein Tipp-Ex.
• Abschreiben und abschreiben lassen oder Hilfe Dritter fu ̈hrt zum Nichtbestehen der Klausur.
Nachname: Vorname: Matrikelnummer: Studiengang:
Aufkleber
Aufgabe
1
2
3
4
5
Punkte
15
20
25
15
15
90
Erreicht
1
GRA/TI Aufgabe 1 (Multiple Choice) [15 Punkte]
Bei den folgenden Fragen ko ̈nnen keine, eine oder mehrere Antworten richtig sein. Kreuzen Sie die richtigen Antworten deutlich an.
(a) Mo ̈glichkeiten zur Reduktion von Data Hazards sind … feste Instruktionsla ̈ngen
Forwarding
Umordnen der Instruktionen dynamische Sprungvorhersage
(b) In welchen Fa ̈llen ist der Branch Prediction Buffer (BPB) 2 KBit groß?
10 LSB der Adresse fu ̈r BPB-Indizierung verwendet, 2-bit Pra ̈diktor 11 LSB der Adresse fu ̈r BPB-Indizierung verwendet, 1-bit Pra ̈diktor
8 LSB der Adresse fu ̈r BPB-Indizierung verwendet, (2,2) korrelierender Pra ̈diktor
6 LSB der Adresse fu ̈r BPB-Indizierung verwendet, (4,1) korrelierender Pra ̈diktor
(c) Welche Maßnahmen reduzieren die Miss-rate eines Caches? ho ̈herer Grad der Assoziativita ̈t
breitere Speicherorganisation gro ̈ßerer Cache
Prefetching
Seite 2 / 19
NAME: Matrikelnummer:
(d) Was ist Predication?
Sprungvorhersage zur Auflo ̈sung von Control Hazards
die bedingte Ausfu ̈hrung von Instruktionen, abha ̈ngig von dem Wert eines Booleschen Registers
eine Technik zur Eliminierung von bedingten Spru ̈ngen
eine Strategie zur Ersetzung von Cacheblo ̈cken
(e) Auf einem Prozessor mit einer Taktfrequenz von 1 GHz werden 106 Instruktionen in 0,5 ms abgearbeitet. Um welche Prozessorarchitektur ko ̈nnte es sich handeln?
superskalarer Prozessor VLIW Prozessor Einzyklenimplementierung Mehrzyklenimplementierung
Seite 3 / 19
GRA/TI Aufgabe 2 (Instruktionssatzarchitekturen) [20 Punkte]
(a) Es sollen die drei Instruktionssatzarchitekturen Stack-, Akkumulator- und Load- Store-Architektur hinsichtlich des Speicherbedarfs und der Speicherbandbreite un- tersucht werden. Erstellen Sie dazu fu ̈r die Anweisung
D = A * B + (A – C * B)
fu ̈r jede der drei Architekturen eine Assemblercodesequenz. Bestimmen Sie den Speicherbedarf der Instruktionen und die Menge der u ̈bertragenen Daten in By- tes. Geben Sie fu ̈r die Stack- und Akkumulator-Architektur außerdem die Belegung des Stacks (Abb. 1) und des Akkumulators (Abb. 3) an.
Die Operanden A, B und C sind 32 bit groß und liegen im Speicher. Das Ergebnis D, ebenfalls 32 bit groß, muss nach Berechnung in den Speicher abgelegt werden. Nehmen Sie an, dass der opcode einer Instruktion 1 Byte betra ̈gt, die Speicheradres- sen 16 bit und die Registeradressen 4 bit lang sind. Die Instruktionsla ̈nge muss ein Vielfaches von einem Byte sein.
(i) Stack-Architektur. Verfu ̈gbare Instruktionen: push, pop, add, sub, mul
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Tabelle 1: Programm in Stack-Architektur
Nach Nach Nach Nach Nach Nach Nach Nach Nach Nach Instruktion 1 Instruktion 2 Instruktion 3 Instruktion 4 Instruktion 5 Instruktion 6 Instruktion 7 Instruktion 8 Instruktion 9 Instruktion 10
Abbildung 1: Belegung des Stacks
Seite 4 / 19
NAME: Matrikelnummer:
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Tabelle 2: Programm in Stack-Architektur – Ersatzlo ̈sung, ungu ̈ltige Lo ̈sung strei- chen!
Nach Nach Nach Nach Nach Nach Nach Nach Nach Nach Instruktion 1 Instruktion 2 Instruktion 3 Instruktion 4 Instruktion 5 Instruktion 6 Instruktion 7 Instruktion 8 Instruktion 9 Instruktion 10
Abbildung 2: Belegung des Stacks – Ersatzlo ̈sung, ungu ̈ltige Lo ̈sung streichen!
Seite 5 / 19
GRA/TI (ii) Akkumulator-Architektur.Verfu ̈gbareInstruktionen:load,store,add,sub,
mul
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Tabelle 3: Programm in Akkumulator-Architektur
Nach Nach Nach Nach Nach Nach Nach Nach Nach Nach Instruktion 1 Instruktion 2 Instruktion 3 Instruktion 4 Instruktion 5 Instruktion 6 Instruktion 7 Instruktion 8 Instruktion 9 Instruktion 10
Abbildung 3: Belegung des Akkumulators
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Tabelle 4: Programm in Akkumulator-Architektur – Ersatzlo ̈sung, ungu ̈ltige Lo ̈sung streichen!
Nach Nach Nach Nach Nach Nach Nach Nach Nach Nach Instruktion 1 Instruktion 2 Instruktion 3 Instruktion 4 Instruktion 5 Instruktion 6 Instruktion 7 Instruktion 8 Instruktion 9 Instruktion 10
Abbildung 4: Belegung des Akkumulators – Ersatzlo ̈sung, ungu ̈ltige Lo ̈sung strei- chen!
Seite 6 / 19
NAME: Matrikelnummer:
(iii) Load-Store-Architektur. Verfu ̈gbare Instruktionen: lw, sw, add, sub, mul. Nehmen Sie an, dass sie beliebig viele Register zur Verfu ̈gung haben. Verwenden Sie die aus der Vorlesung bekannte MIPS Syntax, aber die in dieser Aufgabe definierte Instruktionskodierung.
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Tabelle 5: Programm in Load-Store-Architektur
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Tabelle 6: Programm in Load-Store-Architektur – Ersatzlo ̈sung, ungu ̈ltige Lo ̈sung streichen!
(b) Nennen Sie jeweils einen Vorteil von fester und variabler Instruktionsla ̈nge und erla ̈utern Sie ihn kurz.
Seite 7 / 19
GRA/TI Aufgabe 3 (Prozessorentwurf) [25 Punkte]
In dieser Aufgabe wird die in der Vorlesung besprochene Mehrzyklenimplementierung eines MIPS-Prozessors betrachtet. Sie soll um einen Befehl addm erweitert werden:
addm $s0, imm($s1) # $s0 = $s0 + mem[imm + $s1]
(a) Bestimmen Sie einen geeigneten Instruktionstypen fu ̈r addm. Tragen Sie in die unten stehende Abbildung die entsprechende Instruktionskodierung ein. Kennzeichnen Sie in der Abbildung anhand des obigen Beispiels mit welchen Werten die Instrukti- onsfelder belegt werden. Nicht beno ̈tigte Instruktionsbits ko ̈nnen mit X (don’t care) gekennzeichnet werden.
Instruktionstyp:
31 2625
31 2625
Ersatz, ungu ̈ltige Lo ̈sung streichen!
0
0
Opcode
Opcode
(b) Geben Sie eine Befehlsfolge mit den in der Vorlesung besprochenen Assemblerbe- fehlen an, um addm alternativ abbilden zu ko ̈nnen. Wie viele Taktzyklen beno ̈tigt diese Befehlsfolge?
Anzahl Taktzyklen:
Seite 8 / 19
NAME: Matrikelnummer:
(c) Geben Sie einen Ablauf des addm-Befehls mit Hilfe der in der Vorlesung besproche- nen Pseudocode-Notation fu ̈r die verschiedenen Phasen, die addm durchla ̈uft, an. Wie viele Taktzyklen beno ̈tigt addm?
IF: IR <= Memory[PC];
PC <= PC + 4;
ID: A <= Reg[IR[25:21]];
B <= Reg[IR[20:16]];
ALUOut <= PC + (sign-extend(IR[15:0]) << 2);
Anzahl Taktzyklen:
Seite 9 / 19
GRA/TI
(d) Erweitern Sie den Datenpfad und die Steuersignale der Mehrzyklenimplementierung, um addm ausfu ̈hren zu ko ̈nnen.
Seite 10 / 19
NAME: Matrikelnummer:
Ersatz, ungu ̈ltige Lo ̈sung streichen!
Seite 11 / 19
GRA/TI
(e) Vervollsta ̈ndigen Sie den Automaten der Steuereinheit fu ̈r den addm-Befehl. Instruction fetch
MemRead=1 ALUSrcA = 0 IorD = 0 IRWrite = 1 ALUSrcB = 1 ALUOp = "ADD" PCWrite = 1 PCSource = 0
Instruction decode / Register fetch
ALUSrcA = 0
ALUSrcB = 3 ALUOp = "ADD"
Seite 12 / 19
NAME:
Matrikelnummer:
Ersatzautomat, ungu ̈ltige Lo ̈sung streichen!
Instruction fetch
MemRead=1 ALUSrcA = 0 IorD = 0 IRWrite = 1 ALUSrcB = 1 ALUOp = "ADD" PCWrite = 1 PCSource = 0
Instruction decode / Register fetch
ALUSrcA = 0
ALUSrcB = 3 ALUOp = "ADD"
Seite 13 / 19
GRA/TI
(f) Nun soll die relative Performance zwischen einer klassischen Implementierung ohne Erweiterung und der Implementierung mit addm bestimmt werden, wobei beide Ar- chitekturen mit der gleichen Taktfrequenz betrieben werden. Dazu sei ein passendes Benchmark-Programm gegeben.
Mehrzyklenimplementierung A ohne Erweiterung: Das Programm hat 10.000 In- struktionen.
Instruktion
Ha ̈ufigkeit
Anzahl Takte
add
20%
Sonstige R-Typ
20%
lw
30%
sw
20%
Branch (j und beq)
10%
Mehrzyklenimplementierung B mit addm: Das Programm hat 9.000 Instruktionen.
Instruktion
Ha ̈ufigkeit
Anzahl Takte
add
15%
addm
10%
Sonstige R-Typ
20%
lw
25%
sw
20%
Branch (j und beq)
10%
Geben Sie die relative Performance zwischen den Implementierungen A und B an.
Seite 14 / 19
NAME: Matrikelnummer:
Aufgabe 4 (Branch Delay Slots)
[15 Punkte]
Gegeben sei eine Architektur mit einem Delay Branch Slot. Formen Sie die drei Assemb- lerprogramme so um, dass der Delay Slot stets ausgenutzt wird.
(a)
01: add $3, $2, $1
02: add $6, $1, $4
03: add $2, $5, $3
04: add $5, $4, $3
05: beq $5, $zero, L1
06: nop
...
99: L1: ...
01:______________________________________
02:______________________________________
03:______________________________________
04:______________________________________
05:______________________________________
06:______________________________________
______________________________________
______________________________________
Ersatzlo ̈sung, ungu ̈ltige Lo ̈sung streichen!
01: add $3, $2, $1
02: add $6, $1, $4
03: add $2, $5, $3
04: add $5, $4, $3
05: beq $5, $zero, L1
06: nop
...
99: L1: ...
(b)
01: lw
02: L1: add $1, $1, $1
03: blt $1, $2, L1
04: nop
01:______________________________________
02:______________________________________
03:______________________________________
04:______________________________________
05:______________________________________
06:______________________________________
______________________________________
______________________________________
01:______________________________________
02:______________________________________
03:______________________________________
04:______________________________________
05:______________________________________
06:______________________________________
01: lw $1, 0($a0)
02: L1: add $1, $1, $1
03: blt $1, $2, L1
04: nop
01:______________________________________
02:______________________________________
03:______________________________________
04:______________________________________
05:______________________________________
06:______________________________________
$1, 0($a0)
Ersatzlo ̈sung, ungu ̈ltige Lo ̈sung streichen!
Seite 15 / 19
(c)
01: add $1, $2, $3
02: beq $1, $5, L1
03: nop
04: add $1, $3, $4
05: add $2, $7, $8
06: L1: sll $1, $1, 1
GRA/TI
01:______________________________________
02:______________________________________
03:______________________________________
04:______________________________________
06:______________________________________
05:______________________________________
______________________________________
______________________________________
Ersatzlo ̈sung, ungu ̈ltige Lo ̈sung streichen!
01: add $1, $2, $3
02: beq $1, $5, L1
03: nop
04: add $1, $3, $4
05: add $2, $7, $8
06: L1: sll $1, $1, 1
01:______________________________________
02:______________________________________
03:______________________________________
04:______________________________________
06:______________________________________
05:______________________________________
______________________________________
______________________________________
(c) Welche Einschra ̈nkungen gibt es bei (b) und (c) bezu ̈glich der Verwendung von Regi- stern nach den Codesequenzen?
Seite 16 / 19
NAME: Matrikelnummer:
Aufgabe 5 (Vergleich von Caches)
[15 Punkte]
Fu ̈r diese Aufgabe sei ein 32-bit Prozessor mit einem (byte-adressierten) Adressraum von 1 GB (= 230 Bit) und einem 25 KB großen Cache gegeben, fu ̈r den Sie verschiedene Ver- sionen mit folgenden Charakteristika untersuchen sollen:
(a) Der Cache C1 hat einen Overhead von 36%, wobei dieser wie folgt definiert ist: Overhead = 1 − Nutzdaten
Gesamtgro ̈sse
Wie vera ̈ndert sich der Overhead wenn man stattdessen Variante C2 einsetzt und das System ansonsten unvera ̈ndert la ̈sst?
Hinweis: Wenn Sie diese Aufgabe durch Nachdenken statt Rechnen bearbeiten, za ̈hlt die Lo ̈sung nur mit Begru ̈ndung!
Cache
Assoziativit ̈at
Blockgro ̈ße
C1
4-fach satzassoziativ
1 Wort
C2
5-fach satzassoziativ
1 Wort
C3
4-fach satzassoziativ
16 Worte
C4
8-fach satzassoziativ
16 Worte
Seite 17 / 19
GRA/TI (b) Berechnen Sie die Gro ̈ße der Nutzdaten und die Gesamtgro ̈ße von Variante C3.
Schreiben Sie die Formel fu ̈r den Overhead mit diesen Daten hin. Hinweis: Sie mu ̈ssen den Overhead nicht ausrechnen!
(c) Was sind Vor- und Nachteile von Version C3 gegenu ̈ber C1, und von C4 gegenu ̈ber C3?
Seite 18 / 19
NAME: Matrikelnummer:
Konzeptpapier: Falls der Platz unter den einzelnen Aufgaben nicht ausreicht, ko ̈nnen Sie diese Seiten fu ̈r Zwischenrechnungen nutzen. Bitte Lo ̈sung und Lo ̈sungsweg eindeutig mit der Aufgabennummer markieren!
Seite 19 / 19