Musterlo ̈sung
U ̈bung6 RAWiSe18/19
Diese U ̈bung bescha ̈ftigt sich mit der in der Vorlesung besprochenen Einzyklenimplemen- tierungdesMIPSsubsets.AmEndediesesU ̈bungsblattesbefindensichmehrereidentische Zusatzbla ̈tter mit dem Schaltbild fu ̈r den Datenpfad und den Kontroller. Verwenden Sie diese Zusatzbla ̈tter fu ̈r die in den Aufgaben geforderten Erweiterungen.
Aufgabe 1 (Kontroller fu ̈r Einzyklenimplementierung)
(1) Definieren Sie die Steuersignale, die der Kontroller der Einzyklenimplementierung generiert. Vervollsta ̈ndigen Sie dazu Tabelle 1. Die Steuersignale fu ̈r ALUOp[1:0], den ALU-Kontroller, entnehmen Sie den Vorlesungsunterlagen. Verwenden Sie, wenn mo ̈glich, don’t care Werte X fu ̈r die Steuersignale.
Tabelle 1: Steuerleitungen fu ̈r die MIPS Einzyklenimplementierung
(2) Zeichnen Sie fu ̈r die verschiedenen Instruktionen die Werte der Steuersignale in ein Zusatzblatt ein. Erkla ̈ren Sie den Ablauf des Instruktionszyklus und identifizieren Sie jeweils die Elemente des Datenpfades, die keine Rolle spielen.
Musterlo ̈sung
(1) Lo ̈sungstabelle:
Tabelle 2: Werte der Steuerleitungen fu ̈r die MIPS Einzyklenimplementierung
(2) In den Zeichnungen 1 bis 4 finden sich die jeweils wesentlichen Signale des Datenpfa- des gestrichelt wiedergegeben. Die jeweils aktiven Elemente des Datenpfades sind die, deren Einga ̈nge mit einem gestrichelt gezeichneten Signal belegt sind.
Instr.
RegDst
ALUSrc
MemtoReg
RegWrite
MemRead
MemWrite
Branch
ALUOp[1:0]
R-Type
lw
sw
beq
Instr.
RegDst
ALUSrc
MemtoReg
RegWrite
MemRead
MemWrite
Branch
ALUOp[1:0]
R-Type
1
0
0
1
0
0
0
10
lw
0
1
1
1
1
0
0
00
sw
X
1
X
0
0
1
0
00
beq
X
0
X
0
0
0
1
01
Seite 1 / 8
Musterlo ̈sung
U ̈bung6 RAWiSe18/19
Abbildung 1: R-Typ.
Aufgabe 2 (Vereinfachung des Kontrollers)
(1) Kann man in der Einzyklenimplementierung auf das Steuersignal MemtoReg ver- zichten und den Multiplexer am Ausgang des Datenspeichers stattdessen mit dem Steuersignal MemRead ansteuern?
(2) Gibt es weitere Mo ̈glichkeiten, die Anzahl der Steuersignale zu reduzieren? Falls ja, unter welchen Voraussetzungen?
Musterlo ̈sung
(1) Ja, ein solcher Verzicht auf das Steuersignal MemToReg ist mo ̈glich. In der Ein- zyklenimplementierung sind die Signalwerte von MemRead deckungsgleich mit den notwendigen Werten fu ̈r MemToReg. Insbesondere gilt dies fu ̈r den Wert don’t care (X). Somit ko ̈nnen die notwendigen Signalwerte fu ̈r MemToReg problemlos durch die Werte von MemRead gebildet werden.
(2) Nein, eine weitere Gleichheit bzw. U ̈berdeckung von Steuersignalen kann mit Blick auf Tabelle 2 ausgeschlossen werden. Dort finden sich keine weiteren Mo ̈glichkeiten
Seite 2 / 8
Musterlo ̈sung
U ̈bung6 RAWiSe18/19
zur Reduktion.
Abbildung 2: lw
Hinweis 1: Das Signal MemToReg ko ̈nnte man auch durch das Signal ALUSrc er- setzen.
Hinweis 2: Ha ̈tte man einen Datenspeicher, den man in einem Taktzyklus lesen und schreiben kann (a ̈hnlich wie das Registerfile), ga ̈be es weiteres Potential zum Sparen von Steuerleitungen. Es mu ̈sste dann ja nicht mehr gelten, dass nur eine der Steuerleitungen MemWrite und MemRead auf 1 sein darf. Man ko ̈nnte dann bei einigen Instruktionen MemRead auf don’t care setzen und es zB. durch ALUSrc ersetzen.
Seite 3 / 8
Musterlo ̈sung
U ̈bung6 RAWiSe18/19
Abbildung 3: sw
Aufgabe 3 (Erweiterungen der Einzyklenimplementierung)
Erweitern Sie den MIPS Einzyklendatenpfad derart, dass folgende Instruktionen verar- beitet werden ko ̈nnen:
(1) j (2) addi (3) jal (4) sll
Geben Sie auf den Zusatzbla ̈ttern jeweils die Datenpfadelemente und Steuerleitungen an, die zusa ̈tzlich zu der in der Vorlesung besprochenen Implementierung beno ̈tigt werden. Zeichnen Sie fu ̈r die neuen Instruktionen die Werte der Steuersignale in das Zusatzblatt ein. Erkla ̈ren Sie wiederum den Ablauf des Instruktionszyklus und identifizieren Sie jeweils die Elemente des Datenpfades, die keine Rolle spielen.
Hinweis 1:
Bei den unbedingten Sprunginstruktionen j und jal wird die Sprungadresse durch Kon- katenation der ho ̈chstwertigsten 4 Bit des PC mit der 26-bit Konstanten in der Instruktion gebildet. Diese Adresse ist eine Wortadresse, dh. die niederwertigsten 2 Bit werden auf 0 gesetzt. Das kann zB. realisiert werden, indem die 26-bit Konstante um 2 Bit nach links
Seite 4 / 8
Musterlo ̈sung
U ̈bung6 RAWiSe18/19
Abbildung 4: beq
geschoben wird. MIPS definiert, dass fu ̈r diese Adressbildung der erho ̈hte PC, also PC+4, genommen werden muss.
Hinweis 2:
Fu ̈r die Implementierung der Instruktion sll nehmen Sie an, dass die ALU um einen barrel shifter erweitert wurde. Ein barrel shifter ist eine kombinatorische Schaltung, die ein Eingangswort um eine variable Anzahl von Stellen, vorgegeben durch einen Kontroll- eingang, schiebt. Sie ko ̈nnen annehmen, dass die ALU einen zusa ̈tzlichen Eingang hat, an dem ein bina ̈res Wort angelegt wird, das die Anzahl der Stellen darstellt, um die der obere ALU-Eingang geschoben wird.
Musterlo ̈sung
(1) j
Hier muss das Instruktionsformat J-Typ unterstu ̈tzt werden. Dazu ist das Einfu ̈hren eines Kontrollsignals Jump notwendig. Dieses steuert einen weiteren Multiplexer an, der ein Auswa ̈hlen des neuen Wertes fu ̈r den PC ermo ̈glicht. Dieser Multiplexer befindet sich nach dem ”Branch-Multiplexer”, bzw. unmittelbar vor dem PC. Der neue Wert fu ̈r den PC wird dabei gebildet, indem vom eigentlichen Wert des PC+4 die Bits 31-28 mit den um zwei nach links geshifteten Bits der Sprungadresse aus dem target Feld des Befehls konkateniert werden.
(2) addi
Seite 5 / 8
Musterlo ̈sung
U ̈bung6 RAWiSe18/19
Hier muss nichts erweitert werden. Die Instruktion verwendet die I-Typ Codierung und kann mit der gegebenen Schaltung bereits realisiert werden.
(3) jal
Bei diesem Befehl muss zusa ̈tzlich zum j-Befehl die Ru ̈cksprungadresse (PC+4) im Register $ra gesichert werden. Folglich wird eine Verbindung zwischen dem PC+4 und dem Write data Eingang der Register gezogen. Zur Auswahl des Registers wird vor den Eingang Write register ein Multiplexer platziert, welcher entweder den bis- herigen Wert durchschaltet oder einen Eingang, der fest auf die Adresse von $ra (31) codiert ist. Ein neues Kontrollsignal ist festzulegen, welches diesen Multiplexer ansteuert.
(4) sll
Die Anzahl der Stellen, um die geschoben wird, stehen in den Bits 10 bis 6 des Befehls (R-Typ). Diese mu ̈ssen an den wie in Hinweis 2 beschriebenen weiteren Ein- gang der ALU weitergereicht werden. Bei MIPS wird dieser zusa ̈tzliche Eingang nur ausgewertet, wenn der zugeho ̈rige funct-Code (in den Bits 5 bis 0 der Instruktion) dies vorschreibt.
Wu ̈rde die angelegte Konstante innerhalb der ALU stets verwendet, mu ̈sste dieser Eingang zudem noch mittels eines Multiplexers auf 0 gelegt werden, wodurch ein weiteres Steuersignal notwendig werden wu ̈rde.
Seite 6 / 8
Musterlo ̈sung
U ̈bung6 RAWiSe18/19
Aufgabe 4 (Performance der Einzyklenimplementierung)
Fu ̈r eine Einzyklenimplementierung sind folgende kombinatorische Verzo ̈gerungszeiten ge- geben: Ein Speicherzugriff beno ̈tigt 250 ps, sowohl fu ̈r das Lesen als auch das Schreiben. Eine ALU-Operation bzw. eine Adder-Operation dauert 40 ps. Der Zugriff auf das Re- gisterfile dauert auch 40 ps, sowohl fu ̈r das Lesen als auch das Schreiben. Alle ande- ren Verzo ̈gerungszeiten (zB. der Multiplexer, Kontroller, Leitungen, etc.) werden ver- nachla ̈ssigt.
Fu ̈r diese Aufgabe wird folgender Instruktionsmix angenommen:
Untersuchen Sie die relative Performance zwischen einer “normalen” Einzyklenimplemen- tierung und einer Einzyklenimplementierung mit einer Taktperiode variabler La ̈nge. Bei der normalen Einzyklenimplementierung wird jede Instruktion in einer Taktperiode kon- stanter La ̈nge abgearbeitet. Bei der Implementierung mit Taktperiode variabler La ̈nge kann fu ̈r jede Instruktion die jeweils kleinstmo ̈gliche Taktperiode verwendet werden. Man kann sich vorstellen, dass man abha ̈ngig von der Instruktion die Periode des Taktsignals a ̈ndern kann. Eine solche Implementierung ist zwar nicht praktikabel, der Performancever- gleich zeigt aber den potentiellen “Performanceverlust” einer Einzyklenimplementierung auf. Als Hilfestellung dient folgende Tabelle:
Tabelle 3: Verzo ̈gerungszeiten fu ̈r die Instruktionen
Musterlo ̈sung
Tabelle 4: Verzo ̈gerungszeiten fu ̈r die Instruktionen, Lo ̈sung
Instruktion
relative Ha ̈ufigkeit
lw
25%
sw
10%
R-Type
45%
beq
15%
j
5%
Instruktion
Instr.Memory
Reg.Read
ALUOperation
DataMemory
Reg.Write
Summe
R-Type
lw
sw
beq
j
Instruktion
Instr.Memory
Reg.Read
ALUOperation
DataMemory
Reg.Write
Summe
R-Type
250 ps
40 ps
40 ps
0
40 ps
370 ps
lw
250 ps
40 ps
40 ps
250 ps
40 ps
620 ps
sw
250 ps
40 ps
40 ps
250 ps
0
580 ps
beq
250 ps
40 ps
40 ps
0
0
330 ps
j
250 ps
0
0
0
0
250 ps
Seite 7 / 8
Musterlo ̈sung
U ̈bung6 RAWiSe18/19
Mit Hilfe der Tabelle ergibt sich fu ̈r die relative Performance:
Performancevariabel = 620 =
Performancenormal 370 · 0,45 + 620 · 0,25 + 580 · 0,1 + 330 · 0,15 + 250 · 0,05 = 1,41
Somit ergibt sich eine theoretisch mo ̈gliche Verbesserung einer Einzyklenimplementierung mit variabler Taktla ̈nge um 41 % gegenu ̈ber einer Einzyklenimplementierung mit fester Taktla ̈nge.
Seite 8 / 8