Home

Impressum

kreissl.info[rmation science]

best practices

Superskalarität

Kapitel 8 - Superskalarität

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.

VLIW

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)

VLIW

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.

Inhalt

Anfang

zurück

vor

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