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 für die verschiedenen Operationen benötigt? § Definition der Steuer- und Statussignale
– Entwurf des Kontrollers
§ Pro sequentiellem Schritt im Ablauf einen Zustand definieren
§ Für jeden Zustand: Folgezustände 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 Verzögerungszeiten zwischen zwei Registerstufen sein.
T 3max{ti} 4
RA.4 2018 v1.0.0
4.1 Elemente des Datenpfads
• Laden der Instruktion, Erhöhung 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 nächste auszuführende 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 nötig. 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 Erhöhung des PC
RA.4 2018 v1.0.0
7
Elemente des Datenpfads
• Arithmetik- und Logikinstruktionen
– Lesen von 2 Registern, Ausführen der Berechnung und Schreiben in ein Register
• Komponenten – Registerfile
– ALU
Registerfile
Eingänge:
– 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
Ausgänge:
– 2 Datenausgänge (32 Bit) für 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 für 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 a–b < 0 ? → höchstwertigste Stelle generiert ein set-Signal, das angibt, ob a
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 a–b = 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/Ausgänge
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 höherwertigen Bits
RA.4 2018 v1.0.0
14
Elemente des Datenpfads
• Komponenten
Datenspeicher
Eingänge:
– 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 ausgeführt wird oder nicht
– Berechnen der Sprungzieladresse aus Basis und Offset:
§ MIPS definiert als Basis für bedingte Sprünge 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 für bedingte Verzweigungen
RA.4 2018 v1.0.0
17
• Prinzip
– Jede Instruktion wird in einem Taktzyklus ausgeführt.
– Jede Komponente das Datenpfades kann während eines Instruktionszyklus maximal einmal verwendet werden. Daher muss es auch getrennte Speicher für Instruktionen und Daten geben.
– Damit alle Instruktionsklassen die gleichen Datenpfadelemente nutzen können, benötigt man mehrere Multiplexer.
• Vorteil
– sehr einfache Implementierung; besonders der Kontrollerentwurf ist einfach
• Nachteil
– Die Instruktionen benötigen unterschiedliche Datenpfadelemente und haben daher unterschiedliche kombinatorische Gesamtverzögerungen. Als Taktperiode T muss das Maximum aller Verzögerungen 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 für 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 Steuereingänge, 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 führt unterschiedliche Operationen aus, abhängig 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 don’t care (siehe Digitaltechnik, Kapitel 4.4, unvollständig 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 für lw und sw ist codiert in Instruction[25:21]
– Der 16-bit Offset für 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 benötigt, um zwischen rt und rd auszuwählen
– Da es nur einen Taktschritt pro Instruktion gibt, ist der Kontroller eine rein kombinatorische Schaltung!
• nächste Seite:
Datenpfad und Steuerung für die Einzyklenimplementierung
– zur Übung: welche Erweiterungen im Datenpfad und Kontroller sind für die Implementierung der j Instruktion nötig?
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 benötigt einen Taktzyklus.
– Je nach Instruktion sind verschieden viele Schritte notwendig.
• Vorteil
– Taktperiode kürzer als bei Einzyklenimplementierung → höhere Performance (?)
– Datenpfadelemente können mehrmals in einem Instruktionszyklus verwendet werden → Reduktion der Hardware
• Nachteil
– Register zur Speicherung der Signale zwischen den Taktschritten nötig
– komplexerer Kontroller
RA.4 2018 v1.0.0
27
Blockschaltbild Mehrzyklenimplementierung
• Unterschiede zur Einzyklenimplementierung
– Es wird nur ein Speicher für Instruktionen und Daten verwendet.
– Statt einer ALU und zwei Addierern wird nur eine ALU verwendet.
– Nach den grösseren Datenpfadelementen (Funktionseinheiten) werden Register eingefügt.
RA.4 2018 v1.0.0
28
• Zusätzliche Register Instruction Register (IR)
Memory Data Register (MDR)
Register A, B Register ALUOut
• nächste Seite:
Datenpfad und Kontroller der Mehrzyklenimplementierung (mit Erweiterung für unbedingte Sprünge)
Mehrzyklenimplementierung
speichert die aus dem Speicher geholte Instruktion während des ganzen Instruktionszyklus
→ benötigt ein Steuersignal
speichert die aus dem Speicher gelesenen Daten, die Daten werden im nächsten Schritt verwendet
speichern die gelesenen Registeroperanden, diese Operanden werden im nächsten Schritt verwendet
speichert das Resultat der ALU-Operation, dieses Resultat wird im nächsten 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 Fetch
A <= 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 für 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 nächsten Schritt diese Zwischenergebnisse einfach nicht verwendet.
RA.4 2018 v1.0.0
31
Was passiert in den einzelnen Taktschritten?
• Schritt 3: Execution, Memory Address Computation, Branch Completion – Abhängig von der Instruktion führt 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.0
32
Was passiert in den einzelnen Taktschritten?
• Schritt 4: Memory Access, R-type Instruction Completion
– Die Datentransferinstruktionen greifen auf den Speicher zu. R-Typ Instruktionen
schreiben das Ergebnis in ein Register.
Speicherzugriff: MDR <= Memory[ALUout]; oder
Memory[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.0
33
Spezifikation des Kontrollers
Zustandsnummer
RA.4 2018 v1.0.0
FSM=finite state machine (endlicher Automat)
34
Memory-reference FSM
Spezifikation des Kontrollers
R-type FSM
RA.4 2018 v1.0.0
35
Spezifikation des Kontrollers
Branch FSM
Jump FSM
RA.4 2018 v1.0.0
36
Automatengraph
resultierende CPI-Werte:
Instruktion
CPI
lw
5
sw
4
R-type
4
beq
3
j
3
0
1
37
RA.4 2018 v1.0.0
Beispiel
CPI-Wert
– Gegebener Instruktionsmix
Instruktion(sklasse)
relative Häufigkeit
lw
25%
sw
10%
ALU-Instruktionen
45%
beq
15%
j
5%
CPI = 0,25·5+0,1·4+0,45·4+0,15·3+0,05·3 = 4,05
RA.4 2018 v1.0.0
38
Schritte des Instruktionszyklus
1 2 3 4 5
Instruction Fetch
Instruction Decode, Register Fetch
Execution, Memory Address Computation, Branch Completion
IF
ID EX
Memory Access, R-type Instruction Completion MEM Memory Read Completion WB
RA.4 2018 v1.0.0
WB = write back
39
Vergleich Ein- und Mehrzyklenimplementierung
T1 T2
lw
sw
Einzyklen- implementierung
T1 T2 T3 T4 T5 T6 T7 T8 T9
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
Mehrzyklen- implementierung
RA.4 2018 v1.0.0
40
Zusatzblätter
RA.4 2018 v1.0.0
41
• v1.0.1 (2018-11-28)
– Folie 23 ergänzt um Kommentar wie AluOP and ALUOperation berechnet werden
• v1.0.0 (2018-11-19)
– Aktualisierung für WS 2018/19
RA.4 2018 v1.0.0
Änderungen
45