Von Prof. Dr. Christian Siemers
Fortsetzung von ComputerPartner-Ausgabe 13/05, Seite 29
Der Befehlssatz eines >S<puters
Wie bereits bei den superskalaren CPUs demonstriert, kann man durch den Einsatz von bedingten Befehlen mit Vorhersagebits eine gute Hyperblock-Struktur erreichen. Dies lässt sich auch beim >S<puter zeigen, sodass die entsprechende Befehlssatzerweiterung an dieser Stelle erfolgt. Für den Maschinenbefehlssatz des >S<puters werden zusätzlich folgende Befehle angenommen:
PEQ <Dest>, <Source>, <Ziel bit> (Gleichheit)
PNE <Dest>, <Source>, <Zielbit> (Ungleichheit)
PGE <Dest>, <Source>, <Ziel bit> (größer oder gleich: <Dest> >=<Source>)
PGT <Dest>, <Source>, <Ziel bit> (größer als)
PLE <Dest>, <Source>, <Zielbit> (kleiner oder gleich)
PLT <Dest>, <Source>, <Zielbit> (kleiner als)
Eine Erweiterung für das Setzen von Konditionsbits ist denkbar, insbesondere die bereits angedeutete Verknüpfung dieser Bits mit früheren Werten. Daneben müssen diese Konditionsbits auswertbar sein, was durch die Einführung von bedingten Verschiebe- und arithmetisch/logischen Befehlen erfolgen kann.
Im Folgenden wird für die Modellarchitektur des >S<puters deshalb vorausgesetzt, dass alle Verschiebefehle mit einer Kondition belegbar sind (movp). Außerdem ist Bedingung, dass die arithmetisch/logischen Befehle so ausgeführt werden, dass der erste Verknüpfungsoperand durchgelassen wird, falls die Bedingung nicht erfüllt ist. Im Fall der
addp <Ziel>, <Operand_1>, <Operand_2>, <Prediction_bit>
Verknüpfung wird also der <Operand_1> in das Zielregister geladen, falls das <Predic tion_bit> gelöscht ist, ansonsten die Summe von <Operand_1> und <Operand_2>.
Weitere Methoden der Leistungssteigerung
Die weiteren Methoden zur Steigerung des Durchsatzes in >S<putern entsprechen denen für superskalare Mikroprozessoren. Dazu zählen hinsichtlich der Programmierung im Assembler beziehungsweise C (als Beispiel für eine Hochsprache):
w Nutzung der bedingten Ausführung von Befehlen zur Schaffung von größeren Blöcken ohne Kontrollflussstrukturen
w Unrolling von Schleifen bis zum Maximum der Ressourcen
w Abhängigkeitsanalyse und Beseitigung von Abhängigkeiten durch (Compile-time-) Register Renaming
Nachdem dies für eine superskalare Architektur optimiert wurde, sind die vorhandenen Blöcke erneut zu analysieren und in die strukturale Programmierung zu übersetzen. Diese Übersetzung kann zur Compile-Zeit erfolgen, wobei der Vorteil in der intensiven Analyse ohne Benutzung von Silizium im Zielsystem zu sehen ist. Die strukturale Programmierung wird dabei durch die vorhandene Abhängigkeitsanalyse und vor allem durch die Beseitigung von Abhängigkeiten erheblich unterstützt, sodass die Befehle in Datenflüsse und damit in die Struktur umsetzbar sind. Diese Struktur besitzt dann keine Zyklen oder Rückkopplungen, die für die Hardware-Strukturierung bei asynchronem Design unbrauchbar wäre.
Die Bestimmung von Ausführungszeiten
Der Performance-Gewinn ergibt sich aus der Ausnutzung zweier Vorteile gegen-über der "klassischen" Architektur eines superskalaren Mikroprozessors. Die ALU - innerhalb der bisherigen Architektur vervielfacht - wird nunmehr aufgespaltet, sodass die Einzelteile unabhängig voneinander genutzt werden können. Unter der Annahme, dass die Laufzeit innerhalb der programmierbaren Struktur so klein bleibt, dass die Ergebnisse unabhängig von dem Datenflussweg innerhalb eines Takts vorliegen, ergibt dies eine im Schnitt bessere Ausnutzung der Hardware und kürzere Ausführungszeiten.
Der zweite Vorteil ist, dass Read-after-Write-Hazards auflösbar sind. Read-after-Write bedeutet, dass auf ein Ergebnis nach dessen Berechnung zugegriffen werden muss, um den weiteren Rechenfluss aufrechtzuerhalten. Im Fall der s-Paradigmen-Unit liegt dieses Ergebnis aber vor dem Speichern vor, und es kann innerhalb der Struktur bereits mit dem richtigen Wert weiterbenutzt werden. Dies ist gleichbedeutend mit dem Gewinn eines Ausführungstakts, der in der bisherigen Variante zur Speicherung zu durchlaufen war.
Die Steuerung beziehungsweise die Bestimmung der Ausführungszeit innerhalb der s-Unit nimmt jedoch einen zentralen Punkt innerhalb der Hardware-Implementierung ein. Folgende Verfahren bieten sich hierzu an:
w Die struktural programmierbare Hardware wird so konzipiert und mit dem maximal zulässigen Takt abgestimmt, dass die Laufzeit innerhalb der s-Unit für jeden Fall so dimensioniert ist, dass das Ergebnis nach einem Takt in den Registern speicherbar ist.
w Die Hardware, die in jedem Fall asynchron miteinander verknüpft ist (eine Synchronisierung erfolgt in jedem Fall erst bei den Registern, weshalb auch eine Abhängigkeitsbeseitigung erforderlich ist), liefert beim Durchlauf ein Ready-Signal mit, das die Übernahme in die Register steuert. Diese Form lässt gegebenenfalls höhere Taktraten zu. Dabei ist zum Beispiel im Regelfall ein Takt zum Durchlauf notwendig, in Ausnahmefällen zwei Takte.
Auf den folgenden Seiten gilt es, zwei Beispielprogramme zu analysieren, zu übersetzen und für eine superskalare Architektur bisheriger Implementierung zu optimieren. Die Geschwindigkeiten im Ablauf dieser Maschinenprogramme werden vergleichend zum >S<puter dargestellt.
Programme für die >S<puter-Architektur
Das erste Beispielprogramm aus [1] ist eine bedingte Zuweisung an eine einfache Variable. Bild 5 zeigt den Sourcecode und die Assembler-Übersetzung (mit p-Befehlen), Bild 6 die Umsetzung in die programmierbare Struktur.
Die Übersetzung erfolgt durch Zuordnung eines Vergleichers, konfiguriert für "größer als", und eines dynamischen Multiplexers. Letzterer übernimmt die Auswahl aus den beiden einfließenden Datenströmen anhand des Vergleichsbits zu diesem Ausführungsblock. Die Load-/Store-Befehle verbleiben in der bisherigen Form und sind nicht dargestellt. Zusätzlich ist das Register C0 (für Konstanten) mit dem Vergleichswert zu laden - hier "0".
Während für die Bearbeitung obiger Zuweisung in einer superskalaren CPU sechs Takte notwendig sind (zwei für die Load-Zugriffe, einer für die Bestimmung von p1, einer für die bedingte Zuweisung, zwei für Store), reduziert sich dies im >S<puter bei Annahme der Taktunabhängigkeit der Ausführung auf fünf Takte: Zuweisung an p1 und bedingte Zuweisung laufen asynchron hintereinander ab, der Takt synchronisiert dies bei Schreibzugriff auf r2.
Bild 7 zeigt den C-Sourcecode des zweiten Beispiels, ebenfalls aus [1]. Das kleine Programm besteht aus einer Zuweisungsschleife an ein Array b[] in Abhängigkeit eines Arrays a[], wobei hier besonders die Read-after-Write-Abhängigkeiten zu analysieren sind. Das Interessante an diesem Code ist die Reihenfolge der Adressen, auf die jeweils zugegriffen wird, da die Zuweisung in einem Teil der Schleife b[i] + b[i+1] erfolgt. Das zweite Element des ersten Zugriffs ist gleich dem ersten Element der zweiten Schleife.
1. Optimierung
Die Übersetzung des C-Sourcecodes mit einem optimierenden Compiler für traditionelle Architekturen ergibt das Assembler-Listing in Bild 8 (Seite 32).Der Kontrollflussgraph in Bild 9 zeigt die Wege, auf denen dieser Code durchlaufen wird. Der Compiler selbst hat den Assembler-Code so optimiert, dass einige Basisblöcke entstehen (in Bild 8 durch Linien getrennt).
Die aufeinander folgenden Instruktionen 1 und 2 bedeuten, dass ein Read-after-Write-Hazard vorliegt: r1 wird beschrieben und kann erst danach zum Vergleich mit 0 gelesen werden. Die Abhängigkeit verhindert eine parallele Ausführung. Die Spalte für den aktuellen Zyklus bezieht sich auf eine superskalare Architektur, die prinzipiell parallele Aktionen durchführen kann. Die Berechnung einer Schleife dauert im Maximalfall sechs Zyklen (zwei Zyklen für einen Datentransfer zum Hauptspeicher angenommen), so dass für den then-Part bei neun durchlaufenen Instruktionen 1,5 Instruktionen/Zyklus ausgeführt werden.
2. Optimierung
Durch eine 1:1-Kopie des Blocks L4 für den else-Part, eine Veränderung der Reihenfolge der Anweisungen und den Ersatz der bedingten Verzweigung durch die bedingte Ausführung der Speicherbefehle lässt sich eine Vergrößerung des Basisblocks erreichen. Das zugehörige Assembler-Listing (Bild 10) zeigt die Beschleunigung einer Schleife auf vier Zyklen (bei Annahme, dass die letzte Verzweigung richtig vorhergesagt wird).
Der Durchsatz pro Schleife vergrößert sich damit für superskalare Architekturen auf zwei Instruktionen/Takt. Wenn die s-Paradigmen-Unit ein beliebiges Schaltnetz in einem Takt bearbeiten kann, dann benötigt die >S<puter-Implementierung für alle Berechnungen einschließlich der bedingten Wertzuweisung einen Takt.
Der Durchlauf pro Schleife verkürzt sich hierdurch auf drei Taktzyklen, der Durchsatz beträgt somit 2,66 Instruktionen/Takt. Bild 11 zeigt die Struktur in der s-Unit. Die Load-/Store-Befehle, die der Kommunikation mit dem externen Speicher dienen, müssen ebenfalls eine arithmetische Berechnung für die effektive Adresse vornehmen. Sie sind hier nicht eingezeichnet, obwohl auch Addierer aus der s-Unit für die Adressenaddition nutzbar wären.
3. Optimierung
Die letzte Stufe der hier gezeigten Optimierungen behandelt die Verbesserung der Performance durch ein Zusammenfassen zweier Schleifendurchläufe zu einem (Loop Unrolling) mit nachfolgender Abhängigkeitsanalyse und -behebung.
Diese Optimierung steigert den Durchsatz, falls eine unabhängige, parallele Bearbeitung beider Teilschleifen möglich ist. Daher verwendet diese Methode zur Beseitigung von Abhängigkeiten ein Compiletime Register Renaming. Bild 12 zeigt das Ergebnis nach der Optimierung [1]. Durch die parallele Bearbeitung zweier Schleifen sinkt die Bearbeitungszeit auf durchschnittlich zwei Takte pro (ehemaliger) einfacher Schleife, wobei als Parallelisierungsmaß nunmehr 3,75 Instruktionen/Takt ausgeführt werden. Dies gilt für die superskalare Architektur, während der >S<puter in unserem konkreten Modell eine weitere Steigerung hervorbringt.
Abgesehen von den Adressberechnungen werden vier Additionen in einer Doppelschleife und zwei bedingte Zuweisungen gefordert. Diese Ressourcen sind im Modell vorhanden, das seinerseits mit Additionskapazitäten speziell für Schleifendurchführungen ausgestattet wurde. Damit lässt sich der gesamte Block der Additionen und Wertzuweisungen in einem Takt ausführen, wiederum unter der Annahme, dass das Schaltnetz dies stabil während des Takts durchlaufen lässt. Die durchschnittliche Bearbeitungszeit pro einfacher Schleife liegt dann bei drei Takten, dies ergibt eine Rate von fünf Instruktionen/Takt.
Das >S<puter-Prinzip - die Aufsplittung der ALU in atomare Operationseinheiten und die Konfiguration von Datenpfaden - lässt sich auch auf eine RISC-CPU anwenden. Dies wurde in [1] als Reconfigurable-RISC-Architektur (rRISC) publiziert.
Das Grundmodell, basierend auf der Modell-CPU MPM3, wird durch einen Fetch Look-aside Buffer ergänzt. Dieser Speicher arbeitet im Phasen-Pipelining parallel zur Decode-/Load-Unit, falls es sich um das Schreiben von übersetzten Informationen handelt. Lesend wird dieser Speicher parallel zum Fetch im Hauptspeicher (beziehungsweise Cache) genutzt.
Basisarchitektur rRISC
Die Wahl des RISC-Grundmo-dells als vierstufige Pipeline ist grundsätzlich keine Beschrän-kung. Wie noch zu zeigen ist, geht nicht die Anzahl der Pipeline-Stufen in die Gewinn-/Verlust-rechnung zur CPI-Bestimmung ein, sondern die Anzahl der verlorenen Takte bei Fehlvorhersage (und spekulativer Ausführung). Bedingt durch diesen Umstand kann die vergleichsweise einfache Architektur zur Darstellung aller Effekte genutzt werden.
Die angestrebte Instruktions-parallelität selbst lässt sich nur durch parallel ausführende Teil-einheiten erreichen. Zu diesem Zweck klassifizieren wir zunächst alle Instruktionen in folgender Weise :
1. Load-/Store-Befehle: Hierzu zählen neben den Befehlen Load und Store auch Push- und Pop-Instruktionen, die einen Zugriff auf den Stack ermöglichen.
2. Move-Befehle: Alle Kopier- (Move) und Austausch-Instruk-tionen (Xchg) zwischen Regis-tern des Prozessors sind hier zusammengefasst.
3. Befehle zur Integer-Arith- metik.
4. Logische Befehle: In dieser Klasse sind alle logischen Opera-tionen einschließlich der Shift- und Rotationsoperationen zusammengefasst.
5. Foating-Point-Operationen (entfallen in diesem Fall).
6. Kontrollflussbefehle: Bedingte und unbedingte Sprungbefehle bilden - unabhängig von der Sprungzieladressie-rung - eine weitere Klasse von Befehlen.
7. NOP (No Operation): Die NOP-Instruktion wird gegebenenfalls zur programmtechnischen Verzögerung genutzt. Sie dient allerdings gelegentlich auch als Fülloperation, die im Pro-grammspeicher selbst als Platz-halter fungiert, ohne irgendeine Funktion zu haben.
8. Weitere Kontrollflussbefehle: Je nach Mikroprozessortyp können weitere Befehle wie STOP und WAIT existieren, die direkten Einfluss auf Ausführungsmodi haben. Sämtliche weiteren Ins-truktionen sind in der letzten Klasse zusammengefasst. Weitere Kommandos, die die Flags beeinflussen (zum Beispiel SEC, Set Carry) und darüber den Kon-trollfluss steuern können, zählen in diesen Bereich.
Bei einer angestrebten Parallelisierung der Befehlsaus-führung bietet es sich im einfachsten Fall an, mehreren Instruk-tionen aus disjunkten Klassen einen Ausführungs-Slot anzu- bieten. Bei der hier gewählten Architektur ist die Klasse 5 leer. Als erster Ansatz zur parallelen Ausführung werden sämtliche Befehle der Klasse 1 zur Klasse M (Memory Access), alle Befehle der Klassen 2, 3 und 4 zur Klasse I (interne Befehlsausführung) und alle Kontrollflussbefehle der Klasse 6 zur Klasse C (Kontroll-fluss, Control Flow) gezählt. Je ein Befehl der Klassen M, I und C können parallel zur Ausführung kommen und werden in einer Struktur im FLAB gespeichert. Diese Version heißt rRISC Level 1.
Die Befehlsklasse 7 ist eine Besonderheit. Kommt ein NOP-Befehl als Platzhalter zum Ein-satz, kann seine Ausführung gänzlich entfallen. In diesem Fall bedeutet die Integration des NOP in einer Befehlszusammenfassung nur, dass ein Befehlszähler um eine Einheit inkrementiert werden muss, andere Informationen sind nicht notwendig. Befehle der Klasse 8 bleiben bei der Aus- wertung paralleler Instruktionen aktuell unberücksichtigt.
rRISC Level 2 und 3
Neben dem Basisansatz, Instruk-tionen aus verschiedenen Klassen zu kombinieren, gibt es auch innerhalb der Befehlsklassen Pa-rallelisierungsmöglichkeiten: Zum einen lassen sich vor allem bei den arithmetisch/logischen Befehlen Operationen identifizieren, die in disjunkten ALU-Bereichen ablaufen. Zum anderen können sehr preiswerte Funk- tionen wie Move (Kopie eines Registers in ein anderes) vervielfacht werden.
Zu diesem Zweck sind die Instruktionen weiter zu unterteilen: Die Subklasse MC (Move/ Copy) enthält alle Befehle, die Daten zwischen Registern verschieben oder kopieren. Die arithmetischen und logischen Operationen werden weiterhin in die Subklassen A (arithmetisch), L (logisch) und DI (Dekrement/ Inkrement) unterteilt, so dass die Klasse I nunmehr durch die Sub-klassen A, L, DI und MC darstellbar ist. Tabelle 1 zeigt, wie sich die verschiedenen rRISC-Level durch ihre Parallelitäten unterscheiden.
Der maximale Parallelitätsgrad ist noch zu erläutern. Die erstgenannte Zahl in der Klammer (siehe Tabelle 1, Spalte Parallelitäts-grad bei Level 3:9) entsteht durch die Summe über die Anzahl der Instruktionsklassen mit der Anzahl der Instruktio-nen pro Klasse, jeweils ohne Berück-sichtigung der NOPs. Die zweite Zahl in der Klammer (bei Level 3:13) wird dadurch festgelegt, dass die MC-Subklasse pro Instruktion jeweils ein MOV/MOVH-Paar mit unmittelbarer Adressierung (pro Befehl nur 8 Bit Daten, zusammen 16 Bit) enthalten kann.
Der Fetch Look-aside Buffer (FLAB) ist auf zweifache Weise mit der Fetch-Einheit gekoppelt. Jede aus dem Speicher geladene Instruktion wird an den FLAB übermittelt und im algorithmischen Teil in eine temporäre Zeile integriert. Bei Beginn eines Fetch im Speicher erfolgt eine Überprüfung, ob eine Zeile mit der entsprechenden Startadresse gespeichert ist. Bei einem FLAB-Hit können der Speicherzugriff abgebrochen und sämtliche Zeilenin-formationen an die Fetch-Einheit übertragen werden.
Im Fetch Look-aside Buffer selbst sind die Informationen gespeichert, die durch eine Form des Code Morphing aus den sequenziellen Befehlen gewonnen werden. Hierzu ist eine Gruppe von Befehlen zwecks späterer paralleler Ausführung in der in Bild 3 gezeigten Form gespeichert.
Die Fortsetzung dieses Artikels finden Sie kommende Woche in der ComputerPartner-Ausgabe 15/05.