[SOLVED] R C MIPS graph Rechnerarchitektur (RA)

Rechnerarchitektur (RA)
4. Prozessorentwurf: Datenpfad und Kontroller
Prof. Dr. Christian Plessl
RA.4 2018 v1.0.1
1

4. Prozessorentwurf: Datenpfad und Kontroller
4.1 ElementedesDatenpfades 4.2 Einzyklenimplementierung 4.3 Mehrzyklenimplementierung
RA.4 2018 v1.0.0
Inhaltsverzeichnis
2

Implementierung eines MIPS Subsets
Wir betrachten im folgenden eine MIPS-Implementierung mit vereinfachtem Instruktionssatz (aber allen Instruktionsformaten):
Datentransferinstruktionen:
Arithmetik/Logikinstruktionen:
Verzweigungsinstruktionen:
lw, sw
add, sub, and, or, slt
beq, j
Ein Prozessor besteht aus einem Datenpfad und einem Kontroller.
Vorgehensweise (siehe Digitaltechnik Kapitel 8.4, Entwurf auf der RT-Ebene)
Entwurf des Datenpfades
Welche RT-Komponenten werden fur die verschiedenen Operationen benotigt? Definition der Steuer- und Statussignale
Entwurf des Kontrollers
Pro sequentiellem Schritt im Ablauf einen Zustand definieren
Fur jeden Zustand: Folgezustande und zu setzende Steuersignale bestimmen Kontroller fest-verdrahtet oder mikroprogrammiert realisieren
RA.4 2018 v1.0.0
3

Taktverfahren
Die Gesamtschaltung besteht aus kombinatorischen und sequentiellen Teilen.
Es gibt ein systemweites Taktsignal (CLOCK). Alle Register sind flankengesteuert. Ein sequentielles Element kann in einer Taktperiode gelesen und geschrieben
werden.
sequentielles kombinatorischer
Element
Schaltungsteil
t1 t2 tn
CLOCK
Die Taktperiode muss mindestens so gross wie die maximale Summe aller kombinatorischen Verzogerungszeiten zwischen zwei Registerstufen sein.
T 3max{ti} 4
RA.4 2018 v1.0.0

4.1 Elemente des Datenpfads
Laden der Instruktion, Erhohung des Program Counter (PC)
In jedem Instruktionszyklus wird eine Instruktion aus dem Speicher geholt.
Im Register PC steht die Adresse der Instruktion, die geholt wird.
Meistens ist die nachste auszufuhrende Instruktion an der folgenden Adresse zu finden, dh. PC PC + 4
Komponenten
Instruktionsspeicher
Register PC
Addierer
Instruktionsspeicher
Eingang: Adresse (32 Bit) Ausgang: Instruktion (32 Bit)
Da der Instruktionsspeicher nur gelesen wird, sind keine Steuersignale notig. Man kann diesen Speicher als kombinatorisches Element betrachten.
RA.4 2018 v1.0.0
5

Elemente des Datenpfads
Komponenten
Program Counter
Bei der Taktflanke wird der PC mit dem neuen Wert geladen.
Addierer PC PC + 4
RA.4 2018 v1.0.0
6

Elemente des Datenpfads
Teil des Datenpfades zum Laden der Instruktion und Erhohung des PC
RA.4 2018 v1.0.0
7

Elemente des Datenpfads
Arithmetik- und Logikinstruktionen
Lesen von 2 Registern, Ausfuhren der Berechnung und Schreiben in ein Register
Komponenten Registerfile
ALU
Registerfile
Eingange:
2 Registeradressen (5 Bit), die angeben,
welche Register gelesen werden
1 Registeradresse (5 Bit), die angibt, welches Register geschrieben wird
Dateneingang zum Schreiben (32 Bit)
getaktetes Steuersignal RegWrite zeigt an, wann das Register geschrieben wird
Ausgange:
2 Datenausgange (32 Bit) fur die Register,
die gelesen werden
RA.4 2018 v1.0.0
8

Registerfile mit 32 Registern, 2 Lese- und einem Schreibeport:
Read Register 1 5 Read Register 2 5 RegWrite
Write Register
5
Entwurf eines Multiport-Registerfiles
D aC
Register 0
0
5-to-32 decoder
31
&
32-MUX
Read Data 1
32
D
Register 31 C
&
32-MUX
Read Data 2
32
Write Data 32
RA.4 2018 v1.0.0
9

1-bit ALU fur die Operationen AND, OR, ADD:
cin operation
ALU Entwurf
&
0
1 3-MUX
2
>=1
full adder
a
b
z
cout
RA.4 2018 v1.0.0
10

ALU Erweiterungen
sub durch Addition des 2er-Komplements b invertieren, Cin(0)=1
nor durch a+b = a . b a invertieren, b invertieren
slt durch ab < 0 ? hochstwertigste Stelle generiert ein set-Signal, das angibt, ob a =1
z
b less
cout
0 2-MUX
1
full adder
1
RA.4 2018 v1.0.0
0
1
4-MUX
2
3
11

ainvert bnegate
operation
32-Bit ALU
a0 b0
a1 b1
z0
sub durch bnegate= 1 binvert = Cin(0) =1
beqdurch ab = 0? zero = z0++z31
z1
0
cin
ALU0
less cout
cin
ALU1
less
cout
zero
1
a31 b31
z31 RA.4 2018 v1.0.0
0
less
cin
ALU31
set
>=1
12

ALU Ein/Ausgange
4
ainvert bnegate operation (2 Bit)
RA.4 2018 v1.0.0
13

Elemente des Datenpfads
Datentransferinstruktionen
Berechnen einer Speicheradresse
Schreiben eines Registers in den Speicher oder Lesen vom Speicher in ein Register
Komponenten
Vorzeichenerweiterung
Datenspeicher
ALU, Registerfile
Vorzeichenerweiterung
Eingang: Operand im 2er-Komplement (16 Bit) Ausgang: Operand im 2er-Komplement (32 Bit)
Kopieren des Bit 15 in alle hoherwertigen Bits
RA.4 2018 v1.0.0
14

Elemente des Datenpfads
Komponenten
Datenspeicher
Eingange:
Adresse (32 Bit)
Daten, die geschrieben werden (32 Bit)
getaktetes Steuersignal MemWrite zeigt an, wann die Daten geschrieben werden sollen
Steuersignal MemRead zeigt an, wann die Daten gelesen werden sollen
Ausgang: gelesene Daten (32 Bit)
RA.4 2018 v1.0.0
15

Elemente des Datenpfads
Verzweigungsinstruktionen
Feststellen, ob der Sprung ausgefuhrt wird oder nicht
Berechnen der Sprungzieladresse aus Basis und Offset:
MIPS definiert als Basis fur bedingte Sprunge die Adresse der Instruktion nach der Verzweigungsinstruktion (PC+4)
der 16-bit Offset muss zu (PC+4) dazu addiert werden
das Offset-Feld muss um 2 Bit nach links verschoben werden (Wortadresse)
Komponenten
Registerfile, ALU, Vorzeichenerweiterung
Shifter, Addierer
RA.4 2018 v1.0.0
16

Elemente des Datenpfads
Teil des Datenpfades fur bedingte Verzweigungen
RA.4 2018 v1.0.0
17

Prinzip
Jede Instruktion wird in einem Taktzyklus ausgefuhrt.
Jede Komponente das Datenpfades kann wahrend eines Instruktionszyklus maximal einmal verwendet werden. Daher muss es auch getrennte Speicher fur Instruktionen und Daten geben.
Damit alle Instruktionsklassen die gleichen Datenpfadelemente nutzen konnen, benotigt man mehrere Multiplexer.
Vorteil
sehr einfache Implementierung; besonders der Kontrollerentwurf ist einfach
Nachteil
Die Instruktionen benotigen unterschiedliche Datenpfadelemente und haben daher unterschiedliche kombinatorische Gesamtverzogerungen. Als Taktperiode T muss das Maximum aller Verzogerungen genommen werden.
der CPI-Wert ist zwar 1, aber T wird relativ gross werden
4.2 Einzyklenimplementierung
RA.4 2018 v1.0.0
18

Datenpfad der Einzyklenimplementierung
RA.4 2018 v1.0.0
19

31 26 25
21 20
16 15
11 10
6 5
0
31 26 25
21 20
16 15
0
Kontroller-Entwurf
Hier fur add, sub, and, or, slt, beq, lw, sw Instruktionsformate:
op
rs
rt
rd
shamt
funct
R-Typ
op
rs
rt
immediate
I-Typ
J-Typ
31 26 25
0
op
target
RA.4 2018 v1.0.0
20

Instruktionscodierungen
Instruction
Type
op
funct
add
R
0x0
0x20
sub
R
0x0
0x22
and
R
0x0
0x24
or
R
0x0
0x25
slt
R
0x0
0x2a
beq
I
0x4
lw
I
0x23
sw
I
0x2b
j
J
0x2
RA.4 2018 v1.0.0
21

ALU-Kontroller
Die ALU bekommt einen eigenen Kontroller
Die ALU hat 4 Steuereingange, es werden aber nur sechs Kombinationen
verwendet (bzw. 5, da wir hier die nor Instruktion nicht betrachten)
Beobachtung
Instruktionen lw, sw: Instruktion beq:
Instruktionen R-Typ:
ALU-Kontroller
ALU muss addieren ALU muss subtrahieren
ALU fuhrt unterschiedliche Operationen aus, abhangig vom Feld funct
AluOp[1:0]
funct[5:0] ALU- ALUOperation[3:0] Kontroller
Vorteil: der (Haupt-)Kontroller wird dadurch vereinfacht
RA.4 2018 v1.0.0
22

Spezifikation
X bedeutet dont care (siehe Digitaltechnik, Kapitel 4.4, unvollstandig spezifizierte Funktionen)
ALU-Kontroller
opcode
AluOP[1:0]
funct[5:0]
ALUOperation[3:0]
Funktion der ALU
lw
00
XXXXXX
0010
add
sw
00
XXXXXX
0010
add
beq
01
XXXXXX
0110
sub
R-Typ
10
100000
0010
add
R-Typ
10
100010
0110
sub
R-Typ
10
100100
0000
and
R-Typ
10
100101
0001
or
R-Typ
10
101010
0111
slt
AluOP wird von Controller aus dem opcode Feldes der Instruktion berechnet
ALUOperation wird von ALU control wird mit funct Feld der Instruktion und AluOP berechnet
RA.4 2018 v1.0.0
23

Spezifikation
Der Eingang des Kontrollers ist der Opcode: Instruction[31:26]
Die zu lesenden Register rs,rt sind codiert in Instruction[25:21] und Instruction[20:16]
Das Basisregister rs fur lw und sw ist codiert in Instruction[25:21]
Der 16-bit Offset fur beq, lw und sw ist codiert in Instruction[15:0]
Das Zielregister ist
rt bei lw und codiert in Instruction[20:16]
rd bei add/sub/and/or/slti und codiert in Instruction[15:11]
es wird ein Multiplexer benotigt, um zwischen rt und rd auszuwahlen
Da es nur einen Taktschritt pro Instruktion gibt, ist der Kontroller eine rein kombinatorische Schaltung!
nachste Seite:
Datenpfad und Steuerung fur die Einzyklenimplementierung
zur Ubung: welche Erweiterungen im Datenpfad und Kontroller sind fur die Implementierung der j Instruktion notig?
RA.4 2018 v1.0.0
Kontroller-Entwurf
24

RA.4 2018 v1.0.0
25

Steuersignal RegDst
Branch
MemRead MemWrite
MemtoReg
ALUOp[1:0] ALUSrc
RegWrite
Bedeutung
0: Zielregister codiert im rt Feld 1: Zielregister codiert im rd Feld
0: PC PC+4
1: PC Sprungziel, falls Zero=1
1: Datenspeicher lesen
1: Datenspeicher schreiben (getaktet)
0: Das ALU-Resultat wird in das Zielregister geschrieben.
1: Ein Wert vom Speicher wird in das Zielregister geschrieben.
bestimmt zusammen mit funct die ALU-Operation
0: Der untere ALU-Operand kommt vom zweiten Registerfileausgang
1: Der untere ALU-Operand besteht aus den vorzeichenerweiterten unteren 16 Bit der Instruktion
1: Zielregister schreiben (getaktet)
Steuersignale
RA.4 2018 v1.0.0
26

4.3 Mehrzyklenimplementierung
Prinzip
Die Instruktionsabarbeitung wird in mehrere Schritte aufgeteilt.
Jeder Schritt benotigt einen Taktzyklus.
Je nach Instruktion sind verschieden viele Schritte notwendig.
Vorteil
Taktperiode kurzer als bei Einzyklenimplementierung hohere Performance (?)
Datenpfadelemente konnen mehrmals in einem Instruktionszyklus verwendet werden Reduktion der Hardware
Nachteil
Register zur Speicherung der Signale zwischen den Taktschritten notig
komplexerer Kontroller
RA.4 2018 v1.0.0
27

Blockschaltbild Mehrzyklenimplementierung
Unterschiede zur Einzyklenimplementierung
Es wird nur ein Speicher fur Instruktionen und Daten verwendet.
Statt einer ALU und zwei Addierern wird nur eine ALU verwendet.
Nach den grosseren Datenpfadelementen (Funktionseinheiten) werden Register eingefugt.
RA.4 2018 v1.0.0
28

Zusatzliche Register Instruction Register (IR)
Memory Data Register (MDR)
Register A, B Register ALUOut
nachste Seite:
Datenpfad und Kontroller der Mehrzyklenimplementierung (mit Erweiterung fur unbedingte Sprunge)
Mehrzyklenimplementierung
speichert die aus dem Speicher geholte Instruktion wahrend des ganzen Instruktionszyklus
benotigt ein Steuersignal
speichert die aus dem Speicher gelesenen Daten, die Daten werden im nachsten Schritt verwendet
speichern die gelesenen Registeroperanden, diese Operanden werden im nachsten Schritt verwendet
speichert das Resultat der ALU-Operation, dieses Resultat wird im nachsten Schritt verwendet
RA.4 2018 v1.0.0
29

Mehrzyklenimplementierung
30
RA.4 2018 v1.0.0

Was passiert in den einzelnen Taktschritten?
Schritt 1: Instruction Fetch IR <= Memory[PC];PC <= PC + 4; Schritt 2: Instruction Decode, Register FetchA <= Reg[IR[25:21]];B <= Reg[IR[20:16]];ALUOut <= PC + (sign-extend(IR[15:0]) << 2); In diesem Schritt wertet der Kontroller die Instruktion aus (opcode, function), dh. in diesem Schritt kann noch nichts getan werden, was fur die aktuelle Instruktion spezifisch ist, ABER: Obwohl die Instruktion noch nicht bekannt ist, werden die 2 Register rs und rt vom Registerfile gelesen und die ALU berechnet das Sprungziel. Falls dieser “Optimismus” nicht gerechtfertigt war, werden im nachsten Schritt diese Zwischenergebnisse einfach nicht verwendet. RA.4 2018 v1.0.031 Was passiert in den einzelnen Taktschritten? Schritt 3: Execution, Memory Address Computation, Branch Completion Abhangig von der Instruktion fuhrt die ALU unterschiedliche Operationen aus: Speicheradresse berechnen:Arithmetik/Logik (R-Typ): bedingter Sprung: unbedingter Sprung:ALUOut <= A + sign-extend(IR[15:0]);ALUout <= A op B;if (A=B) PC <= ALUOut;PC <= {PC[31:28], IR[25:0], “00”};RA.4 2018 v1.0.032 Was passiert in den einzelnen Taktschritten? Schritt 4: Memory Access, R-type Instruction Completion Die Datentransferinstruktionen greifen auf den Speicher zu. R-Typ Instruktionenschreiben das Ergebnis in ein Register.Speicherzugriff: MDR <= Memory[ALUout]; oderMemory[ALUOut] <= B; Arithmetik/Logik (R-Typ): Reg[IR[15:11]] <= ALUOut; Schritt 5: Memory Read Completion Reg[IR[20:16]] <= MDR; RA.4 2018 v1.0.033 Spezifikation des KontrollersZustandsnummerRA.4 2018 v1.0.0FSM=finite state machine (endlicher Automat)34 Memory-reference FSMSpezifikation des KontrollersR-type FSM RA.4 2018 v1.0.035 Spezifikation des Kontrollers Branch FSMJump FSMRA.4 2018 v1.0.036Automatengraph resultierende CPI-Werte:InstruktionCPIlw5sw4R-type4beq3j3 0137RA.4 2018 v1.0.0BeispielCPI-Wert Gegebener InstruktionsmixInstruktion(sklasse)relative Haufigkeitlw25%sw10%ALU-Instruktionen45%beq15%j5% CPI = 0,255+0,14+0,454+0,153+0,053 = 4,05 RA.4 2018 v1.0.038 Schritte des Instruktionszyklus1 2 3 4 5Instruction FetchInstruction Decode, Register FetchExecution, Memory Address Computation, Branch CompletionIFID EX Memory Access, R-type Instruction Completion MEM Memory Read Completion WBRA.4 2018 v1.0.0WB = write back39 Vergleich Ein- und Mehrzyklenimplementierung T1 T2lwswEinzyklen- implementierungT1 T2 T3 T4 T5 T6 T7 T8 T9IFIDEXMEMWBIFIDEXMEMMehrzyklen- implementierungRA.4 2018 v1.0.040 ZusatzblatterRA.4 2018 v1.0.041 v1.0.1 (2018-11-28) Folie 23 erganzt um Kommentar wie AluOP and ALUOperation berechnet werden v1.0.0 (2018-11-19) Aktualisierung fur WS 2018/19RA.4 2018 v1.0.0Anderungen 45