Musterlo ̈sung
U ̈bung7 RAWiSe18/19
Diese U ̈bung bescha ̈ftigt sich mit der in der Vorlesung besprochenen Mehrzyklenimple- mentierung des MIPS subsets. Am Ende dieses U ̈bungsblattes befinden sich mehrere iden- tische 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 (Erweiterung der Mehrzyklenimplementierung)
Erweitern Sie die in der Vorlesung besprochene Mehrzyklenimplementierung derart, dass die Instruktion jal abgearbeitet werden kann. Gehen Sie folgendermassen vor:
(1) Erweiteren Sie – falls no ̈tig – den Datenpfad und die Steuersignale und zeichnen Sie diese Erweiterungen in einem Zusatzblatt ein.
(2) Beschreiben Sie den Ablauf des Instruktionszyklus fu ̈r jal in der in der Vorlesung verwendeten Pseudocode-Notation. Geben Sie fu ̈r jeden der Taktschritte IF, ID, EX, MEM und WB die Signalzuweisungen an.
(3) Geben Sie den Automatengraphen fu ̈r den um jal erweiterten Kontroller an. Musterlo ̈sung
(1) Es sind zwei Erweiterungen des Datenpfads und der Steuersignale notwendig:
1. DasRegister$ramussalsdaszuschreibendeRegisterdesRegisterfilesauswa ̈hl- bar sein. Dazu sind das Steuersignal RegDst auf zwei Leitungen und der ent- sprechende Multiplexer um einen weiteren Eingang mit der fest kodierten Adresse von $ra (31) zu erweitern.
2. Fu ̈r das in das Registerfile zu schreibende Datum soll zusa ̈tzlich der PC auswa ̈hl- bar sein. Dazu mu ̈ssen das Steuersignal MemToReg auf zwei Leitungen und der entsprechende Multiplexer um einen mit dem PC verbundenen Eingang erwei- tert werden.
(2) Die IF- und ID-Phasen bleiben unvera ̈ndert, die MEM- und WB-Phasen werden nicht beno ̈tigt.
EX-Phase: Reg[31] <= PC
PC <= {PC[31:28], IR[25:0], 00}
RegDst=10
MemToReg=10
RegWrite
PCSource=10
PCWrite
Seite 1 / 8
Musterlo ̈sung
U ̈bung7 RAWiSe18/19
Abbildung 1: Erweiterung des Datenpfads und der Steuersignale der Mehryklenimplemen- tierung fu ̈r die jal-Instruktion und der zugeho ̈rige Automatengraph.
Seite 2 / 8
Musterlo ̈sung
U ̈bung7 RAWiSe18/19
Aufgabe 2 (Erweiterung der Mehrzyklenimplementierung)
Die Mehrzyklenimplementierung soll um eine neuartige Instruktion wai erweitert werden. wai steht fu ̈r “where-am-I” und soll die Adresse der gerade ausgefu ̈hrten Instruktion in ein Register laden.
(1) Definieren Sie eine geeignete Instruktionscodierung fu ̈r wai.
(2) Erweiteren Sie – falls no ̈tig – den Datenpfad und die Steuersignale und zeichnen Sie
diese Erweiterungen in einem Zusatzblatt ein.
(3) Beschreiben Sie den Ablauf des Instruktionszyklus fu ̈r wai in der in der Vorlesung verwendeten Pseudocode-Notation. Geben Sie fu ̈r jeden der Taktschritte IF, ID, EX, MEM und WB die Signalzuweisungen an.
(4) Geben Sie den Automatengraphen fu ̈r den um wai erweiterten Kontroller an. Musterlo ̈sung
(1) Fu ̈r die Instruktion ”wai $reg” beno ̈tigt man einen Registeroperanden. Grundsa ̈tz- lich wa ̈ren die zwei Instruktionscodierungen R-Type und I-Type geeignet, da beide Felder fu ̈r Registeroperanden haben. Die Implementierung der wai Instruktion mit einer R-Type Codierung ist aber unangenehm, da alle R-Type Instruktionen den opcode von 0 haben, und sich nur in dem Feld funct unterscheiden. Dieses Feld wird in der bisherigen Implementierung nicht im Hauptkontroller, sondern im ALU- Kontroller verwendet. Um die wai Instruktion als R-Type Instruktion verarbeiten zu ko ̈nnen, mu ̈sste man das funct Feld auch im Hautpkontroller verwenden.
Die I-Type Codierung ist besser geeignet. Im opcode Feld muss der neue Opcode fu ̈r wai stehen. Da das Register geschrieben wird, sollte der Registeroperand im rt-Feld codiert sein. Alle anderen Felder sind don’t cares.
(2) Der Datenpfad und und die Steuersignale mu ̈ssen nicht erweitert werden.
(3) Die IF- und ID-Phasen bleiben unvera ̈ndert. Da in der IF-Phase der PC bereits um 4 erho ̈ht wurde, muss man vom PC wieder 4 subtrahieren, um die Adresse der aktuellen Instruktion zu erhalten. Dies geschieht in der EX-Phase. Erst danach in der MEM-Phase kann der Wert in ein Register geschrieben werden. Die WB-Phase wird nicht beno ̈tigt.
Seite 3 / 8
Musterlo ̈sung
U ̈bung7 RAWiSe18/19
EX-Phase: ALUOut <= PC - 4
ALUsrcA=0
ALUsrcB=01
ALUOp=01
MEM-Phase: Reg[IR[20:16]] <= ALUOut
RegDst=0
MemToReg=0
RegWrite
Abbildung 2: Automatengraph fu ̈r den um wai erweiterten Kontroller.
Eine alternative Implementierung der wai Instruktion ko ̈nnte die Tatsache nutzen, dass immer in der ID-Phase die Sprungadresse fu ̈r einen bedingten Sprung berechnet und in das Register ALUOut geschrieben wird. Setzt man den Offset (immediate Feld des I-Type Formats) auf -1, so wird wieder die Adresse der gerade aktiven Instruktion berechnet. In der EX-Phase muss dann das Register ALUOut in das Zielregister geschrieben werden. Diese Variante hat den Vorteil, dass die wai Instruktion nur 3 Schritte beno ̈tigt.
Seite 4 / 8
Musterlo ̈sung
U ̈bung7 RAWiSe18/19
Aufgabe 3 (Performancevergleich)
Fu ̈r diese Aufgabe wird folgender Instruktionsmix angenommen:
Zu vergleichen sind drei Implementierungen eines Instruktionssatzes:
• Implementierung M1:
M1 ist eine Mehrzyklenimplementierung wie in der Vorlesung besprochen. Die Takt- frequenz betra ̈gt 600 MHz.
• Implementierung M2:
M2 baut auf M1 auf. Der Unterschied besteht darin, dass bei M2 das Schreiben von Registern im selben Taktzyklus geschieht wie das Lesen des Speichers oder eine ALU Operation. Im Automatengraph des Kontrollers fallen dann die Zusta ̈nde 6 und 7 bzw. 3 und 4 zusammen. Allerdings wird die maximale kombinatorische Verzo ̈gerung gro ̈sser. Die Taktfrequenz der resultierenden Implementierung kann deshalb maximal 400 MHz betragen.
• Implementierung M3:
M3 baut auf M2 auf. Die Erweiterung besteht darin, dass die Speicheradresse im selben Taktzyklus bestimmt wird, in dem auch der Speicherzugriff stattfindet. Im Automatengraph des Kontrollers fallen dann die Zusta ̈nde 2, 3 und 4 bzw. 2 und 5 bzw. 6 und 7 zusammen. Die resultierende Implementierung beno ̈tigt eine noch la ̈ngere Taktperiode und hat deshalb eine maximale Taktfrequenz von 300 MHz.
Stellen Sie fest, welche Implementierung die ho ̈chste Performance hat. Verwenden Sie als Performancemetrik die MIPS-Rate. Warum ist die MIPS-Rate in diesem Fall eine geeignete Performancemetrik?
Instruktionsklasse
relative Ha ̈ufigkeit
lw
30%
sw
15%
R-Type
43%
beq, j
12%
Musterlo ̈sung
MIPS = CPI =
Ic = Ic
=f[MHz] Texe·106 Ic ·CPI·T ·106 CPI
n
(CPIi · Fi) i=1
Seite 5 / 8
Musterlo ̈sung
U ̈bung7 RAWiSe18/19
• Implementierung M1:
Abbildung 3: Automatengraph fu ̈r die Implementierung M1.
0
1 2689
357
4
beq, j CPI = 3 12%
lw CPI = 5 30%
sw CPI = 4 15%
R-Type CPI = 4 43%
Instruktionsklasse
relative Ha ̈ufigkeit
CPIi
lw
30%
5
sw
15%
4
R-Type
43%
4
beq, j
12%
3
⇒ CPIM1 = 5 · 0,3 + 4 · 0,15 + 4 · 0,43 + 3 · 0,12 = 4,18
⇒ MIPSM1 = 600 = 143,54 4,18
Seite 6 / 8
Musterlo ̈sung
U ̈bung7 RAWiSe18/19
• Implementierung M2:
0
1 2689
357
4
beq, j CPI = 3 12%
lw CPI = 4 30%
sw CPI = 4 15%
R-Type CPI = 3 43%
Abbildung 4: Automatengraph fu ̈r die Implementierung M2.
⇒ CPI = 4·0,3+4·0,15+3·0,43+3·0,12 = 3,45 ⇒ MIPS = 400 = 115,94 M2 M2 3,45
Instruktionsklasse
relative Ha ̈ufigkeit
CPIi
lw
30%
4
sw
15%
4
R-Type
43%
3
beq, j
12%
3
Seite 7 / 8
Musterlo ̈sung
U ̈bung7 RAWiSe18/19
• Implementierung M3:
2
0
1
2689
beq,j CPI = 3 12%
357
4
lw CPI = 3 30%
sw CPI = 3 15%
R-Type CPI = 3 43%
Abbildung 5: Automatengraph fu ̈r die Implementierung M3.
⇒CPI =3·0,3+3·0,15+3·0,43+3·0,12=3⇒MIPS =300 =100 M2 M2 3
Die Implementierung M1 hat die ho ̈chste Performance. Da sich der Instruktionssatz der Prozessoren in diesem Beispiel nicht unterscheidet und wir von identischen Ic-Werten ausgehen (das Programm wird hier gar nicht diskutiert), ist die MIPS-Rate eine geeignete Metrik.
Instruktionsklasse
relative Ha ̈ufigkeit
CPIi
lw
30%
3
sw
15%
3
R-Type
43%
3
beq, j
12%
3
Seite 8 / 8