Klausur zur Vorlesung
Grundlagen der Rechnerarchitektur / Technische Informatik (GRA/TI)
Prof. Marco Platzner Fachgebiet Technische Informatik Universita ̈t Paderborn
27.02.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
15
20
20
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) Was berechnet folgendes Assemblerprogramm:
# x in $t0, y in $t1
xor $t1, $t0, $t1
xor $t0, $t1, $t0
xor $t1, $t1, $t0
x in $t0, y in $t1
x in $t0, x in $t1
0 in $t0, 0 in $t1
y in $t0, x in $t1
(b) Was sind Charakteristika einer RISC Instruktionssatzarchitektur? feste Instruktionsla ̈nge
viele, komplexe Instruktionsarten load/store Architektur Register/Speicher Operationen
(c) Welche Aussagen sind fu ̈r einen Write-Back Cache korrekt? Cache und Hauptspeicher sind immer konsistent.
Jeder Cacheblock beno ̈tigt ein Dirty-Bit.
Write-Back funktioniert bei Caches mit beliebigem Assoziativita ̈tsgrad.
Seite 2 / 14
NAME: Matrikelnummer:
(d) Wie gross ist die durchschnittliche Rotationslatenz bei einer Festplatte mit 15000 Umdrehungen pro Minute?
0.5 ms 1 ms 2 ms 3 ms
(e) Welche Gemeinsamkeiten haben Superskalar- und VLIW-Prozessoren? Beide sind Prozessoren mit Mehrfachzuordnung.
Bei beiden fu ̈hrt der Compiler die Zurodnung von Instruktionen zu Ausfu ̈hrungseinheiten durch.
Beide haben einen idealen CPI-Wert von kleiner eins. Beide ko ̈nnen von Instruktions-Caches profitieren.
Seite 3 / 14
GRA/TI Aufgabe 2 (Assembler und Leistungsbewertung) [20 Punkte]
a) In die MIPS-Assembler-Implementierung der Ackermannfunktion a(n,m) haben sich einige Fehler eingeschlichen. Identifizieren und markieren Sie die Fehler und geben Sie korrekte Versionen der entsprechenden Codezeilen in den zugeho ̈rigen Kommentarfeldern an. Das Korrigieren richtigen Codes fu ̈hrt zu Punktabzug. Die Ackermannfunktion:
a(0,m) = m+1 a(n+1,0) = a(n,1)
a(n+1,m+1) = a(n,a(n+1,m))
Die Parameter n und m werden in den Registern $a0 und $a1 u ̈bergeben. Das Resultat
befindet sich im Register $v0.
1 ackermann:
2 sw $ra, -4($sp)
3 sw $a1, -8($sp)
4 sw $a0, -12($sp)
5 subi $sp, $sp,
6 slt $t0, $zero,
7 beq $t0, $zero,
8 addi $v0, $a1,
9 jal return
12
$a0
NNichtNull
1
$a0
MNichtNull
-1
1
-1
$zero -1
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
10
11 NNichtNull:
12 slt $t0, $zero,
13 bne $t0, $zero,
14 addi $a0, $a0,
15 addi $a1, $zero,
16 j ackermann
17 jal return
18
19 MNichtNull:
20 addi $a1, $a1,
21 jal ackermann
22 xor $a1, $v0,
23 addi $a0, $a0,
24 j ackermann
25
26 return:
27 subi $sp,
28 lw $ra,
29 lw $a1,
30 lw $a0,
31 jr $ra
$sp, -12
-4($sp)
-8($sp)
-12($sp)
Seite 4 / 14
NAME: Matrikelnummer:
b) Die Funktion ackermann wird mit den Parametern n = 1 und m = 0 ausgefu ̈hrt. Welches Ergebnis wird berechnet?
Notieren Sie die Werte der Register $a0, $a1 und $sp bei jedem Aufruf der Ackermann- funktion und zwar nach dem Abarbeiten der fu ̈nften Zeile. Der Stackpointer wird mit 0x100 vor dem ersten Aufruf der Ackermannfunktion initialisiert.
Ersatztabelle
c) Gegeben sei ein 2 GHz schneller Prozessor in Mehrzyklenimplementierung. Berechnen Sie die Ausfu ̈hrungszeit der Ackermannfunktion fu ̈r n = 1 und m = 0, indem Sie fu ̈r jeden Aufruf der Ackermannfunktion die Anzahl der Instruktionen einer bestimmten In- struktionsklasse in der unten gegebenen Tabelle notieren und dann die Gesamtzahl der Zyklen pro Instruktionsklasse sowie u ̈ber alle Instruktionsklassen bilden. Bestimmen Sie dann den durchschnittlichen CPI Wert.
$sp
$a0
$a1
$sp
$a0
$a1
Instruktionsklassei
ack(1,0)
ack( , )
CPIi
Zyklen
R-typ
4
load word
store word
5
4
branch
3
jump / return
2
Ersatztabelle
CPI=__________________
Gesamtanzahl Zyklen:
Gesamtanzahl Zyklen:
Instruktionsklassei
ack(1,0)
ack( , )
CPIi
Zyklen
R-typ
4
load word
store word
5
4
branch
3
jump / return
2
Seite 5 / 14
GRA/TI
Aufgabe 3 (Leistungsbewertung) [15 Punkte]
Ein Prozessor mit einer wie in der Vorlesung besprochenen Mehrzyklenimplementierung soll nur eine begrenzte Auswahl von Programmen ausfu ̈hren. Von daher ist man in der Lage, einen typischen Instruktionsmix anzugeben:
Der Prozessor habe eine Taktfrequenz von 500 MHz.
(a) Berechnen Sie den Speedup fu ̈r den Fall, dass die Arithmetik-Instruktionen doppelt so schnell ausgefu ̈hrt werden ko ̈nnen.
Instruktion
Ha ̈ufigkeit
CPI-Wert
Arithmetik
70%
4
Load
10%
5
Store
15%
4
Jump / Branch
5%
3
(b) Anstatt die Arithmetik-Instruktionen zu beschleunigen, wird nun u ̈berlegt, den Pro- zessor mit einer Pipeline auszustatten, um den Instruktionsdurchsatz zu erho ̈hen. Fu ̈r den gegebenen Instruktionsmix stellt man dabei fest, dass 60% der Load- Instruktionen zu einem Datenkonflikt fu ̈hren, welche zu einem Pipeline-Stall von jeweils 2 Taktzyklen fu ̈hren. Außerdem fu ̈hren die Jump-Instruktionen zu einem Pipeline-Stall von jeweils 1 weiteren Taktzyklus. 20% der Arithmetik-Instruktionen stehen ebenfalls im Konflikt. Wie viele Pipeline-Stall-Zyklen darf im Schnitt ein Konflikt bei den Arithmetik-Instruktionen maximal haben, damit ein Speedup von mindestens 3 gegenu ̈ber der urspru ̈nglichen Implementierung ohne Verbesserungen erreicht wird?
Seite 6 / 14
NAME: Matrikelnummer:
(c) Als eine weitere Optimierungsmo ̈glichkeit kann man getrennte Caches fu ̈r Daten und Instruktionen einfu ̈hren, um die Zugriffszeit auf den Hauptspeicher zu optimieren. Die Caches unterscheiden sich dabei nur in ihrer Miss-Rate. Durch die Caches kann die Taktperiodendauer des Prozessors auf 0, 4 ns gesenkt werden, so dass bei einem Cache-Hit nur ein Taktzyklus beno ̈tigt wird. Ein Cache-Miss fu ̈hrt nun allerdings dazu, dass der Prozessor 4 weitere Taktzyklen warten muss, um das Ergebnis aus dem Hauptspeicher bereit zu stellen. Der Instruktions-Cache habe eine Miss-Rate von 10%. Wie groß darf die Miss-Rate des Daten-Caches maximal sein, damit ein Speedup von 4, 5 gegenu ̈ber der urspru ̈nglichen Implementierung ohne Verbesserun- gen erreicht werden kann?
Seite 7 / 14
GRA/TI Aufgabe 4 (Multi-level Cache) [20 Punkte]
Ein 2 GHz Prozessor hat vier Caches, wie in Abbildung 1 dargestellt, je einen Level 1 Cache fu ̈r Instruktionen und Daten, einen gemeinsamen Level 2 und einen gemeinsamen Level 3 Cache. Die Anbindung zum Hauptspeicher ist mit einer einfachen Speicherorganisation realisiert, so dass die Worte nacheinander aus dem Speicher geholt und u ̈bertragen werden. Dabei muss, fu ̈r zusammenha ̈ngende Speicherblo ̈cke, nur einmal die Adresse u ̈bertragen werden. Der Speicherbus hat eine Taktfrequenz von 200 MHz, also eine Taktperiode von 5 ns. Im Folgenden bezeichnet cyclesP Taktzyklen des Prozessors und cyclesM Taktzyklen des Speicherbusses.
Bus
Abbildung 1: Skizze der Speicherorganisation Die Caches haben folgende Charakteristika:
Das Speichersystem hat folgende Charakteristika:
CPU
L1 Inst.
L2 unified
L1 Data
L3 unified
Memory
Cache
Gro ̈ße
Blockgro ̈ße
hit-time
miss-rate
Level 3
6 MB
16 Worte
35 cyclesP
1%
Level 2
1 MB
4 Worte
8 cyclesP
5%
Level 1 Daten
64 KB
4 Worte
1 cycleP
10 %
Level 1 Instruktionen
64 KB
4 Worte
1 cycleP
2%
Takt
Speicher- breite
Bus- breite
Adresse senden
Speicherzugriff
Datentransfer
200 MHz
1 Wort
1 Wort
2 cyclesM
26 cyclesM
2 cyclesM
Seite 8 / 14
NAME: Matrikelnummer:
(a) Wie hoch ist die miss-penalty des Level 3 Caches im System aus Abbildung 1, also wie lange braucht das System zur U ̈bertragung eines Cacheblocks aus dem Hauptspeicher? Benennen Sie die dabei Komponenten der miss-penalty Formel und geben Sie das Ergebnis in Nanosekunden an!
(b) Berechnen Sie die mittlere Zugriffszeit fu ̈r Instruktionen und die fu ̈r Daten am je- weiligen Level 1 Cache. Arbeiten Sie sich dafu ̈r vom L3 Cache hoch und geben Sie jeweils die mittlere Zugriffszeit der Stufe an.
Seite 9 / 14
GRA/TI
(c) Statt einer Speicherbank haben Sie nun 8 Speicherba ̈nke zur Verfu ̈gung, sodass Sie eine Speicherbreite von 8 realisieren, also 8 Worte gleichzeitig aus dem Speicher laden ko ̈nnen. Entwerfen Sie damit eine Speicherorganisation, die die mittlere Zugriffszeit am Level 3 Cache auf unter 45 cyclesP senkt. Beschreiben Sie Ihre Speicherorgani- sation und nennen Sie Vor- und Nachteile im Vergleich zur einfachen.
Seite 10 / 14
NAME: Matrikelnummer:
Aufgabe 5 (Busarbitrierung)
[20 Punkte]
Abbildung 2 zeigt vier Einheiten (E1…E4) und ein Memory, die an einen synchronen Bus angeschlossen sind. Es wird das Daisy-Chain Arbitrierungsschema verwendet. Zusa ̈tzlich gilt folgende Timeout-Strategie: Wenn eine Einheit zum Zeitpunkt t das Request Signal setzt und 5 Takte lang kein Grant erha ̈lt, setzt sie zum Zeitpunkt t+6 das Request Signal erneut.
Bus Arbiter
Grant1
DataRequest DataReady Data
Grant2
Grant3
Grant4
Release
Request
E1
E2
E3
E4
Memory
Abbildung 2: Daisy Chain Architektur
Das Senden von Speicheradresse und Daten erfolgt gemultiplext und dauert jeweils 2 Tak- te, dazwischen gibt es ein Delay von 1 Takt. Die Signale Release, Request und Grant sind nur fu ̈r einen Takt auf 1 gesetzt.
(a) Fu ̈llen Sie das Timing Diagramm in Abbildung 3 fu ̈r den Fall aus, dass E1, E4 und E3 zu den Zeitpunkten 1, 3 und 11 von dem Memory lesen wollen. Geben Sie bei Data ”A“ an, wenn eine Adresse gesendet wird und ”D“ wenn Daten gesendet werden.
E1 E4 E3
Request Release Grant1 Grant2 Grant3 Grant4 DataRequest DataReady Data
Abbildung 3: Timing-Diagramm Seite 11 / 14
GRA/TI
(b) Entwerfen Sie den Controller von E1 wie in Abbildung 4 dargestellt als Moore- Automaten. Gehen Sie davon aus, dass zusa ̈tzlich folgende Signale fu ̈r Einga ̈nge zur Verfu ̈gung stehen:
Requested → Logic der Einheit will Request setzen
Timeout
→ Einheit hat 5 Takte erfolglos auf Grant gewartet
Grant1 Grant2 Request
Release
DataRequest DataReady
Abbildung 4: E1 Controller
E1 Requested
Timeout
Logic
Controller
CLK
Grant1 Requested
true
Abbildung 5: Moore-Automat
Seite 12 / 14
NAME: Matrikelnummer:
E1 E4 E3
Request Release Grant1 Grant2 Grant3 Grant4 DataRequest DataReady Data
Abbildung 6: Timing-Diagramm (Ersatzlo ̈sung, falsche Lo ̈sung streichen)
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 13 / 14
GRA/TI
CLK
Grant1 Requested
true
Abbildung 7: Moore-Automat (Ersatzlo ̈sung, falsche Lo ̈sung streichen)
Seite 14 / 14