2 Prozessorstruktur / Funktionseinheiten 2.1 Registerfilesusers.etech.haw-hamburg.de/users/Schwarz/En/Lecture/WP/Notes/Cha… · RISC DSP 2-1 university of applied ... • Somit können

Prof. Dr. J. Reichardt Prof. Dr. B. Schwarz

RISC DSP 2-1

university of applied sciences hamburg DEPARTEMENT OF ELECTRICAL ENGINEERING

AND COMPUTER SCIENCE

2 Prozessorstruktur / Funktionseinheiten 2.1 Registerfiles

• Ein großer Teil von HLL-Operationen besteht aus Variablenzuweisungen und Operanden-zugriffen.

• Die meisten Zugriffe betreffen lokale Variablen. Ø Schnelle Operandenverfügbarkeit mit einem großen Registersatz. Ø Die am häufigsten benötigten Variablen sind in Registern vorzuhalten, um die Anzahl der

Speicher-Register-Operatonen zu minimieren.

• Software-Lösung: Der Compiler muss von den benötigten Variablen so viele wie möglich, ent-sprechend ihrer Lebensdauer, der begrenzten Zahl von Registern zuordnen: Register Sharing. Die Zahl der im externen Speicher gehaltenen Variablen ist zu minimieren.

• Hardware-Lösung: Überlappende Register-Fenster zur Parameterübergabe bei Funktionsaufru-fen, damit keine Register-Speicher-Operationen erforderlich sind. Beispielimplementierungen: SPARC Architektur von Sun; Intanium Prozessor von Intel und HP mit EPIC Technologie (explicitly parallel instruction computing).

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com

http://www.fineprint.com


RISC DSP 2-2


AND COMPUTER SCIENCE 2.1.1 Register-Fenster zur Parameterübergabe zwischen Funktionen

• Lokale Variablen der einzelnen Funktionen und die globalen Variablen sind den Registern zu-zuordnen.

• Problem: Jede Funktion hat einen anderen Satz von lokalen Variablen. Ø Bei jedem Funktionsaufruf müssen Variablen in den Speicher transferiert werden, damit die

Register vom aufgerufenen Programm genutzt werden können. Ø Es sind Parameter an die aufgerufene Funktion zu übergeben. Ø Bei einer Rückkehr in die aufrufende Funktion sind Ergebnisse zu übertragen und die ur-

sprünglichen Registerinhalte aus dem Speicher zurück zu holen. • Die Lösung basiert auf Untersuchungsergebnissen nach denen: Ø Typische Funktionen mit wenigen Parametern und lokalen Variablen auskommen. Ø Die Schachtelung von sequentiellen Funktionsaufrufen nur in einem verhältnismäßig schma-

len Band stattfindet.

• Register-Gruppierung Ø Kleine Gruppen von Registern werden gebildet und den einzelnen Funktionen zugeordnet. Ø Funktionsaufrufe steuern die Auswahl der Register-Gruppe. Ø Die Rückkehr zur aufrufenden Funktion schaltet das vorherige Register-Fenster ein.




RISC DSP 2-3



Bild 2-1: Überlappende Register-Fenster zweier Funktionen.

• Drei Bereiche in einem Register-Fenster: Ø Parameter-Register Ø Register für lokale Variablen Ø Temporäre Register

• Die temporären Register eines Fensters überlappen mit den Parameter-Registern des nächsten. Physikalisch gesehen sind es die selben Flipflops.

• Parameterübergaben zwischen benachbarten Funktionen finden somit ohne Datentransfers statt.




RISC DSP 2-4



Bild 2-2: Überlappende Register-Fenster in einem Ringpuffer mit 6 Gruppen [2].

• Da nur eine endliche Zahl von Regis-ter-Fenstern bereitgestellt werden kann, wird ein in sich geschlossener Ringpuffer mit N Fenstern gebildet, der die letzten N-1 Funktionsaktivie-rungen enthält.

• Ältere Funktionsaufrufe müssen mit

ihrem Register-Fenster im externen Speicher gesichert werden. Diese Re-gisterinhalte werden restauriert, wenn die Schachtelungstiefe zurück-genommen wird.

• Die Register A.out und B.in überlap-

pen und sind die selben Register.




RISC DSP 2-5



Funktionsübersicht des Ringpuffers • Tritt ein Funktionsaufruf auf, so wird ein Fenster-Zeiger (current window pointer – CWP) be-

wegt, um das aktuelle Register-Fenster zu kennzeichnen. • Wenn alle Fenster in Gebrauch sind, wird ein Interrupt erzeugt und das älteste Fenster in den

Speicher transferiert. • Ein weiterer Fenster-Zeiger (saved window pointer – SWP) gibt den Anfang des Register-

Fensters an, in das ein gespeichertes Fenster zurück transferiert werden soll.

Erläuterungen zu Bild 2-2: • Der Ringpuffer ist bis zur Tiefe 4 gefüllt. Der CWP zeigt auf das Fenster der aktiven Funktion

D. Der SWP zeigt auf das Fenster, das als erstes gespeichert werden müsste. • Falls Funktion D die Funktion E aufruft, wird das temporäre Register von als Parametersatz

vom Parameter-Register der Funktion E genutzt und der CWP wird um eine Fensterbreite in-krementiert.

• Ein Aufruf von F durch E kann nicht ohne Weiteres erfolgen, da das temporäre Register von F mit dem Fenster von A überlappt, dass die Ursprungsdaten der Schachtelung enthält. Ø Nimmt der CWP den Wert des SWP an, so wird ein Interrupt erzeugt, der A.in und A.loc im

Speicher sichert. Danach kann der Funktionsaufruf von F ausgeführt werden.




RISC DSP 2-6


AND COMPUTER SCIENCE 2.1.2 Register-Sharing optimiert durch den Compiler

• Im Fall von Registerfiles mit 16 bis 32 Registern übernimmt der Compiler die Zuordnung von Variablen zu den verfügbaren Registern.

• Der Compiler hat das Ziel, Variablen für so viel wie mögliche Operationen in lokalen Registern vorzuhalten, damit Speicherzugriffe vermieden werden.

Grobe Vorgehensweise:

• Jeder Variablen wird ein symbolisches Register zugewiesen. • Die (unbegrenzten) symbolischen Register werden den realen Registern zugeordnet, sofern sie

sich in ihrem zeitlichen Gebrauch nicht überlappen. • Wenn alle realen Register mit Variablen belegt sind, werden die übrigen Variablen im Speicher

abgelegt.

Entwurfsverfahren: Graph Coloring • Ein Graph mit Knoten und Kanten wird gebildet, wobei die Knoten den symbolischen Registern

(Variablen) entsprechen. • Zwei symbolische Register, die im Programmablauf zur gleichen Zeit genutzt werden, sind

durch eine Kante zu verbinden.




RISC DSP 2-7



• Jedem Knoten wird eine Farbe zugeordnet, wobei benachbarte Knoten unterschiedlich gekenn-zeichnet sind.

• Die Anzahl der verfügbaren n Farben entspricht der Anzahl der realen Register. • Die Knoten, die nicht mit einer Farbe gekennzeichnet werden können, repräsentieren eine Vari-

able, die im Speicher abgelegt wird.

Bild 2-3: Register-Sharing – Graph Coloring [2]. (G. De Micheli: Synthesis and Optimization of Digital Circuits. McGraw-Hill 1994)




RISC DSP 2-8



2.2 Phasenpipelining

• Der Bearbeitungsablauf von Maschinenbefehle wird in Ausführungsphasen unterteilt. Die aus-führende Hardware besteht jeweils aus Schaltnetzen, die zum einen die Datenmanipulation durchführen und zum anderen die Steuersignale für den Datenpfad erzeugen.

• Der wesentlicher Schritt des Phasenpipelinings besteht darin, diese Schaltnetze durch Trennre-

gister zu separieren, um die Signalpfade der kombinatorischen Logik zu verkürzen. Die einzel-nen Logikstufen können damit gleichzeitig in einer Taktperiode, d.h.parallel, ihre durch Regis-ter bereitgestellten Eingangssignale verarbeiten und mit der nächsten Taktflanke an die nächste Registerstufe weiterreichen.

• Somit können von dieser Hardwarekette in den einzelnen Pipeline-Stufen unabhängig voneinan-

der Ausführungsphasen von unterschiedlichen Befehlen bearbeitet werden.

Ø Pipeline: Neue Befehle werden also am Eingang aufgenommen, währenddessen spätere Aus-führungsphasen vorher geholter Befehle am Ausgang die Ergebnisse präsentieren.




RISC DSP 2-9



2.2.1 Vereinfachte Pipeline der MIPS-Technologie

• Als Beispiel für die einführende Übersicht wird die 5-stufige Pipeline der 32-Bit MIPS-Computer gewählt, die auf die Entwicklungen der Stanford-Gruppe zurückgehen [2, 3] (vgl. Bild 2-4). Das zugrunde liegende Befehlssatzformat ist in Bild 1-2 dargestellt.

Pipeline-Stufen (vgl. Hardware-Elemente in Bild 1-3):

• Instruction fetch cycle (IF)

Der Programmzähler (PC) adressiert den externen Speicher und der nächste Befehl wird in das Instruktionsregister (IR) transferiert. Der PC wird um 4 inkrementiert (die Befehle sind 4 Byte lang) oder die Verzweigungszieladresse wird übernommen.

• Instruction decode/register fetch cycle (ID/RF) Dekodierung des Befehls und Lesen der Register entsprechend der Quellregister-Kennungen (rt, rs). Ggf. Vorzeichenerweiterung des Immediate-Feldes für Adressberechnungen oder die ALU-Operationen mit unmittelbar verfügbaren Operanden. Die Dekodierung findet parallel zum Le-sen des Registerfiles statt, da die Registerkennungen aus festen Feldern des Befehlsformates ent-nommen werden können.




RISC DSP 2-10



Bild 2-4: Hardware-Struktur der Pipeline mit Trennregistern zwischen den Stufen [3].

ADD

PC Instruc-

tionMemory

IF/ID MEM/WB

ALU

EX/MEMID/EX

RegisterFile

Sign-extens. 3216

IR[rs]

IR[rt]

Zero?

Branchtaken

DataMemory

1

0

4

MUX1

MUX2

MUX3

Data

IR[rt] or IR[rd]

Address

ALUout

StoreData

LoadData

1

0

1

0

0

1

MUX0




RISC DSP 2-11



• Execution/effective address cycle (EX): Die ALU arbeitet mit den Operanden, die über den vorherigen Zyklus bereitgestellt wurden. Ø Speicheradressierung: Die ALU addiert den Inhalt eines Basisregisters zum Inhalt des Imme-

diate-Feldes, um eine effektive Speicheradresse zu bestimmen. Ø Register-Register Operation: Entsprechend des Operationscodes werden die zwei Operanden

aus dem Registerfile verarbeitet. Ø Register-Unmittelbar: Ein Registerinhalt wird mit dem Inhalt des Immediate-Feldes ver-

knüpft. In einer Load/Store-Architektur können Adressberechnungen und ALU-Operationen in einer Stufe ausgeführt werden, da es keinen Befehl gibt, der beide schritte benötigt. Der Registervergleich für den Fall einer bedingten Verzweigung wird durchgeführt.

• Memory access (MEM):

Load: Mit der berechneten effektiven Adresse wird ein Datum aus einer Speicherzelle gelesen. Store: Ein Registerinhalt wird unter der berechneten Adresse abgespeichert.

• Write-back cycle (WB):

Speicherinhalte oder ALU-Ergebnisse werden in das Registerfile zurück geschrieben.




RISC DSP 2-12


AND COMPUTER SCIENCE Pipeline-Vorgänge:

• Obwohl jeder Befehl für seine Ausführung 5 Taktzyklen benötigt, wird mit jedem Takt eine neue Instruktion initiiert und jeweils eine Phase von 5 verschiedenen Befehlen wird abgeschlos-sen.

Bild 2-5: Parallele Ausführung von Befehlsphasen in den durch Trennregister separierten Stufen [3].

ALU

Instr.Mem

DataMem

RegFile

ALU

Instr.Mem

DataMem

RegFile Reg

File

ALU

Instr.Mem

DataMem

IF/ID

ID/EX

RegFile Reg

File

EX/

MEM

MEM/

WB

IF/ID

ID/EX

EX/

MEM

MEM/

WB

IF/ID

ID/EX

EX/

MEM

MEM/

WB




RISC DSP 2-13



• Die Hauptfunktionseinheiten der Pipeline in Bild 2-5 werden jeweils von einem anderen Befehl in aufeinander folgenden Taktzyklen benutzt: Die überlappende Ausführung von mehren Befehlen bereitet also keine Ressourcenkonflikte.

• Damit nicht zwei unterschiedliche Aktionen mit dem gleichen Abschnitt der Datenpfad-

Hardware ausgeführt werden müssen, sind spezielle Vorkehrungen zu treffen.

Ø Separate Befehls- und Datenspeicher sind vorausgesetzt worden, die z. B. mit getrennten Ca-ches implementiert werden können. Ø Das Registerfile wird in zwei Stufen genutzt: Einmal zum Lesen in ID und einmal für das Zu-

rückschreiben in WB. Zur Vermeidung eines Ressourcenkonfliktes (structural hazard) wird der Schreibvorgang in der ersten Hälfte der Taktperiode und der Lesevorgang in der zweiten Hälfte ausgeführt.

• Die Pipeline-Register haben im Prozessor eine zentrale Bedeutung: Ø Benachbarte Stufen können sich nicht direkt beeinflussen: Am Ende eines Taktzyklus werden

die Ergebnisse einer Stufe in einem Register gespeichert und deren Ausgänge bilden dann während des folgenden Taktes die Eingänge für die nächste Stufe.




RISC DSP 2-14


AND COMPUTER SCIENCE 2.2.2 Geschwindigkeitskennwerte

• Das Pipelining erhöht den Befehlsdurchsatz (throuput) der CPU: Die Anzahl der Instruktionen, die pro Zeiteinheit abgeschlossen werden. Je Tiefer die Pipeline gestaltet wird, umso größer wird der Durchsatz.

• Die Ausführungszeit eines jeden Befehls wird dagegen nicht reduziert. Die Latenz der Pipeline beträgt 5 Taktzyklen.

Bild 2-6: Relative CPU Durchsatzverbesserung mit Pipelining [2].




RISC DSP 2-15


AND COMPUTER SCIENCE 2.2.3 Pipeline-Konflikte

• Bisher wurde angenommen, dass jede sich in der Pipeline befindende Instruktion von den ande-ren unabhängig ist.

• Situationen der Pipeline-Vorgänge werden Hazards genannt, die einen nächsten Befehl in der Befehlskette bei seiner Ausführung im vorgesehenen Taktzyklus behindern:

1. Ressourcenkonflikte (structural hazards)

Diese Funktionseinschränkungen entstehen, wenn die Hardware nicht alle möglichen paralle-len Kombinationen von Befehlsausführungsphasen unterstützt.

2. Datenkonflikte (data hazards)

Wenn aufeinander folgende Instruktionen eines Programms durch die Überlappung der Aus-führungsphasen noch nicht auf Ergebnisse zugreifen können, die im Registerfile abgespei-chert sein sollten, entstehen Datenkonflikte.

3. Steuerungskonflikte (control hazards)

Der Befehlsstrom durch die Pipeline wird gestört, wenn die sequentielle Programmabarbei-tung durch Verzweigungen oder Funktionsaufrufe, die Sprünge im PC-Stand darstellen, un-terbrochen wird.




RISC DSP 2-16



1. Ressourcenkonflikte (structural hazards) • Konflikte beim Zugriff auf Elemente des Datenpfades sind durch mehrfache Realisierung zu

vermeiden, wenn keine Hardware-Einschränkungen zu befolgen sind. Im Fall der vorgestellten Load/Store-Architektur muss die ALU für Adressberechnungen und Arithmetikfunktionen nur einmal vorhanden sein, da entweder Daten gespeichert bzw. gela-den werden oder Registerinhalte verarbeitet werden.

• Solche Konflikte entstehen ebenfalls, wenn z.B. nur eine Eingangsschnittstelle für das Regis-terfile vorhanden ist und in einem Taktzyklus zwei Pipelinestufen in die Register schreiben möchten. Falls eine Folge von Befehlen diesen Konflikt erzeugt, kann die Pipeline einen der Befehle verzögern (pipeline stall) bis die Register wieder verfügbar sind.

• Sofern nur eine Speicherschnittstelle vorhanden ist, tritt ein Ressourcenkonflikt auf, falls Da-

ten abgespeichert bzw. geladen werden sollen und ein neuer Befehl der Pipeline zuzuführen ist (vgl. Tabelle 2-1). Der Konflikt wird durch eine Verzögerung des nächsten Befehls aufge-löst, die als „bubble“ durch die Pipeline wandert. Pipeline stalls mit dieser Ursache lassen sich durch geteilte Caches für Daten und Befehle oder einen Befehlspuffer vermeiden.




RISC DSP 2-17



Tabelle 2-1: Pipeline verzögert aufgrund eines Ressourcenkonflikts. Load bzw. Store kollidiert mit Instruction Fetch.

2. Datenkonflikte (data hazards)

• Die hauptsächlichen Datenkonflikte treten auf, wenn ein Befehl B auf einen Befehl A folgt

wobei B ein Register lesen will, dass von Befehl A noch nicht aktualisiert wurde (read after write hazard) (Tabelle 2-2a).

• RAW hazards können durch Umordnung der Befehlsreihenfolge (instruction reordering, pi-

peline scheduling) behoben werden (vgl. Tabelle 2-2b). Dazu muss der Compiler den ursprüng-lichen Befehlsstrom analysieren, um verschiebbare Befehle zu erkennen, sodass die

Clock cycles Instructions 1 2 3 4 5 6 7 8 9 10 Load instr. IF ID EX MEM WB R-R instr. 1 IF ID EX MEM WB R-R instr. 2 IF ID EX MEM WB Store instr. stall IF ID EX MEM WB R-R instr. 3 IF ID EX MEM WB R-R instr. 4 IF ID EX MEM R-R instr. 5 stall IF ID




RISC DSP 2-18



Ergebnisse der Programmausführung korrekt bleiben. Lassen sich keine Befehle in der sequen-tiellen Abfolge verschieben, da direkte Abhängigkeiten existieren, kann der Compiler no-operation Befehle (NOP) einfügen, um die erforderlichen Pipeline stalls SW-technisch zu er-zwingen.

Tabelle 2-2: Befehlsstrom a) mit RAW data hazard erfodert Verzögerungen. Nach Umordnung b) sind wein-ger Pipeline stalls erforderlich.

a) Clock cycles Instructions 1 2 3 4 5 6 7 8 9 10 add r1,r2,r3 IF ID EX MEM WB sub r4,r1,r5 IF ID EX MEM WB and r6,67,r8 IF ID EX MEM WB xor r9,10,r11 IF ID EX MEM

b) Clock cycles Instructions 1 2 3 4 5 6 7 8 9 10 add r1,r2,r3 IF ID EX MEM WB and r6,67,r8 IF ID EX MEM WB xor r9,10,r11 IF ID EX MEM WB sub r4,r1,r5 IF ID EX MEM WB




RISC DSP 2-19



• Eine Hardware-Lösung besteht darin, die ALU-Ergebnisse aus einem oder mehreren Pipeline-Registern zum ALU-Eingang zurückzuführen. Da hier die folgenden Befehle direkt, ohne Betei-ligung des Registerfiles, mit aktuellen Resultaten versorgt werden, wird dies auch Forwarding oder Bypassing genannt. Eine statische, lineare Pipeline wird mit diesem Direktpfad zur nichtli-nearen Pipeline.

• Wenn die Forwarding Hardware eine RAW Situation erkennt, wird das in einem Pipeline-

Register gespeicherte ALU-Ergebnis von einem Multiplexer anstelle von Registerfile-Inhalten den ALU-Eingängen zugeführt.

• Das Beispiel in Bild 2-7 zeigt, dass das Ergebnis des add Befehls erst mit der 5. Taktperiode im Registerfile vorliegt. Die sub und and Instruktionen greifen also auf falsche Registerinhalte zu. Durch Forwarding des in Pipeline-Registern vorliegenden add Ergebnisses kann die ALU den sub und den and Befehl mit aktuellen Werten bearbeiten, ohne auf die Aktualisierung des Regis-terfiles mit Pipeline stalls warten zu müssen.

• Der xor Befehl greift auf aktuelle Operanden zu, da er den Registerfile im 6. Taktzyklus nach

dem Schreibvorgang liest. Auch der or Befehl arbeitet ungestört, da die MIPS-Pipeline mit der negativen Taktflanke in den Registerfile schreibt und mit der positiven Flanke den Transfer in die angekoppelten Pipeline-Register durchführt.




RISC DSP 2-20



Bild 2-7: Auflösung von Datenkonflikten durch Forwarding von Pipeline-Registern zum ALU-Eingang [3].

InstrMem

RegFile

ALU

InstrMem

RegFile

ALU

InstrMem

DataMem

RegFile

ALU

InstrMem

DataMem

RegFile Reg

File

ALU

InstrMem

DataMem

RegFile Reg

File

add r1,r2,r3 sub r4,r1,r5 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11




RISC DSP 2-21



3. Steuerungskonflikte (control hazards)

• Störungen des Pipeline-Durchsatzes entstehen, wenn ein Verzweigungsbefehl alle nachfolgend in die Pipeline aufgenommenen Befehle ungültig werden lässt, da das Sprungziel nicht mit dem se-quentiell fortschreitenden Programmablauf übereinstimmt.

• Die Pipeline muss bis zur Entscheidungsstufe des Verzweigungsbefehls gelöscht werden (flushing

the pipeline), damit ein Neubeginn mit dem Befehl an der Sprungzieladresse erfolgen kann.

• Mit der Pipeline-Hardware nach Bild 2-4 wird bei einem bedingten Verzweigungsbefehl die Zieladresse mit dem Ende der Execute-Phase erkannt und nach einem weiteren Takt liegt erst eine neue Zieladresse am Befehlsspeicher, sodass 3 Pipeline Stalls auftreten.

T Tabelle 2-3: Bei Ausführung einer Verzweigung treten 3 Pipeline Stalls auf.

Clock cycles Instructions 1 2 3 4 5 6 7 8 9 Taken branch instruct. IF ID EX MEM WB Instruction i+1 IF ID EX idle idle Instruction i+2 IF ID idle idle idle Instruction i+3 IF idle idle idle idle Branch target IF ID EX MEM WB




RISC DSP 2-22



• Pipeline-Verzögerungen (stalls) dieser Art lassen sich vermeiden oder reduzieren, indem Kom-binationen der folgenden Maßnahmen durchgeführt werden:

a) Früherkennung (early detection), b) Frühe Bedingungsauswertung (early condition evaluation) c) Verzögerte Verzweigung (delayed branches) d) Verzweigungsvorhersage (branch prediction)

• Bei unbedingten Verzweigungen (jmp) könnte die neue Zieladresse schon während der ID-Phase bestimmt werden, sodass nur noch ein Pipeline stall auftreten würde (a)).

• Bei bedingten Verzweigungen muss zusätzliche die Bedingung ausgewertet werden. Das Hard-

ware-Beispiel in Bild 2-4 repräsentiert ein sehr späte Sprungzielerkennung, da die Adressbe-rechnung in die ALU integriert ist und die Ergebnisse hinter dem Pipeline-Register abgegriffen werden.

Ø Wird die eine separate Adressberechnung in die ID-Phase gelegt und deren Ergebnis mit der Bedingungsauswertung direkt in die IF-Stufe rückgeführt, so ergibt sich eine Verzö-gerung mit nur einem Taktzyklus (b)).




RISC DSP 2-23



Delayed Branches

• Dies ist eine Software-Methode , die auf der Beobachtung beruht, dass bis zur Ausführung der Verzweigung mehrere unnötige Befehle in die Pipeline geladen worden sind. Diese unnötigen Be-fehle, die dem Verzweigungsbefehl folgen, können als Branch Delay Slots aufgefasst werden, die mit sinnvollen Befehlen aufgefüllt werden können.

• Wenn die Befehle, die dem Verzweigungsbefehl vorausgehen, nicht mit der Verzweigung zu-

sammenhängen, dann können diese vom Compiler in die Branch Delay Slots verschoben werden. Sollange die Verzweigung bearbeitet wird, können die verschobenen Befehle durch die Pipeline gesteuert werden.

• Bild 2-8 zeigt wie Delay Slots je nach Befehlsabhängigkeit gefüllt werden können. Ø In a) wird der Delay Slot mit einem unabhängigen Befehl gefüllt, der der Verzweigung vo-

rausgeht. Ø In b) wird der Befehl des Sprungziels in den Delay Slot kopiert. Für Verzweigungen mit hoher

Wahrscheinlichkeit, wie z. B. Schleifen, wird dies bevorzugt.




RISC DSP 2-24


AND COMPUTER SCIENCE Bild 2-8: Ablaufplanung von Branch Delay Slots [3]. Der obere Rahmen zeigt jeweils die Situation vor der Ablauf-veränderung. Die Pfeile in den Rahmen zeigen die Sprungrichtung an.




RISC DSP 2-25



Bild 2-9: Auflösung von Control Hazards durch Delayed Branch bei einer 3-stufigen Pipeline [2].




RISC DSP 2-26



Branch Prediction • Zur Vorhersage einer Programmverzweigung gibt es mehrere, je nach Pipeline-Struktur auszu-

wählende Verfahren. Zu den üblichen Techniken gehören: Ø Predict never taken Ø Predict always taken Ø Branch history table

• Die ersten beiden sind statische Ansätze, da keine Abhängigkeit von der Vorgeschichte der Be-

fehlsausführungssequenz besteht. Die dritte Variante berücksichtigt die „Erfahrung“ mit vo-rausgegangenen Entscheidungen bei der Ausführung der Verzweigungsbefehle.

Predict branch never taken • Diese einfachste Technik geht von der Annahme aus, dass beim Auftreffen auf einen Verzei-

gungsbefehl die Wahrscheinlichkeit einer Verzweigung eher geringer ist. Diese Annahme beruht auf der Kenntnis, dass Schleifen mehrfach durchlaufen werden und im Fall von Einstiegsbedin-gungen der Art

for (i = 0; i <= 1000; i++) {...}

zuerst die Bearbeitung erfolgt und zum Schluss erst eine Verzweigung.




RISC DSP 2-27



• Die Pipeline-Steuerung lädt unabhängig vom Verzweigungsbefehl die nächsten sequentiellen be-fehle. Tritt dann schließlich die Verzweigung auf, werden die aus den fälschlich geladenen Befehlen abgeleiteten Steuersignale aufgehoben, damit keine unzulässigen Schreibvorgänge in das Registerfile oder den externen Speicher stattfinden.

Predict branch always taken • Für den Fall, dass es sich um fußgesteuerte Schleifen mit der Bedingung im Anschluss an den

Schleifenrumpf handelt, wie. z. B. do {...} while((a != 0) && (b != 0));

ist die Verzweigungswahrscheinlichkeit des Verzweigungsbefehls eher höher. Es sollen also nach dem Verzweigungsbefehl die Befehle bei der Sprungzieladresse geholt werden.

• Dies ist ohne Pipeline-Stalls nur dann möglich, wenn schon in der IF-Phase der Pipeline der Verzweigungsbefehl erkannt wird und die Zieladresse feststellbar ist. Da die Verzweigungsanalyse (Bedingungsauswertung, Zieladressberechnung) in tieferen Pipeli-ne-Stufen durchgeführt wird, sind zusätzlich Informationen parallel zur IF-Phase bereit zu stel-len.




RISC DSP 2-28


AND COMPUTER SCIENCE Branch history table; branch target buffer (BTB) • Der BTB ist ein kleiner Cache-Speicher, der zur Hardware der Pipeline IF-Stufe gehört. Jeder

Eintrag der History-Tabelle besteht aus drei Elementen (vgl. Bild 2-10): Ø Adresse eines Verzeigungsbefehls. Ø Zieladresse der auszuführenden Verzeigung. Ø Ein oder mehrere Zustandsbits Si, die die Vorgeschichte der Verzweigung kennzeichnen.

• Mit einem Zustandsbit S = 1 wird bezeichnet, dass die Verzweigung bei der letzten Ausführung

stattgefunden hat und in der aktuellen Situation genauso verfahren werden soll. Ist die Vorher-sage für diese Verzweigungsausführung falsch, so wird das Bit in der History-Tabelle geändert.

• Auf den BTB wird wie auf ein n-Wege assoziativ Cache zugegriffen. Jede Befehlsspeicheradres-

sierung initiiert parallel dazu einen Lookup-Vorgang im BTB.

Ø Liegt kein Treffer vor, d. h. die aktuelle Befehlsadresse ist im BTB nicht aufgefunden worden, so wird die dem Verzweigungsbefehl direkt folgende sequentielle Adresse für den nächsten Be-fehlsholvorgang gewählt. Ø Wenn ein Treffer vorliegt, d.h. die Adresse des Verzweigungsbefehles ist gespeichert, dann

wird die Vorhersage auf Basis des Zustandsbits Si durchgeführt: Die nächste sequentielle Ad-resse oder die Verzweigungszieladresse wird über den Multiplexer zum Adressbus geführt.




RISC DSP 2-29



Bild 2-10: Branch Target Buffer. Abbildung zwischen Verzweigungsbefehl und Zieladresse mit n-Bit-Sprunghistorie.

Stallings [2]




RISC DSP 2-30



• Im Laufe der weiteren Bearbeitung des Verzweigungsbefehls in den Pipelining-Stufen signali-siert die EX-Stufe dem BTB das Ergebnis zur Auswertung der Verzeigungsbedingung. Das Zu-standsbit wird entsprechend der korrekten oder falschen Vorhersage aktualisiert.

• Wenn die Vorhersage falsch war, so muss der Multiplexer die sequentielle Adresse anlegen und

mit Stalls der Pipeline ist die vollständigen Ausführung der fälschlich geladenen Befehle zu ver-hindern.

• Sofern ein Verzweigungsbefehl adressiert wird, der nicht in dem BTB enthalten ist, wird dieser

auf Basis der Bedingungsauswertung der EX-Stufe in die History-Tabelle übernommen. Ein vorhandener Eintrag wird dafür gemäß üblichen Austauschalgorithmen für Cache-Inhalte ge-löscht.

• Der BTB-Inhalt wird also im Laufe der Programmausführung mit tatsächlichen, beim letzten

mal angesprungenen Adressen aufgebaut. Da die MIPS-Struktur nur mit PC-relativen Verzwei-gungsbefehlen arbeitet, sind die aufgenommenen Zieladresseneinträge Konstanten, die aus der Adressberechnung der EX-Stufe stammen.




RISC DSP 2-31


AND COMPUTER SCIENCE Sprungvorhersage mit 2 Zustandsbits

• Mit einem Zustandsbit für die Verzweigungsvorhersage ergibt sich bei der wiederholten Schlei-fenbearbeitung ein systematisches Problem: Ø Beim Verlassen einer Schleife wird die Zieladresse falsch vorhergesagt, da vorher laufend

verzweigt wurde und zum Schluss die sequentielle Adresse benötigt wird, das Zustandsbit jedoch auf 1 steht. Ø Nach der Korrektur steht das Zustandsbit auf 0, sodass beim erneuten Einstieg in diese

Schleife am Schluss des Schleifenrumpfes ein weiteres Mal falsch vorhergesagt wird.

• Diese Fehlervorhersagen können durch einen 2-Bit Tabelleneintrag verhindert werden: Den Entscheidungen wird eine zweite Chance gegeben (vgl. Bild 2-11). Ø Die Vorhersagerichtung wird erst nach zwei falschen aufeinanderfolgenden Entschei-

dungen geändert. Ø Ein Zustandsbit (links) steht dafür, wie der Verzeigungsbefehl auszuführen ist und das

zweite Bit (rechts) gibt an, wie bei der letzten Verzweigung entschieden wurde.

• Nach einer Reihe von zutreffenden Vorhersagen (predict taken) befindet sich der Entschei-dungsautomat im Zustand 11 (z. B. nach mehreren Schleifeniterationen). Wird die Schleife ver-lassen und die EX-Stufe meldet „no branch“, so ändert sich die Vorhersage für die nächste Be-arbeitung noch nicht. Nur das Vergangenheitsbit wird auf 0 gesetzt.




RISC DSP 2-32



Bild 2-11: Zustandsdiagramm des 2-Bit Entscheidungsautomaten [8]. Bit links Vorhersage, Bit rechts Historie.

• Beim nächsten Einstieg in diese Schleife wird dann eine Verzweigung richtig vorhergesagt (branch) und der Zustand 11 (predict branch) wird angenommen.

• Nur wenn zwei aufeinanderfolgende, vorhergesagte Verzweigungen nicht ausgeführt wurden,

geht der Automat in den Zustand 00 (predict no branch) über.




RISC DSP 2-33


AND COMPUTER SCIENCE 2.2.4 RISC Pipeline Implementierung

• Die Pipeline-Register transportieren Werte (Operanden, PC-Stände und Ergebnisse) und Steuerinformationen von einer Stufe zur nächsten.

• Jede Stufe ist in jedem Taktzyklus mit dem gleichen Ausführungsschritt eines anderen Befehls

aktiviert. Die Aktionen, die im Auftrag eines Befehls durchgeführt werden finden zwischen den Pipeline-Registern statt.

• Jeder Wert, den eine spätere Stufe benötigt, wird von Register zu Register getaktet und parallel

dazu von den erforderlichen Steuerinformationen begleitet, die im Opcode- und Funktionsfeld des Befehlswortes enthalten sind.

• Die Steuersignale können in jeder Stufe aus den mitgeführten Befehlswortanteilen durch Schalt-

netze abgeleitet werden. Ø So wird z. B. die Zielregisterkennung IR[rd] für eine ALU-Operation mit zwei Registerope-

randen bis in das MEM/WB-Register getragen, damit die ALUout-Daten in das Registerfile zurück geschrieben werden können. Ø Die Zielregisterkennung IR[rt] in MEM/WB ist für ALU-Ergebnisse mit Immediate-

Operanden und für Daten von Load-Befehlen notwendig.




RISC DSP 2-34



Bild 2-12: Hardware-Implementierung mit der integrierten Steuersignalerzeugung [3, 4].

ADD

PC Instruc-

tionMemory

IF/ID MEM/WB

ALU

EX/MEMID/EX

RegisterFile

Sign-extens. 3216

IR[rs]

IR[rt]

Zero?

Branchtaken

DataMemory

1

0

4

MUX1

MUX2

MUX3

Data

IR[rt] or IR[rd]

Address

ALUout

StoreData

LoadData

1

0

1

0

0

1

MUX0




RISC DSP 2-35



• Zur Steuerung der Pipeline sind im wesentlichen die 4 Multiplexer anzusteuern und aus dem Funktionsfeld des Befehlswortes die ALU-Funktion auszuwählen.

Ø Der obere ALU-Eingangsmultiplexer MUX1 selektiert mit SEL1 =1 für Verzweigungen den

PC-Wert und ansonsten den Operanden aus dem Register mit der Kennung IR[rs]. Ø Der untere Multiplexer MUX2 liefert mit SEL2 = 0 den zweiten ALU-Operanden (IR[rt]).

Ansonsten wird aus dem Imm-Register des ID/EX-Registerstufe der Adress-Offset für Verzei-gungen oder der Immediate-Operand für arithmetische Operationen entnommen.

Ø Der Multiplexer MUX0 der IF-Stufe wählt den inkrementierten PC-Stand aus oder leitet die

Zieladressberechnung EX/MEM.ALUout eines Verzweigungsbefehls zum Laden des PC wei-ter. Die Ansteuerung erfolgt mit dem Bit EX/MEM.cond, das die Verzeigungsentscheidung darstellt.

Ø Der Multiplexer MUX3 der WB-Stufe entscheidet über das Zurückschreiben eines ALU-

Ergebnisses oder das Laden eines Datums aus dem externen Speicher.

• Im Fall von Branch-Hazards muss die Steuerung diese erkennen und Pipeline-Stalls einfügen: Dazu sind die Befehle in den IF- und ID-Stufen nicht weiter zu transportieren. Ø Die Steuersignalinhalte der ID/EX-Registerstufe könne dazu auf 0 gesetzt werden.




RISC DSP 2-36



Forwarding von ALU-Ergebnissen • Zur Auflösung von Daten-Hazards sind ALU-Ergebnisse den sequentiell folgenden Befehlen di-

rekt zur Verfügung zu stellen. Dazu sind Signalrückführungen aus den EX/MEM- und MEM/WB-Registerstufen erforderlich, die den ALU-Eingangsmultiplexern zuzuführen sind (vgl.

• Bild 2-13). • Die Forwarding-Logik besteht im wesentlichen aus Komparatoren, die die Zielregisterkennun-

gen (IR[rd] bzw. IR[rt]) in den Registerstufen EX/MEM und MEM/WB mit den Quellregister-kennungen (IR[rs] bzw. IR[rt]) der Registerstufen ID/EX und EX/MEM vergleicht.

• Diese zusätzliche Freigabelogik liefert die Steuersignale, die zur Auswahl der nun aufwendigeren

ALU-Eingangsmultiplexerpfade benötigt werden.

• Eine Auswertung der MIPS-Pipeline und des zugehörigen Befehlsatzes liefert eine Tabelle mit 10 Vergleichen, die über ein Forwarding entscheiden.




RISC DSP 2-37



Bild 2-13: Register-Feedback für das Data-Forwarding [3, 5]

ALU

ID/EX

Zero?

DataMemory

MUX1

MUX2

Address

ALUout

StoreData

EX/MEM MEM/WB

MUX3

LoadData

0

1



Documents

2 Prozessorstruktur / Funktionseinheiten 2.1 Registerfilesusers.etech.haw-hamburg.de/users/Schwarz/En/Lecture/WP/Notes/Cha… · RISC DSP 2-1 university of applied ... • Somit können