Kapitel 8 - Superskalarität
|
Inhalt
|
- Was ist Dynamic Scheduling?
- Wie funktioniert Out-Of-Order Execution?
- Was heißt Multiple-Issu?
- Wie arbeitet spekulative Befehlsausführung?
- Wie arbeiten Tomasulo und VLIW-Prozessoren?
|
Was bedeutet superskalar?
Mit normalen Pipelines (Überlappen von Instruktionen) ist nur eine maximale Performance von einem
Befehl / Takt technisch und theoretisch möglich. Um diese Grenze zu unterschreiten, ist Parallelität auf
Befehlsebene (Instruction Level Parallelism) notwendig. Dies bedeutet das der typische Risc-Prozessor, um Einiges
erweitert werden muss:
- Prozessor muss in der Lage sein, mehrere Befehle gleichzeitig pro Takt zu laden
- Branches dürfen möglichst nicht zur Behinderung des Befehlsflusses führen (deshalb Sprungvorhersage)
- Datenabhängigkeiten treten hier in erhöhtem Maße auf und müssen behandelbar sein
- um echte Datenabhängigkeiten auflösen zu können, is Out-Of-Order Ausführung mit anschließender "Sortierung" notwendig
Dynamic Scheduling
Static Scheduling nutzt lediglich Compilertechniken zur Separierung unabhängiger
Befehle und ist sehr unflexibel. Beim Dynamic Scheduling wird durch Präsenz mehrerer
paralleler Buffer und Execution Units versucht, Ressourcen- und Datenkonflikte zu eliminieren.
Out-Of-Order Execution
In-Order-Issue Pipes müssen, falls ein Befehle gestoppt wird, alle Folgebefehle
warten. Durch eine zusätzliche Hardware, welche das Umordnen der Befehlsausführung
zur Laufzeit vornimmt, kann dies verhindert werden. Möglichkeiten dafür sind
Scoreboards oder Tomasulo.
Was ist das Problem des Präzisen Zustandes?
Das Prinzip des Präzisen Zustandes besagt, daß bei Unterbrechungen (Interrupts, Exeptions) der Zustand
der CPU sicherbar und wiederherstellbar sein muss. Dieses Konzept muss auch bei superskalaren Architekturen
gelten. Dies ist in superskalaren Architekturen weitaus aufwendiger und bedarf zusätzlicher Hardware.
Welche Entwurfskriterien sind zu betrachten?
- Stategien zum holen mehrerer Instruktionen pro Takt (und Einfluss von Branches)
- Methoden zum Auffinden von Datenabhängigkeiten zwischen Registerinhalten
- Methoden zum Aussenden (Issue) mehrerer Befehle gleichzeitig
- Ressourcen zur paralellen Ausführung (mehrere Ausführungseinheiten und Zwischenbuffer)
- Ausführung mehrerer LOAD/STORE-Pipelines in enger Abstimmung mit Ausführungseinheiten
(LOAD/STORE Instruktionen müssen entkoppelt auf Grund der verschiedenen Latenzzeiten ablaufen können)
- Methoden zur Bestimmung der korrekten Ausführungsreihenfolge und Speicherfolge der Register
Superskalare Prozessoren müssen nicht die Instruktionssequentialität (siehe out-of-order-execution)einhalten,
jedoch immer die Ergebnissequentialität (siehe in-order-commit).
Superskalar-Prozessoren und VLIW-Prozessoren als Multipe-Issue CPU's
Beide Techniken senden mehr als nur einen Befehl pro Taktzyklus aus und versuchen so,
die CPI unter eins zu drücken. Moderne Prozessoren kombinieren beide Techniken.
Der größte Unterschied zwischen beiden Technologien besteht darin, daß Very Long
Instruction Word basierende Systeme für verschiedene Prozessoren neu compiliert
werden muss. Superskalare-Prozessoren sind dagegen gleich kompatibel.
Was heißt Multiple-Issu?
Ist das Mehrfach-Aussenden von Befehlen, welchen gewissen issue criteria unterliegen
müssen. Die folgende Abbildung zeigt das Superskalarprinzip - eine 5-stufige Pipeline
mit zweifacher Superskalarität.
Superskalarität mit VLIW
Der IA-64-Befehlssatz von Intel wird auf "Very Long Instruction Words" basieren. Es werden drei Instruktionen
ein einen fetten 128 Bit Befehl gepackt. Hier besteht nun die Möglichkeit, explizit festzulegen, welche Befehle
parallel abgearbeitet werden sollen bzw. können. So eröffnen sich völlig neue Optimierungsmöglichkeiten im
Compilerbau. Man nennt dieses Prinzip EPIC. Der Transmeta verwendet auch VLIW. Hier muss aber der Compiler
nicht die Optimierungen vornehmen, da der Transmeta um der Core eine Morphing Softwareebene hat, welche die
Aufteilung in parallel abarbeitbare Befehle ausführt. Dadurch, daß nun explizit gesagt wird, welche
Instruktionen parallel ausführbar sind, ist nun nicht mehr so viel Chipfläche zum Auflösen von Hazards
notwendig und kann z.B. für mehr Register verwendet werden.
Das Scoreboard
Ein Scoreboard ist eine zusätzliche Steuereinheit, welche die Verantwortung für das Befehlsaussenden und das
Erkennen von Konflikten trägt. Das Scoreboard wählt aus einem Pool potentiel ausführbarer Befehle
(Instruction Window) einen Satz von Befehlen aus. Ein Register wird als ungültig markiert, wenn die
Dekodiereinheit erkannt hat, dass ein Befehl sein Ergebnis in dieses Register schreiben möchte. So
wird verhindert, dass ein anderer Befehl dieses Register liest, solange es ungültig ist. Nachteil ist,
daß keine Ressourcen- und auch keine Datenabhängigkeiten auftreten dürfen. Eine bessere Variante ist die
Tomasulo-Methode, welche eine Auflösung von WAR- und WAW-Konflikten ermöglicht.
Zusammenfassend gesagt, besteht ein Scoreboard aus einer Vielzahl von Zählern (wie oft wurde gelesen und geschrieben) für die verwendeten Register und Funktionseinheiten. Ein Scoreboard, welches auch WAR und WAW Konflikte lösen kann, wäre zwar extrem aufwendig aber möglich.
Wann können Befehle mit der Scoreboard Technik nicht ausgesandt werden?
- Wenn ein aktueller Operand geschrieben wird (RAW)
- Wenn das Ergebnisregister gelesen wird (WAR)
- Wenn das Ergebnisregister geschrieben wird (WAW)
WAR und WAW sind weniger schwerwiegend als RAW Abhängigkeiten, da diese nur Ressourcenkonflikte darstellen. RAW Konflikte
logische Abhängigkeiten und können nicht so einfach aufgelöst werden. Mit der Scoreboard Methode muss gewartet werden, bis der
abhängige Vorgängerbefehl sein Ergebnis geschrieben hat. Erst dann kann der Folgebefehl das benötigte Datum lesen und mit der Abarbeitung
fortsetzen. Lösen lassen sich alle Probleme mit Out-Of-Order Execution und Register Renaming Technik. Dazu muss das Scoreboard
erweitert werden.
Die Tomasulo-Methode
Hauptidee sind hier sogenannte Reservation Stations, welche eine Art Zwischenpuffer für Operanden darstellen.
Die Reservation Stations besitzen eine eindeutige ID, welche jedem Befehl mitgegeben wird. So kann die richtige
Reihenfolge beibehalten werden. Wird ein Befehl ausgeführt, arbeitet dieser nicht auf den eigentlichen Registern,
sondern auf den assoziierten Reservation Stations, was das Prinzip des schon erwähnten Register Renamings ist.
Über einen Common Data Bus werden die Ergebnisse zu allen beteiligten Einheiten gebroadcaset.
Reservation Stations erkennen Hazards und können selbst entscheiden, wann sie den dazugehörigen Befehl ausführen.
Nämlich erst dann, wenn alle Operanden vorliegen.
Um controll stalls komplett vermeiden zu können, wird die Tomasulo-Methode mit der spekulativen Befehlsausführung
kombiniert.
Wie arbeitet die spekulative Befehlsausführung?
Sprungziel-Befehle werden schon ausgeführt, wenn das Ergebnis des Sprungtests noch gar nicht vorliegt. Somit
muss es die Möglichkeit geben, bei falscher Vorhersage alle Änderungen zu Verwerfen (Rollback-Fähigkeit).
Die Hauptsächliche Hardware-Erweiterung liegt in der Aufspaltung der Ergebnisschreibphase in eine
Bereitstellungsphase mit Zwischenspeicherung im Reorder Buffer und eine Phase in der ein Befehl
commited, d.h. gänzlich der Ausführung übergeben wird. Ein commit bedeutet, daß eine eventuelle
Sprungvorhersage richtig war!
Somit stellt dies eine Kombination von out-of-order-execution via Tomasulo mit einem erzwungenen
in-order-commit dar.
Der Reorder-Buffer stellt in der Welt des Tomasulo weitere Register zur Verfügung, welche auch die Funktion
von Store Buffern übernehmen könnten, so daß dieser als Teil des Tomasulo nicht direkt mehr erkennbar wäre.
(Store Buffer enthalten Informationen darüber, welche Reservation Stations, welches Ergebnis erwartet)
Aus welchen Feldern setzt sich ein Reorder-Buffer-Eintrag zusammen?
- Befehlstyp (Branch, Store oder Registeroperaton)
- Zielfeld (Registernummer oder Speicheradresse)
- Datenfeld (Ergebnis der Operation)
Die Phasen des Tomasulo
|
Fetch und Decode
|
Holt Instruktionen in einen Befehlscache.
Die Decode-Unit holt sich einen Teil der Befehle und versucht mehrere gleichzeitig
zu decodieren (In-Order).
Dabei wird versucht Sprünge vorherzusagen.
Übergibt dekodierten Befehle in der richtigen Reihenfolge an die Dispatch (Issue) Unit.
|
|
Dispatch / Issue
|
Holt dekodierte Befehle aus Befehlspuffer und übergibt sie In-Order an die Reservation Stations
der Execute Units, sobald alle Operanden verfügbar sind (Issue).
Solange im Reorder Buffer Platz ist, reserviert sie ein Feld für diesen Befehl mit
Hilfe des Tags und gibt dieses an die RS weiter. Wenn nicht wartet sie, bis ein Platz frei wird.
(Dispatch Phase)
|
|
Execution
|
Führt Befehle auf den Schattenregistern aus, um Data Hazards zu meiden.
Befehle werden in den Reorder-Buffer geschrieben und Out-Of-Order ausgeführt, solange es keine
RAW-Konflikte gibt. Nach Beenden eines Befehls wird Ergebnis an
alle RS gebroadcastet, so dass wartende Befehle fortfahren können.
(Write result)
|
|
Commit
|
Die Commit/Completion oder Retire Einheit schreibt die Ergebnisse
aus den Renaming Registern in die echten ISA Register zurück,
nachdem sie geprüft hat, ob abhängige vorangehende Befehle
ihre Ergebnisse geliefert haben und keine falsche Sprungvorhersage
eingetreten war.
|
Erklären Sie die Phasen Issue, Execute, Write Result und Commit!
Die Issue-Phase entnimmt einen Befehl aus dem Befehlsbuffer und versucht diesen an eine freie Reservation Station zu übergeben. Dabei reserviert sie einen Platz im Reorder-Buffer und gibt den dazugehörigen Tag an die Reservation Station. So kann beim Ergebnis-Broadcasting das Ergebnis mit diesem Tag gekennzeichnet werden. (1)
Sind nun alle notwendigen Operanden vorhanden und keine weiteren RAW-Abhängigkeiten bestehen, kann der Befehl
ausgeführt werden. (Execute-Phase). (2)
Ist das Ergebniss berechnet, wird es auf den CDB gelegt und in den Reorder-Buffer geschrieben (Write Result). (3)
Der Reorder-Buffer ist als Ringbuffer angelegt, bei dem die Reihenfolge der Befehle, durch die der erwarteten Ergebnisse (über das verliehene Tag) definiert wird. Nun werden in der Commit-Phase falsch vorhergesagte Sprünge zurückgesetzt und es wird bei dem richtigen Nachfolgebefehl fortgesetzt. Das Ergeniss wird in die ISA Register zurückgeschrieben. (4)
Muliple Issue am Beispiel
Instruktionen werden in eine oder mehrere Mikrooperationen dekodiert und in eine Warteschlange gestellt.
Sprungerkennung erfolgt erst statisch und dann dynamisch mit 4 History Bits (da siebenstufige Decode-Pipeline!). Dann werden Register im Reorder-Buffer (der P4 hat Platz für 40 µOps) zugewiesen. Dabei werden um Konflikte zu vermeiden Renaming-Register (Schattenregister) eingesetzt. In der Execute Phase werden Mikrooperationen aus dem Reorderbuffer entnommen und spekulativ ausgeführt.
Es wird ein komplexes Scoreboard verwendet, um aktive Operationen und Register zu
verwalten. Falls mehrere Mikrooperationen bereit sind, wählt ein Algorithmus den nächst
Wichtigsten aus (z.B. Sprünge).
Mikrooperationen deren Operanden alle verfügbar sind, werden in die Reservation Stations geschrieben,
welche 20 solcher Einträge aufnehmen kann. Dort warten die Ops, bis eine entsprechende Ausführungseinheit
frei wird.
Die Execute-Units haben fünf Ports, um Operationen auszuführen. Manche Ausführungseinheiten teilen sich
einen Port (FPU,MMX).
Die Retire (Completion) Einheit sendet fertige Ergebnisse an die richtige Stelle. Der P2 unterstützt
speculative execution. Falls begonnene Instruktionen nicht mehr benötigt werden, wird die Rollback
Fähigkeit genutzt.
Der Pentium 4 nutzt einen Trace Cache für die letzten drei dekodierten Befehle. Im Hit Falle, bedient
sich die Execution Unit direkt dieser Befehle, was vor allem bei Schleifen einen beträchtlichen Speedup bringt.
Die UlraSparc 2 ist dagegen eine reine Risc Maschine mit vierfachen statt 2facher Superskalarität.
Durch das Risc Prinzip müssen hier Instruktionen nicht in mehrere Mikrooperationen umgesetzt werden.
Desweiteren unterstützt die meist gleich große Befehlslänge das Pipelining besser, als die z.T.
komplexeren Cisc Befehle des Pentium.
Neu ist das so genannte Folding der PicoJava CPU, welche Instruktionen faltet, d.h. zusammenfasst und
gleiche Instruktionen in einem Zyklus (auf verschiedenen Registern) abarbeiten kann. ( 5 x schneller als
P2, obwohl auch CISC)
- Auflösung von RAW durch Out-Of-Order Ausführung möglich
- WAW und WAR Konflikte durch Register Renaming auflösbar
- Tomasulo liegt Idee der Reservation Stations zu Grunde
- Tomasulo wird zusammen mit Spekulativer Ausführung angewandt
- Meist vier Phasen, wie Fetch/Decode, Issue, Execute und Commit
|
|
|
Merktabelle: Superskalarität |
Wie werden Unterbrechungsanforderungen gehandhabt?
Bei Interrupts muss sichergestellt werden, daß nach Abarbeitung der Unterbrechung, die CPU wieder in einen sicheren (präzisen)
Zustand zurückkehren kann.
Das erste Verfahren benutzt Checkpoints, an denen der tatsächliche Zustand der CPU ein Update erfährt und der bisherige in einen
History-Buffer gelegt wird. Somit ist jederzeit ein präziser Zustand wiederherstellbar (Recovery), wobei
innerhalb der Commit-Phase nur der korrekte Zustand hergestellt werden muss und die nicht weiter benötigten aus dem Historybuffer
wieder entfernt werden.
Das zweite Verfahren wird dem Ersten oft bevorzugt. Es steht eng mit der Verwendung des Reorder-Buffers in Verbindung.
Dabei wird der Zustand des Rechners in zwei aufgeteilt:
- einen Physikalischen Zustand, der bei jeder ausgeführten Instruktion gesetzt wird
- und einem architekturellen Zustand, welcher erst beschrieben wird, wenn ein eventueller spekulativer Status geklärt wurde
Während der Commit-Phase, wird der spekulative Zustand in den architekturellen (und den physikalischen) übernommen, die Renaming Register
des Reorder-Buffers in die Registerfile geschrieben bzw. die Store-Operation durchgeführt.
Dabei wird der "spekulative Zustand" ebenfalls im Reorder-Buffer mitgeloggt. Erst bei
Zusammenfassung Superskalar-CPU's - dynamic scheduled pinelines
Da das Pipeline Konzept schnell an seine Grenzen gelangt ist, ist eine andere Methode notwendig. Es muss
möglich sein, dass mehrere Befehle pro Takt beendet werden können und unabhängige Befehle, welche in Pipes
wegen vorangehender Abhängigkeiten warten müssen, in der Ausführungsfolge vorzuziehen. Superskalare Prozessoren
erkennen parallel verarbeitbare Befehle von selbst und benötigen somit keine speziell optimierenden Compiler,
wie sie z.B. VLIW verlangen. Dafür sind sie weitaus komplexer. Um RAW, WAW und WAR Abhängigkeiten zu vermeiden, wird versucht Instruktionen anders anzuordnen. Dafür ist ein Scoreboard notwendig, das für jedes benutzte Register die Leseabhängigkeiten und Schreibabhängigkeiten zählt.
Der Tomasulo Algorithmus ist ein Verfahren, welches sich durchgesetzt hat, da es WAW und WAR Konflikte
dynamisch auflösen kann. Dies ist so einfach möglich weil WAW und WAR keine echten Datenabhängigkeiten sind, sondern nur entstehen, wenn ein späterer Befehl ein Register wiederverwendet, ohne die darin enthaltenen Daten zu benötigen.
Hier tritt das Register Renaming oder "Arbeiten auf Schattenregistern" in Kraft. Würde es mehr Register geben, könnten diese Abhängigkeiten schon vom Compiler aufgelöst werden.
Mit Register Renaming werden intern versteckte Register benutzt, um Abhängigkeiten aufzulösen.
Spekulative Ausführung wird benutzt um weitere Lücken im Ablauf zu füllen. Hierbei werden Sprungziel-Befehle gegebenenfalls schon ausgeführt, wenn noch gar nicht klar ist, ob dieser überhaupt wahr werden. Dies wird meist mit dynamischen Scheduling nach Tomasulo kombiniert. Falsch vorhergesagte Befehle erreichen nie die Commit-Phase und werden verworfen. Dies ist möglich, da sich die Ereignis-Schreibphase in Bypassing (Zwischenspeicherung im Reorder-Buffer) und dem Rückschreiben auf die echten ISA Register aufteilen lässt.
Wie können RAW-Konflikte gelöst werden?
RAW Konflikte sind echte Abhängigkeiten und gekönnen nicht aufgelöst werden. Es kann nur Versucht werden, durch eine
Out-Of-Order Ausführung die Ausführungseinheiten stets gefüllt zu halten, um somit negative Auswirkungen auf den
Befehlsfluss zu minimieren oder zu vermeiden.
|
|
|
|
|
| Kapitel 1 | Einleitung |
|
Befehlsschleife, Risc und Cisc...
|
| Kapitel 2 | Interrupts |
|
Interrupts, Polling, DMA...
|
| Kapitel 3 | Speicherschutz |
|
Segmentation, Paging, Mapping, Multitasking...
|
| Kapitel 4 | Caches |
|
Lokalität, Cache-Arten, Schreibstrategien...
|
| Kapitel 5 | Risc |
|
Risc-Architektur, Load/Store, Registerfenster...
|
| Kapitel 6 | Pipelining |
|
Prinzip, Datenkonflikte, Forwarding, Delayed Load
|
| Kapitel 7 | Branch Prediction |
|
Statische / Dynamische Brach-Prediction...
|
| Kapitel 8 | Superskalarität |
|
Out-Of-Order Execution, Scoreboard und Tomasulo, VLIW...
|
| Kapitel 9 | Parallelrechner |
|
SMP,Vektorrechner, Cache-Kohärenz
|
|
|
|
|
|
|
|
|
Quellen:
|
Andrew S. Tanenbaum
Computerarchitektur
|
Andrew S. Tanenbaum
Moderne Betriebssysteme
|
Petterson
Computer Architectur & Design
|
Christian Märtin
Rechnerarchitekturen
|
Rehm
Skript und Vorlesung
|
Word Wide Web
Verschiedenste Seiten
|
|
|
|
|
|
|
Home 
RISC - CISC