7 Pipelining - TUM · 2015-07-08 · 7.1 Pipelining-Datenpfad 319 Durchsatz des Datenpfads (Anzahl der Befehle, die pro Zeiteinheit abgearbeitet werden können) kann bei einer n stuﬁgen

317

7 Pipelining

Nachfolgende Abbildung zeigt die bekannte Datenpfad-Schaltung.

Befehls-Speicher

Adresse

Daten

Allzweck-Registerblock

Z

Y

X

$X

8

8

8 64

64$Z

$Y

$X6464

ALU

15…0 16

048

0

1

Add

BZ64 64

4

327…0

15…8

23…16

0

10

5664

Steuerung

31…24

8

Daten-Speicher

Adresse

Daten-Eingang

Daten-Ausgang

0

1clk

Zugriffs-Art

Der Befehlsablauf ist wie folgt: Durch Takten des Befehlszählers BZ wird die Befehl-

sadresse um die Befehlswortbreite in Byte erhöht, so dass das als nächstes auszu-

führende Befehlswort am Befehlsspeicher ausgegeben wird. Durch das Befehlswort

bestimmt sich, welche Allzweckregister adressiert werden, welche Operation an der

ALU eingestellt wird, welche Zugriffsart am Datenspeicher ausgewählt wird, wie die

Multiplexer angesteuert werden und wann/ob Allzweck-Registerblock oder Speicher

getaktet werden.

Wenn der durch den Befehlszähler adressierte Befehl abgearbeitet ist, wird der Befehls-

zähler erneut getaktet und der nächste Befehl wird ausgeführt.

Durch diese Vorgehensweise wird der gesamte Datenpfad vom gerade ausgeführten

Befehl immer komplett belegt. Obwohl also z.B. bei einem Additions-Befehl die Addition

bereits durchgeführt wurde und nur noch das Ergebnis in den Registerblock geschrieben

werden muss, ist die ALU blockiert und kann von keinem anderen Befehl verwendet

werden. Damit werden die im Datenpfad verbauten Komponenten nicht optimal genutzt.

Um die Komponenten des Datenpfads besser auszunutzen, können die einzelnen

Komponenten (oder auch Teile davon) durch Register separiert und die Komponenten

dann unabhängig von einander verwendet werden. Dieses Vorgehen wird Pipelining

genannt, die Trennungs-Register dementsprechend Pipelining-Register.

318 7 Pipelining

7.1 Pipelining-DatenpfadNachfolgende Abbildung zeigt einen Pipelining-Datenpfad.

Befehls-Speicher

32 Lesen $ZLesen $Y

Schreiben/Lesen $X

Schreib-Daten $X

Lese-Daten $Z

Lese-Daten $Y

Registerblock

0..7

8..15Daten

ALU64

BZ64

Adresse

Add64

4

64

Schreiben

640

1

24..31

32

64BR

64

64

0

1

2

64

64

64

ES

ALU-Funktion

64

Daten-Speicher

Adr.

Lese-Daten $X

64 Schreib-Daten

SP

AFDirektoperand

ES

SP ES

2Zugriffs-Art

Zugriffs-Art

Lese-Daten

Ergebnisauswahl

16..23

Reg.-Schreiben

8 8

8

8

Sp.-Schreiben

Schrei-ben

0

1

32

64

Steuerung

8

8Clk1

Clk2Clk3

Clk4

Reg.-Puls

Sp.-Puls

X-Au

swah

l

16..23 $X

$Y

$Z

DirOp.

X X X

ErgALU

$X

ErgALU

LeseDat.

648

056

Befehlsspeicher, Allzweck-Registerblock (Operanden bereitstellen), ALU, Datenspeicher

und der Übergang ALU/Datenspeicher ! Allzweck-Registerblock (Ergebnis/Lesewort in

Register ablegen) sind durch sog. Pipelining-Register voneinander getrennt. Gleichzeitig

teilen die Pipelining-Register den Datenpfad in Stufen, auch Phasen genannt, ein. Bei

dem gezeigten Datenpfad sind es fünf Stufen/Phasen:

• Befehl holen (BH; Befehls-Speicher),

• Befehl dekodieren und Operanden bereitstellen (BD; Allzweck-Registerblock

und Steuerung),

• Befehl ausführen (AF; ALU),

• Speicherzugriff (SP; Datenspeicher) und

• Ergebnis schreiben (ES; Allzweck-Registerblock).

Durch dieses Vorgehen können die von den einzelnen Komponenten bereitgestellten

Datenworte sofort in den Pipelining-Registern zwischengepuffert werden. Damit werden

die Komponenten frei und können sofort von nachfolgenden Befehlen genutzt werden.

Dadruch verringert sich zwar nicht die Auführungszeit der einzelnen Befehle. Der Befehls-

7.1 Pipelining-Datenpfad 319

Durchsatz des Datenpfads (Anzahl der Befehle, die pro Zeiteinheit abgearbeitet werden

können) kann bei einer n stufigen Pipeline jedoch bis um den Faktor n gesteigert werden.

Ein Pipeline-Füll-Diagramm zeigt für verschiedene Zeitpunkte t

i

an, welche Befehle sich

gerade in welcher Pipeline-Stufe befinden. Gegeben ist folgende MMIX-Befehlssequenz:

ADD $1,$2,3SUB $2,$2,$3MUL $3,$3,5DIV $4,$4,4LDW $5,$254,0LDO $6,$254,8OR $7,$7,#ACAND $8,$8,#DCNEG $9,0,5

a) Tragen Sie in das nachfolgende Pipeline-Füll-Diagramm die Zuordnung Befehl $Pipelinestufe für die angegebenen Zeitpunkte 1, 2, ... , 9 ein.

BH BD AF SP ES BH BD AF SP

BH BD AF SP ES BH BD AF

BH BD AF SP ES BH BD

BH BD AF SP ES BH

BH BD AF SP ES

t [clk]1 2 3 4 5 6 7 8 9

320 7 Pipelining

Sobald die Pipeline gefüllt ist, wird mit jedem Takt ein Befehl abgearbeitet.

b) Ab welchem Zeitpunkt ist die Pipeline gefüllt?

c) Bis zu welchem Faktor kann der gezeigten Pipelining-Datenpfad Programme

schneller ausführen als der zuvor kennengelernte Datenpfad, der kein Pipelining

unterstützt?

d) Welche Anforderung muss man an die einzelnen Stufen eines Pipelining-

Datenpfads stellen, damit man die Komponenten des Datenpfads bestmöglichst

ausnutzt und den maximalen Performance-Gewinn erzielen kann?

Nehmen Sie folgende Registerbelegung an: $1 = 0x11, $2 = 0x22, $3 = 0x33, $4 = 0x44.

e) Tragen Sie in die angegebenen Pipeline-Register diejenigen Werte ein, die sich bei

Ausführung der unter den Pipeline-Registern abgebildeten Befehle ergeben.

Reg. Schr.:

Erg. Ausw.:

Sp. Schr.:

Zugr.-Art:

ALU:

Dir. Op.:

$X:

Dir. Op.:

$Y:

$Z:

X:

Reg. Schr.:

Erg. Ausw.:

Sp. Schr.:

Zugr.-Art:

$X:

Erg. ALU:

X:

Reg. Schr.:

Erg. Ausw.:

Lese-Daten:

X:

Erg. ALU:

SR $4,$2,2 ADD $1,$2,3 SUB $3,$3,1

STT $1,$254,0

STT $1,$254,0

0x21

SUB $3,$3,1 ADD $1,$2,3 SR $4,$2,2 STT $1,$254,0

Befehlssequenz:

7.2 Pipelining-Konflikte 321

7.2 Pipelining-KonflikteDurch die gleichzeitige Ausführung mehrerer Befehle können verschiedene Konflikte

(engl. hazards) auftreten.

Datenkonflikte

Benötigt ein Befehl ein Datenwort, das von einem vorausgehenden Befehl berechnet,

jedoch noch nicht in den Allzweck-Registerblock abgespeichert wurde, spricht man von

einem Datenkonflikt. Beispiel:

ADD $1,$2,$3MUL $3,$2,$1

Der Additionsbefehl liest in der BD-Phase Register 2 und 3 aus dem Registerblock aus

und berechnet in der AF-Phase das Ergebnis. Gleichzeitig adressiert der Multiplikati-

onsbefehl in der BD-Phase den Registerblock und liest die Register 2 und 1 aus. Der in

Register 1 gespeicherte Wert ist jedoch veraltet – er enthält noch nicht das Ergebnis des

Additionsbefehls. Dieses wäre erst nach Abschluss der ES-Phase des Additions-Befehls

verfügbar.

Erkennen von Datenkonflikten

Gegeben ist der nachfolgend abgebildete Ausschnitt aus einer MMIX-Codesequenz.

LDT $3,$2,32 Zeile 1SUB $2,$4,8 Zeile 2OR $1,$2,$3 Zeile 3STO $2,$254,$1 Zeile 4

a) Geben Sie alle auftretenden Datenkonflikte an. Nehmen Sie dabei an, dass der

Registerblock ein Datenwort, das gerade in ihn hineingeschrieben wird, nicht

gleichzeitig am Ausgang ausgeben kann.

322 7 Pipelining

Gegeben ist der folgende Ausschnitt aus einer MMIX Codesequenz:

SUB $2,$5,10 Zeile 1LDO $5,$0,2*8 Zeile 2OR $1,$2,$3 Zeile 3SRU $1,$5,$1 Zeile 4

b) Geben Sie alle auftretenden Datenkonflikte an. Nehmen Sie dabei an, dass der


gleichzeitig am Ausgang ausgegeben werden kann.

Gegeben ist der folgende Ausschnitt aus einer MMIX Codesequenz:

ADD $1,$3,1 Zeile 1OR $2,$1,$3 Zeile 2SRU $1,$2,$1 Zeile 3STO $1,$254,0 Zeile 4

T c) Geben Sie alle auftretenden Datenkonflikte an. Nehmen Sie dabei an, dass der


gleichzeitig am Ausgang ausgegeben werden kann.


Auflösen von Datenkonflikten durch Einfügen von NOP-Befehlen

Um in obigem Beispiel sicherzustellen, dass der Multiplikations-Befehl den vom

Additions-Befehl geänderten Wert verwendet, können zwischen Additions-Befehl und

dem Multiplikations-Befehl sog. NOP-Befehle eingefügt werden. NOP steht für ‘‘no

operation’’ und meint Befehle, die ‘‘nichts tun’’, d.h. keine Zustandsänderung (Änderung

von Werten in Registern, Speicher) bewirken. Beim MMIX wird der NOP-Befehl SWYM

(‘‘sympathize with your machinery’’) genannt.

a) GebenSie an,mit Siemit SWYM-Befehlen zwischen ADD $1,$2,$3 und MUL $3,$2,$1dafür sorgen, dass der Multiplikations-Befehl den vom Additions-Befehl geänder-

ten Wert aus dem Registerblock ausliest.

Befehls-Speicher

32 Lesen $ZLesen $Y

Schreiben/Lesen $X

Schreib-Daten $X

Lese-Daten $Z

Lese-Daten $Y

Registerblock

0..7

8..15Daten

ALU64

BZ64

Adresse

Add64

4

64

Schreiben

640

1

24..31

32

64BR

64

64

0

1

2

64

64

64

ES

ALU-Funktion

64

Daten-Speicher

Adr.

Lese-Daten $X

64 Schreib-Daten

SP

AFDirektoperand

ES

SP ES

2Zugriffs-Art

Zugriffs-Art

Lese-Daten

Ergebnisauswahl

16..23

Reg.-Schreiben

8 8

8

8

Sp.-Schreiben

Schrei-ben

0

1

32

64

Steuerung

8

8Clk1

Clk2Clk3

Clk4

Reg.-Puls

Sp.-Puls

X-Au

swah

l

16..23 $X

$Y

$Z

DirOp.

X X X

ErgALU

$X

ErgALU

LeseDat.

648

056

324 7 Pipelining

T b) Geben Sie an, wie Sie mit SWYM-Befehlen zwischen LDB $1,$254,0 und MUL$3,$2,$1 dafür sorgen, dass der Multiplikations-Befehl den vom Lade-Befehl

geänderten Wert aus dem Registerblock ausliest.

Auflösen von Datenkonflikten mittels Befehlsumstellung

Datenkonflikte mit NOP-Befehle aufzulösen funktioniert zwar, verringert jedoch bei

Datenabhängigkeiten den durch Pipelining effektiv erreichbaren Befehls-Durchsatz.

Unter Umständen können jedoch zwischen der Änderung eines Werts und der nächsten

Verwendung des geänderten Werts Befehle eingefügt werden, die ohnehin ausgeführt

werden müssen und unabhängig vom geänderten Wert sind.

Betrachten Sie nachfolgende Befehlssequenz.

ADD $1,$2,$3SWYMSWYMSWYMMUL $3,$2,$1SUB $4,$5,1SRU $5,$5,2SL $6,$3,2

a) Geben Sie an, wie Sie den Code durch Befehlsumstellung schneller ausführbar

machen können.


Gegeben ist die nachfolgend angegebene Befehlssequenz.

ADD $1,$2,$3SWYMSWYMSWYMMUL $2,$5,$1SUB $4,$3,1SRU $5,$6,2

T b) Geben Sie an, wie Sie den angegebenen Code durch Befehlsumstellung schnel-

ler ausführbar machen können als durch ausschließliches Einfügen von NOP-

Befehlen.

326 7 Pipelining

Auflösen von Datenkonflikten durch ‘‘Stalls’’

Werden Datenkonflikte nicht bereits durch Befehlsumstellung und Einfügen von NOP-

Befehlen vermieden, können Prozessoren Datenkonflikte auch selbst erkennen und

entsprechende Pipeline-Stufen so lange anhalten, bis der Konflikt aufgelöst ist. Um bei

angehaltenen Pipeline-Stufen denselben Befehl nicht mehrfach auszuführen, werden

sog. ‘‘Stalls’’ eingefügt. Dazu werden die Steuer-Einträge der ‘‘angehaltenen’’ Stufen so

modifiziert, dass keine Schreibzugriffe auf Register oder Speicher erfolgen. Durch das

teilweise Anhalten von Pipelinestufen verringert sich der Befehlsdurchsatz.

Auflösen von Datenkonflikten durch Forwarding-Pfade

Forwarding-Pfade sind zusätzliche Leitungen, über welche noch nicht in den Regis-

terblock geschriebene Ergebnisse an andere Pipelining-Stufen weitergeleitet werden

können.

a) Erweitern Sie nachfolgenden Datenpfad-Ausschnitt um Forwarding-Pfade, mit de-

nen Sie sowohl Ergebnisse der ALU als auch aus dem Datenspeicher ausgelesene

Werte am Z-Eingang der ALU bereitstellen können.

Befehls-Speicher

32 Lesen $ZLesen $Y

Schreiben/Lesen $X

Schreib-Daten $X

Lese-Daten $Z

Lese-Daten $Y

Registerblock

0..78..15

Daten

ALU64

BZ64

Adresse

Add64

4

64

Schreiben

640

1

24..31

32

64BR

64

64

0

1

2

64

64

64

ES

ALU-Funktion

64

Daten-Speicher

Adr.

Lese-Daten $X

64 Schreib-Daten

SP

AFDirektoperand

ES

SP ES

2Zugriffs-Art

Zugriffs-Art

Lese-Daten

Ergebnisauswahl

16..23

Reg.-Schreiben

8 8

8

8

Sp.-Schreiben

Schrei-ben

0

1

32

64

Steuerung

8

8Clk1

Clk2Clk3

Clk4

Reg.-Puls

Sp.-Puls

X-Au

swah

l

16..23 $X

$Y

$Z

DirOp.

X X X

ErgALU

$X

ErgALU

LeseDat.

648

056


Betrachten Sie folgende Befehle:

ADD $1,$2,$3SUB $3,$2,$1

b) Kann der SUB-Befehl durch Forwarding-Pfade so auf den vom ADD-Befehl be-

rechneten Wert zugreifen, dass in der AF-Phase der SUB-Befehl direkt nach dem

ADD-Befehl bearbeitet werden kann?

Betrachten Sie folgende Befehle:

LDO $1,$254,0SUB $3,$2,$1

c) Was ist hier anders?

d) Was für Konsequenzen ergeben sich daraus?

328 7 Pipelining

Nehmen Sie folgende Register-Belegung an: $1 = 0x01, $2 = 0x22, $3 = 0x03, $254

= 0x2000000000000000. Nehmen Sie desweiteren an, dass im Speicher an der OCTA-

Adresse 0x2000000000000000 der Wert 0x0123456789ABCDEF steht.

e) Tragen Sie in nachfolgende Abbildung den Inhalt der Pipeline-Register für die unter

den Pipeline-Registern angegebenen Befehle ein. Geben Sie für alle irrelevanten

Einträge ‘‘X’’ an. Nehmen Sie an, dass zwischen dem Ausgang des Datenspeichers

und dem Eingang des nach der BD-Phase angeordneten Pipeline-Registers ein

Forwarding-Pfad geschaltet ist.

Reg. Schr.:

Erg. Ausw.:

Sp. Schr.:

Zugr.-Art:

ALU:

Dir. Op.:

$X:

Dir. Op.:

$Y:

$Z:

X:

Reg. Schr.:

Erg. Ausw.:

Sp. Schr.:

Zugr.-Art:

$X:

Erg. ALU:

X:

Reg. Schr.:

Erg. Ausw.:

Lese-Daten:

X:

Erg. ALU:

ADD $1,$3,2 Stall LDT $3,$254,$1

STT $1,$254,0

STT $1,$254,0

0x21


Nehmen Sie die folgenden Registerwerte an: $1 = 0x11, $2 = 0x22, $3 = 0x33, $254 =

0x2000000000000000

T f) Tragen Sie in nachfolgende Abbildung den Inhalt der Pipeline-Register für die unter

den Pipeline-Registern angegebenen Befehle ein. Geben Sie für alle irrelevanten

Einträge ‘‘X’’ an. Nehmen Sie an, dass von der ALU-benötigte und noch nicht in

den Registerblock geschriebene Ergebnisse über Forwarding-Pfade an das der

BD-Phase folgende Pipeline-Register geleitet werden.

Reg. Schr.:

Erg. Ausw.:

Sp. Schr.:

Zugr.-Art:

ALU:

Dir. Op.:

$X:

Dir. Op.:

$Y:

$Z:

X:

Reg. Schr.:

Erg. Ausw.:

Sp. Schr.:

Zugr.-Art:

$X:

Erg. ALU:

X:

Reg. Schr.:

Erg. Ausw.:

Lese-Daten:

X:

Erg. ALU:

0x05

SUB $1,$3,$2ADD $3,$254,0 OR $2,$2,36 AND $3,$2,28

1

1

0

X

1

1

0

X

1

1

ADD $3,$254,0

330 7 Pipelining

Strukturkonflikte

Benötigen zwei Befehle gleichzeitig eine Hardware-Resource, spricht man von einem

Strukturkonflikt. Ein Beispiel für einen Strukturkonflikt beim MMIX ist die gleichzeitige

Verwendung des Adresseingangs X des Allzweck-Registerblocks:

• Ein Register-Register-Befehl befindet sich in der ES-Phase und will sein Er-

gebnis in das Register X schreiben. Dazu muss er den Registerblock über den

Adress-Eingang X adressieren.

• Gleichzeitig befindet sich ein Speicherbefehl in der BD-Phase und will ebenfalls

den Adress-Eingang X verwenden, um Register X aus dem Registerblock

auszulesen und dann im Speicher abzulegen.

Verwendet der Speicherbefehl ein X-Register, dessen Wert über einen Forwarding-Pfad

erreicht werden kann, kann der Strukturkonflikt dadurch aufgelöst werden.

Anderenfalls muss der Speicherbefehl zurückgestellt werden, d.h. es muss ein Stall

eingefügt werden.

Gegeben ist der nachfolgend abgebildete Ausschnitt aus einer MMIX-Codesequenz.


a) Wo tritt ein Strukturkonflikt auf? Wie kann dieser behoben werden?


Gegeben ist die folgende Codesequenz:


b) Tragen Sie in nachfolgendes Pipeline-Füll-Diagramm die ausgeführten Befehle

sowie die benötigten Forwarding-Pfade ein, wenn sie den Strukturkonflikt mit

einem Forwarding-Pfad auflösen.

BH BD AF SP ES

BH BD AF SP ES

BH BD AF SP ES

BH BD AF SP ES

T c) Tragen Sie in nachfolgende Tabelle ein, wie Sie den Strukturkonflikt mit einem Stall

auflösen können.

LDT

SUB

OR

STO

1 2 3 4 5 6 7 8 9 10

332 7 Pipelining

Steuerungskonflikte

Befinden Sie im Programmcode bedingte Sprünge, dann entscheidet sich erst in der

AF-Phase des Sprungbefehls, ob zum Sprungziel verzweigt wird, oder ob der auf

den aktuellen Befehl folgende Befehl als nächstes ausgeführt werden soll. Es ist also

möglich, dass in der BH-Phase Befehle in den Datenpfad geladen werden, die gar

nicht ausgeführt werden sollen. In diesem Fall müssen die fälschlicherweise geladenen

Befehle verworfen werden und im Anschluss die richtigen Befehle geladen werden. Man

nennt dieses Vorgehen ‘‘Pipeline-Flush’’, da die Pipeline geleert wird.

Um bei bedingten Verzweigungen in der Befehlsphase mit hoher Wahrscheinlichkeit den

richtigen Befehl zu laden, unterstützt der MMIX für jeden Sprungbefehl zwei Varianten:

• Bei ‘‘normalen’’ Sprungbefehle (BZ, BN, BNN, ...) wird angenommen, dass

nicht verzweigt wird. Dementsprechend werden nach dem Sprungbefehl die

unmittelbar folgenden Befehle in die Pipeline geladen.

• Bei den P-Versionen der Sprungbefehle (PBZ, PBN, PBNN, ...) wird ange-

nommen, dass verzweigt wird (probable branch). Dementsprechend werden

nach dem Sprungbefehl die am Sprungziel stehenden Befehle in die Pipeline

geladen.


Betrachten Sie nachfolgendes Programm.

LOC #100GREG @

Main LDA base_a,ALDA base_b,BSET i,1000SET s,0BZ i,EndeLDB a,base_a,iLDB b,base_b,iMUL a,a,bADD s,s,aSUB i,i,1JMP Start

Ende STO s,STRAP 0,Halt,0

a) Geben Sie die Adressen an, die der MMIX-Prozessor in der BH-Phase adressiert,

wenn sich der BZ-Befehl in der BD- und in der AF-Phase befindet.

b) Geben Sie die Adressen an, die der MMIX-Prozessor in der BH-Phase adressiert,

wenn der BZ-Befehl durch einen PBZ-Befehl ersetzt würde und sich dieser in der

BD- bzw. in der AF-Phase befindet.

334 7 Pipelining

T c) Geben Sie MMIX-Befehle an, die den nachfolgenden C-Code implementieren.

Verwenden Sie zur Realisierung der do-while-Schleife diejenige Variante des

Sprungbefehls, der mit höherer Wahrscheinlichkeit die tatsächlich auszuführenden

Befehle in die Pipeline lädt.

C-Code: int a, b;

a = 100;b = 0;

do{

b += (a * b);a--;

} while( a >= 0);

MMIX-Code:

T d) Umwieviele Takte würde der Code langsamer ausgeführt werden, wenn die falsche

Variante des Sprungbefehls verwendet werden würde?

Documents

7 Pipelining - TUM · 2015-07-08 · 7.1 Pipelining-Datenpfad 319 Durchsatz des Datenpfads (Anzahl der Befehle, die pro Zeiteinheit abgearbeitet werden können) kann bei einer n stuﬁgen