代写 algorithm MIPS compiler Klausur zur Vorlesung

Klausur zur Vorlesung
Grundlagen der Rechnerarchitektur (GRA)
Prof. Marco Platzner Fachgebiet Technische Informatik Universita ̈t Paderborn
27.09.2017
• 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
15
20
25
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) Wie nennt man die Konvention, nach der das niederwertigste Byte eines Wortes an der niedrigsten Byte-Adresse im Speicher abgelegt wird?
Little Endian Big Endian CISC
RISC
(b) Der CPI-Wert (Cycles-Per-Instruction), den ein ausgefu ̈hrtes Programm auf einem Prozessor erreicht, wird beeinflusst durch:
Programmiersprache
Compiler
Instruktionssatz des Prozessors Technologie des Prozessors
(c) Welche MIPS-Rate muss man fu ̈r einen Prozessor mit einer Taktperiode von 1 ns und einem CPI-Wert von 0,5 angeben?
Nicht bestimmbar, da zu wenige Parameter angegeben sind. 1000 MIPS
2000 MIPS
5000 MIPS
Seite 2 / 22

NAME: Matrikelnummer:
(d) Welche Maßnahmen reduzieren die Miss-penalty eines Caches? gro ̈ßerer Cache
ho ̈herer Grad an Assoziativita ̈t Victim Cache
breite Speicherorganisation
(e) Wie gross ist die durchschnittliche Rotationslatenz bei einer Festplatte mit 8000 Umdrehungen pro Minute?
7,75 μs 1,50 ms 3,75 ms 40,00 ms
Seite 3 / 22

GRA/TI Aufgabe 2 (Assembler) [15 Punkte]
(a) Gegeben ist eine unvollsta ̈ndige Implementierung der rekursiven Fibonacci-Funktion f(n). Vervollsta ̈ndigen Sie die rekursive Implementierung. Beachten Sie dabei die in der Vorlesung behandelte Konvention fu ̈r die Verwendung verschiedener Registertypen bei Funktionsaufrufen. Kommentieren Sie bitte Ihren Code.
f:
# Sichern relevanter Register
# ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # Abbruchbedingung fu ̈r die Rekursion
# $v0 = 1
# ist n < 3 ? # dann springe zu RET # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # Wiederherstellen relevanter Register # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ RET: addi $a0, $a0, -1 jal f sw $v0, 0($sp) addi $a0, $a0, -1 jal lw add f $t0, 0($sp) $v0, $v0, $t0 Seite 4 / 22 NAME: Matrikelnummer: Ersatzlo ̈sung (inkorrekte Lo ̈sung bitte streichen): f: # Sichern relevanter Register # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # Abbruchbedingung fu ̈r die Rekursion # $v0 = 1 # ist n < 3 ? # dann springe zu RET # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # Wiederherstellen relevanter Register # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ RET: addi $a0, $a0, -1 jal f sw $v0, 0($sp) addi $a0, $a0, -1 jal lw add f $t0, 0($sp) $v0, $v0, $t0 Seite 5 / 22 GRA/TI (b) Wie viele Worte werden auf dem Stack bei der Berechnung von f(n) mit n = 3,4,5 ho ̈chstens belegt? Vervollsta ̈ndigen Sie bitte die folgende Tabelle. Ersatzlo ̈sung (inkorrekte Lo ̈sung bitte streichen): n 3 4 5 maximale Stackbelegung in Worten n 3 4 5 maximale Stackbelegung in Worten (c) Die Fibonacci Funktion f(n) kann auch durch einen iterativen Algorithmus berechnet werden. Welche Vorteile wu ̈rde eine iterative Implementierung von f(n) gegenu ̈ber der rekursiven Implementierung bieten? Seite 6 / 22 NAME: Matrikelnummer: Seite 7 / 22 GRA/TI Aufgabe 3 (Instruktionssatzarchitekturen) [20 Punkte] (a) EssollendiedreiInstruktionssatzarchitekturenStack-,Speicher-Speicher-undRegister- Register-Architektur hinsichtlich des Speicherbedarfs und der Speicherbandbreite untersucht werden. Gegeben sei dafu ̈r folgendes Programm fu ̈r eine dieser Architek- turen: 1: add Adresse_A Adresse_I Adresse_I 2: mul Adresse_A Adresse_A Adresse_S 3: add Adresse_B Adresse_B Adresse_A Fu ̈r welche der Instruktionssatzarchitekturen ist dieses Programm? Stack-Architektur Speicher-Speicher-Architektur Register-Register-Architektur (b) Was berechnet das Programm? Schreiben Sie die arithmetischen Ausdru ̈cke hin. 1A= 2 3 Tabelle 1: Programm als arithmetische Sequenz (c) Erstellen Sie nun fu ̈r jede der drei Architekturen eine Assemblercodesequenz, die das Programm implementiert, und bestimmen Sie den Speicherbedarf der Instruktionen, sowie die Menge der u ̈bertragenen Daten in Bytes. Geben Sie fu ̈r die Stack- und Register-Register-Architektur außerdem die Belegung des Stacks (Abb. 1) und der Register (Abb. 3) an. Alle auftretenden Operanden (z.B. I, S, ...) sind 32 bit groß und liegen im Spei- cher. Alle Ergebnisse (A und B) sind ebenfalls 32 bit groß und mu ̈ssen nach Ablauf des Programms im Speicher abgelegt sein. Nehmen Sie an, dass der opcode einer Instruktion 1 Byte betra ̈gt, die Speicheradressen 16 bit und die Registeradressen 4 bit lang sind. Die Instruktionsla ̈nge muss ein Vielfaches von einem Byte sein. Seite 8 / 22 NAME: Matrikelnummer: (i) Stack-Architektur. Verfu ̈gbare Instruktionen: push, pop, add, mul Assembler-Instruktion Speicherbedarf U ̈bertragene Daten 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Tabelle 2: Programm in Stack-Architektur Nach Instruktion 1 Nach Instruktion 2 Nach Instruktion 3 Nach Instruktion 4 Nach Instruktion 5 Nach Instruktion 6 Nach Instruktion 7 Nach Nach Nach Nach Instruktion 11 Instruktion 12 Instruktion 13 Instruktion 14 Instruktion 15 Instruktion 16 Instruktion 17 Instruktion 18 Instruktion 19 Instruktion 20 Abbildung 1: Belegung des Stacks Nach Nach Nach Nach Nach Nach Nach Nach Nach Instruktion 8 Instruktion 9 Instruktion 10 Seite 9 / 22 GRA/TI Assembler-Instruktion Speicherbedarf U ̈bertragene Daten 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Tabelle 3: Programm in Stack-Architektur - Ersatz, ungu ̈ltige Lo ̈sung streichen! Nach Instruktion 1 Nach Instruktion 2 Nach Instruktion 3 Nach Instruktion 4 Nach Instruktion 5 Nach Instruktion 6 Nach Instruktion 7 Nach Instruktion 8 Nach Nach Instruktion 9 Instruktion 10 Nach Instruktion 11 Instruktion 12 Instruktion 13 Instruktion 14 Instruktion 15 Instruktion 16 Instruktion 17 Instruktion 18 Instruktion 19 Instruktion 20 Abbildung 2: Belegung des Stacks - Ersatz, ungu ̈ltige Lo ̈sung streichen! Seite 10 / 22 Nach Nach Nach Nach Nach Nach Nach Nach Nach NAME: Matrikelnummer: (ii) Register-Register-Architektur. Verfu ̈gbare Instr.: load, store, add, mul Assembler-Instruktion Speicherbedarf U ̈bertragene Daten 1 2 3 4 5 6 7 8 9 10 Reg0 Reg1 Reg2 Reg3 Reg4 Reg5 Nach Instruktion 1 Nach Instruktion 2 Nach Instruktion 3 Nach Instruktion 4 Nach Instruktion 5 Nach Instruktion 6 Nach Instruktion 7 Nach Nach Nach Tabelle 4: Programm in Register-Register-Architektur Abbildung 3: Belegung der Register Instruktion 8 Instruktion 9 Instruktion 10 Assembler-Instruktion Speicherbedarf U ̈bertragene Daten 1 2 3 4 5 6 7 8 9 10 Tabelle 5: Programm in Register-Register-Architektur - Ersatz, ungu ̈ltige Lo ̈sung streichen! Reg0 Reg1 Reg2 Reg3 Reg4 Reg5 Nach Instruktion 1 Nach Instruktion 2 Nach Instruktion 3 Nach Instruktion 4 Nach Instruktion 5 Nach Instruktion 6 Nach Instruktion 7 Nach Nach Nach Abbildung 4: Belegung der Register - Ersatz, ungu ̈ltige Lo ̈sung streichen! Seite 11 / 22 Instruktion 8 Instruktion 9 Instruktion 10 GRA/TI (iii) Speicher-Speicher-Architektur. Verfu ̈gbare Instruktionen: add, mul. Assembler-Instruktion Speicherbedarf U ̈bertragene Daten 1 2 3 4 5 6 7 8 9 10 Tabelle 6: Programm in Speicher-Speicher-Architektur Assembler-Instruktion Speicherbedarf U ̈bertragene Daten 1 2 3 4 5 6 7 8 9 10 Tabelle 7: Programm in Speicher-Speicher-Architektur - Ersatz, ungu ̈ltige Lo ̈sung streichen! Seite 12 / 22 NAME: Matrikelnummer: Aufgabe 4 (Pipelining) [25 Punkte] (a) Ein Prozessorhersteller entwirft eine neue Prozessorgeneration mit 10 Pipelinestu- fen. Wie hoch ist der zu erwartende Speedup gegenu ̈ber einer Mehrzyklenimple- mentierung, in der jeder Befehl des Testprogramms (9991 Instruktionen) alle 10 Taktphasen durchla ̈uft? Speedup: (b) Im folgenden soll ein Prozessor mit 5-stufiger Pipeline (IF, ID, EX, MEM, WB) be- trachtet werden. Der Registerfilezugriff erfolgt im Ganztaktverfahren. Der Prozessor verwendet eine Harvard-Architektur. Die Pipeline verwendet kein Forwarding. Folgendes Assembler Codefragment soll auf dem Prozessor ausgefu ̈hrt werden: 0: sub $t2, $t1, $t3 1: and $t4, $t2, $t5 2: or $t4, $t4, $t2 3: add $t9, $t4, $t2 Seite 13 / 22 GRA/TI (i) Geben Sie die Pipelinebelegung – fu ̈r das oben gezeigte Codefragment – fu ̈r den Fall an, dass die Pipeline bei einem auftretenden Konflikt angehalten wird. Fu ̈llen Sie hierzu das Diagramm in Abbildung 5 aus. Takte sub $t2, $t1, $t3 and $t4, $t2, $t5 or $t4, $t4, $t2 add $t9, $t4, $t2 Takte sub $t2, $t1, $t3 and $t4, $t2, $t5 or $t4, $t4, $t2 add $t9, $t4, $t2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 IF ID EX ME WB Abbildung 5: Pipelinebelegung fu ̈r (i) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 IF ID EX ME WB Abbildung 6: Ersatzdiagramm: Pipelinebelegung fu ̈r (i) (ii) Wie vera ̈ndert sich die Pipelinebelegung wenn Forwarding verwendet wird? Fu ̈llen Sie hierzu das Diagramm in Abbildung 7 aus. Machen Sie das Forwar- ding mit Hilfe von Pfeilen deutlich. Takte sub $t2, $t1, $t3 and $t4, $t2, $t5 or $t4, $t4, $t2 add $t9, $t4, $t2 Takte sub $t2, $t1, $t3 and $t4, $t2, $t5 or $t4, $t4, $t2 add $t9, $t4, $t2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 IF ID EX ME WB Abbildung 7: Pipelinebelegung fu ̈r (ii) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 IF ID EX ME WB Abbildung 8: Ersatzdiagramm: Pipelinebelegung fu ̈r (ii) Seite 14 / 22 NAME: Matrikelnummer: (c) Nun soll das folgende Codefragment auf dem Prozessor ohne Forwarding ausgefu ̈hrt werden. Der Registerfilezugriff findet im Ganztaktverfahren statt. Die Zeile 1: liegt im Befehlsspeicher an der Adresse 0x00200010. 1: addi 2: addi 3: addi 4: sub 5: add $t1, $zero, 20 $t2, $zero, 22 $t3, $zero, 11 $t4, $t1, $t1 $t5, $t2, $t3 Wie sind die Busbelegungen an Stellen (siehe Abbildung 9) innerhalb der einzelnen Pipelinestufen, zu dem Zeit- punkt in dem der Befehl der Zeile 5 die IF Stufe erreicht hat? Geben Sie die Busbelegung in Hexadezimal- oder Bina ̈rdarstellung an. Fu ̈llen Sie hierzu die Tabelle 8 aus. Hinweis: add: sub: addi: den mit den Buchstaben (a-p) gekennzeichneten opcode 000000 rs rt rd shamt 00000 funct 100000 opcode 000000 rs rt rd shamt 00000 funct 100010 opcode 001000 rs rt immediate Seite 15 / 22 GRA/TI Abbildung 9: Pipeline-Datenpfad Seite 16 / 22 a Address Read Data2 4 p o M U X IF RF EX MEM WB Instruction Memory b M M U X c Read Reg.1 d Read Reg.2 Read Data1 ik jl e Write Reg. n Data Memory f Write RF Data U X g h M m U X Address Read Data Write Data Sign. Extend ALU ADD PC Shift left 2 ADD NAME: Matrikelnummer: a: b: c: d: e: f: g: h: i: j: k: l: m: n: o: p: opcode 000000 rs rt rd shamt 00000 funct 100000 opcode 000000 rs rt rd shamt 00000 funct 100010 Tabelle 8: Busbelegung fu ̈r (c) Seite 17 / 22 GRA/TI a: b: c: d: e: f: g: h: i: j: k: l: m: n: o: p: opcode 000000 rs rt rd shamt 00000 funct 100000 opcode 000000 rs rt rd shamt 00000 funct 100010 Tabelle 9: Ersatztabelle: Busbelegung fu ̈r (c) Seite 18 / 22 NAME: Matrikelnummer: Aufgabe 5 (Arbitrierung) [15 Punkte] Abbildung 10(a) zeigt ein System mit zwei CPUs, die an einen gemeinsamen Bus ange- schlossen sind. Da beide CPUs Busmaster werden ko ̈nnen, wird der Buszugriff durch einen zentralen Arbiter gesteuert. Die CPUs fordern u ̈ber request-Signale (r1=1 bzw. r2=1) den Bus an. Falls einer CPU der Buszugriff gewa ̈hrt wird, antwortet der Arbiter mit einem grant-Signal (g1=1 bzw. g2=1). Gibt eine CPU den Bus wieder frei, wird das entsprechen- de request Signal wieder auf 0 gesetzt, worauf der Arbiter das entsprechende grant-Signal auch wieder auf 0 setzt. (a) Blockdiagramm (b) Zustandsautomat fu ̈r den Arbiter Abbildung 10: System mit zwei CPUs und zentralem Arbiter (a) Abbildung 10(b) zeigt den Moore-Zustandsautomat des zentralen Arbiters. Die Aus- gabesignale (g1,g2) sind in den Zusta ̈nden angegeben. Begru ̈nden Sie, ob dieser Arbiter den CPUs unterschiedliche Priorita ̈ten zuweist. Wenn ja, welche der CPUs hat die ho ̈here Prioria ̈t? r1.r2 S0 0 0 Sx g1 g2 r1.r2 r2 r1 r1 r2 r2 10 01 S1 S2 Arbiter g1r1 r2g2 Bus CPU1 CPU2 Seite 19 / 22 GRA/TI (b) Skizzieren Sie ein Blockdiagramm fu ̈r ein System mit zwei CPUs und einem gemein- samen Bus, das Daisy-Chain Arbitrierung verwendet. Zeichnen Sie alle Steuersignale ein und benennen Sie diese. Die Arbitrierung soll dieselben Priorita ̈ten fu ̈r die CPUs imple- mentieren wie die zentrale Arbitrierung in Abbildung 10(b). (c) Entwerfen Sie einen zentralen Busarbiter, der keine festen Priorita ̈ten vergibt, sondern ”fair” ist. Ein ”fairer” Arbiter weist den CPUs abwechselnd den Bus zu, falls sie ihn gleichzeitig anfordern. Geben Sie den Moore-Zustandsautomat Ihres ”fairen” Arbiters an. Seite 20 / 22 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 21 / 22 GRA/TI 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 22 / 22