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, in Bild 1 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.
| |
Teil 1 | |
|---|---|
Teil 2 | |
Teil 3 | Reconfigurable RISC |
Teil 4 | UCB/UCM;-Konzept |
Teil 5 | XPP-Architektur und Xputer |
Diesen Artikel und eine ganze Reihe weiterer Grundlagenthemen zu Prozessoren finden Sie auch in unserem tecCHANNEL-Compact "Prozessor-Technologie". Die Ausgabe können Sie in unserem Online-Shop versandkostenfrei bestellen. Ausführliche Infos zum Inhalt des tecCHANNEL-Compact "Prozessor-Technologie" finden Sie hier.
Basisarchitektur rRISC
Die Wahl des RISC-Grundmodells als vierstufige Pipeline ist grundsätzlich keine Beschränkung. Wie noch zu zeigen ist, geht nicht die Anzahl der Pipeline-Stufen in die Gewinn-/Verlustrechnung 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 Instruktionsparallelität selbst lässt sich nur durch parallel ausführende Teileinheiten 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-Instruktionen (Xchg) zwischen Registern des Prozessors sind hier zusammengefasst.
3. Befehle zur Integer-Arithmetik.
4. Logische Befehle: In dieser Klasse sind alle logischen Operationen 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 Sprungzieladressierung - 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 Programmspeicher selbst als Platzhalter 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 Instruktionen sind in der letzten Klasse zusammengefasst. Weitere Kommandos, die die Flags beeinflussen (zum Beispiel SEC, Set Carry) und darüber den Kontrollfluss steuern können, zählen in diesen Bereich.
Bei einer angestrebten Parallelisierung der Befehlsausführung bietet es sich im einfachsten Fall an, mehreren Instruktionen aus disjunkten Klassen einen Ausführungs-Slot anzubieten. 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 (Kontrollfluss, 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 bezeichnet man als rRISC Level 1.
Die Befehlsklasse 7 ist eine Besonderheit. Kommt ein NOP-Befehl als Platzhalter zum Einsatz, 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 Auswertung paralleler Instruktionen aktuell unberücksichtigt.
rRISC Level 2 und 3
Neben dem Basisansatz, Instruktionen aus verschiedenen Klassen zu kombinieren, gibt es auch innerhalb der Befehlsklassen Parallelisierungsmö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 Funktionen wie Move (Kopie eines Registers in ein anderes) vervielfacht werden.
Instruktionen | Parallelitätsgrad | |
|---|---|---|
Tabelle 1: Definition der rRISC-Level für das modifizierte MPM3-Modell. | ||
Level 1 | 1 M-Klasse 1 C-Klasse 1 I-Klasse | 3 (4) |
Level 2 | 1 M-Klasse 1 C-Klasse 1 AL-Subklasse (A, DI, L) 4 MC-Subklasse | 7 (11) |
Level 3 | 1 M-Klasse 1 C-Klasse 1 A-Subklasse 1 L-Subklasse 1 DI-Subklasse 4 MC-Subklasse | 9 (13) |
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 Subklassen A, L, DI und MC darstellbar ist. Tabelle 10.2 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 10.2, Spalte Parallelitätsgrad bei Level 3:9) entsteht durch die Summe über die Anzahl der Instruktionsklassen mit der Anzahl der Instruktionen pro Klasse, jeweils ohne Berücksichtigung 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.
Aufbau und Funktionsweise des Fetch Look-aside Buffers
Der Fetch Look-aside Buffer (FLAB) ist auf zweifache Weise mit der Fetch-Einheit gekoppelt (Bild 2). 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 Zeileninformationen 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.
FLAB-Zeile
Bild 3 zeigt das Speicherformat für rRISC Level 1. Mit dem nachfolgend beschriebenen Algorithmus wird ein in den Prozessor kommender Instruktionsstrom in die entsprechenden Zeilenabschnitte gespeichert. Hierbei erfolgen im Sinn eines Code Morphing einige Umwandlungen.
Zur Speicherung der I-Instruktionen benötigt man Operationscode, Quellregister beziehungsweise unmittelbare Daten als Quellen und das Zielregister. Die unmittelbaren Daten werden entsprechend den Konventionen auf volle Breite erweitert. Bei RISC-Prozessoren mit einem Instruktionsformat, dessen Breite identisch mit der Datenbreite ist, sind die unmittelbaren Daten nicht mit der vollen Datenbreite speicherbar. Präfix-Instruktionen zur Erweiterung der Konstanten lassen sich direkt integrieren, was einer Verschmelzung der Befehle mit den Daten entspricht.
M-Instruktionen bleiben unverändert, da hier keine Zusammenfassungen möglich sind. Bei C-Instruktionen wird als Sprungziel immer die vollständige Adresse geschrieben, außerdem lassen sich alle Hinweise zur Sprungvorhersage in der FLAB-Zeile sichern. Bei der hier beschriebenen Lösung, basierend auf dem MPM3-Modell, benötigen wir pro Zeile im FLAB-Speicher 157 Bit. Zusätzlich sind für die Daten-Hazard-Informationen für nachfolgende Instruktionen (zur Erkennung von Read-after-Write-Hazards) 20 Bit erforderlich.
Übersetzungsalgorithmus für Code Morphing
Innerhalb des algorithmischen Teils des FLAB wird der ursprüngliche Code in einen Code mit Strukturinformationen umgewandelt. So sind Datenabhängigkeiten erkennbar, und eine parallele Ausführbarkeit der integrierten Operationen ist möglich. Die Umwandlung ist eine Abwandlung des Code Morphing. Den hier verwendeten Algorithmus nennt man Procedural Driven Structural Programming (PDSP), da aus den sequenziellen Instruktionen eine Strukturinformation gewonnen wird. Im Wesentlichen besteht PDSP aus den folgenden Schritten:
1. Die aktuelle Instruktion ist gemäß ihrer Klassenzugehörigkeit auf ihre Übersetzbarkeit zu prüfen. Dies führt gegebenenfalls zur Beendigung der aktuellen FLAB-Zeile. Als integrierbar sind bei rRISC alle Befehle der I-, M- und C-Klasse sowie der NOP-Befehl definiert.
2. Ist die Instruktion übersetzbar, wird geprüft, ob eine freie Ressource vorhanden ist. Eine negative Antwort führt zur Beendigung, eine positive zur vorläufigen Belegung dieser Ressource und zur Eintragung in die Strukturinformation. Ein NOP-Befehl ist als Spezialfall durch Erhöhen des Befehlszählers integriert.
3. Nach der vorläufigen Übersetzung werden die Datenabhängigkeiten überprüft. Im Allgemeinen lassen sich Datenabhängigkeiten (RAW-Hazard) in die Struktur übersetzen; im speziellen Fall der rRISC-Architektur wurde jedoch auf ein Data Forwarding innerhalb der Struktur verzichtet, so dass Datenabhängigkeiten zur Beendigung des Algorithmus führen.
4. Als Spezialfall werden MOV/MOVH-Instruktionspaare (mit unmittelbarer Adressierung) der Modellarchitektur als ein Befehl behandelt. Ein MOV #-Befehl kann die unteren 8 Bit in ein Register laden, ein MOVH #-Befehl die oberen. Ein direktes Aufeinanderfolgen mit identischem Zielregister wird als Instruktionspaar gewertet und entsprechend übersetzt.
Übersetzungsalgorithmus für Code Morphing II
Als Endkriterien für eine FLAB-Zeile sind also nicht integrierbare Instruktionen, Ressourcenbelegung und Datenabhängigkeiten definiert. Ist eine Zeile beendet und enthält sie mehr als eine Instruktion, so wird sie im Pufferbereich gespeichert. Der Ersatz von älteren FLAB-Zeilen erfolgt über einen Least-Recently-Used- (LRU-) Algorithmus, der Speicher ist im Übrigen vollassoziativ aufgebaut.
Im Phasenschema des RISC-Prozessors wird am Ende des zweiten Takts einer Befehlsbearbeitung, also parallel zum Ende der Decode-/Load-Phase, das Ergebnis der Instruktionsübersetzung im temporären Teil gespeichert. Parallel hierzu sind die Bestimmung eines Endkriteriums sowie die Auswertung des LRU-Algorithmus erledigt, so dass auch die Speicherung in einer regulären FLAB-Zeile erfolgt. Damit steht das Übersetzungsergebnis zwei Takte nach Beginn der Befehlsbearbeitung zur Nutzung im Mikroprozessor bereit. Dies bedeutet auch für den extremen Fall einer Programmschleife mit zwei Instruktionen (I-Instruktion und anschließender Branch, zum Beispiel für Wartezähler), dass diese ab der zweiten Ausführung als Struktur verfügbar ist. Jede verzweigende Branch-Instruktion benötigt bei der ersten Ausführung zwei Takte (nach Look-ahead Resolution).
Die Einträge in der FLAB-Zeile bleiben mit einer Ausnahme unverändert: Das sind die ständig aktualisierten Verzweigungsinformationen. Wir haben in unserem Beispielmodell eine dynamische Branch-Vorhersage mit einem Bit gewählt, so dass in jedem FLAB-Eintrag mit Branch-Befehl auch der letzte Verzweigungsweg aktuell gespeichert ist.
Beispiel für die Funktion des FLAB
Das folgende Beispiel dient der Verdeutlichung des Effekts, den man mit Hilfe des FLAB und der Integration von Instruktionen in eine parallel ausführbare Struktur erreichen kann. Es ist einer Patentschrift des Unternehmens Transmeta entnommen, in der es ebenfalls die Leistungsfähigkeit des Code Morphing demonstrieren soll.
Eine kurzen Programmschleife initialisiert ein Array. Bild 4 zeigt die entsprechende Assembler-Übersetzung aus Übersichtsgründen ohne Initialisierung der Register. Die ersten beiden Instruktionen lassen sich in einer FLAB-Zeile zusammenfassen, da hier keine RAW-Hazards auftreten (R4 wird erst nach dem Speichern (ST), wo es als Ziel dient, um 2 (in R5 stehend) dekrementiert). Gleiches gilt für die Kombination der beiden unteren Instruktionen, obwohl der Branch-Befehl von dem Ergebnis des Dekrementbefehls abhängt. Hier tritt eine Sprungvorhersage auf.
Bei korrekter Vorhersage (ab dem zweiten Durchlauf) wird die Assembler-Schleife bei einer RISC-Architektur in vier Takten, bei rRISC Level 1 in zwei Takten und bei rRISC Level 3 in einem Takt durchlaufen.
Programmausführung und Simulationsergebnisse
Ein kritischer Aspekt bei der Einführung der neuen Architektur ist, dass gegebenenfalls Fehlvorhersagen bei bedingten Verzweigungen zu einer erhöhten Anzahl an Takten zur Wiederherstellung des korrekten Programmzustands führen. Die Ausführung eines Branch-Befehls benötigt bei der Modell-CPU in der RISC-Variante einen Takt bei korrekter Vorhersage und zwei Takte bei Fehlprognose. In der rRISC-Variante wird die Branch-Instruktion, falls sie in einer FLAB-Zeile integriert ist, parallel zu einer anderen Instruktion ausgeführt und benötigt selbst also keinen Takt.
Die Abhängigkeit von vorangegangenen Instruktionen, die in der gleichen FLAB-Zeile sein können, bewirkt allerdings, dass zwei Takte Verlust bei Fehlvorhersage auftreten. Die Verlusttakte für FLAB-Zeile und normale Branch-Instruktion stimmen in diesem Fall überein, so dass keine erhöhte Anzahl bei Fehlvorhersage auftritt. Im Allgemeinen lässt sich eine Formel für den Fall angeben, dass keine zusätzlichen Maßnahmen wie Wartezyklen eingefügt werden müssen, um irreversible Ergebnisse zu verhindern.
Für diese Formel sei ein k-stufiges Pipelining angenommen. Am Ende der Stufe kf sei der Fetch beendet, und am Ende der Stufe kst seien die Status-Flags per Data Forwarding verfügbar, die einen Branch beeinflussen. In der Stufe kexe würden dann die irreversiblen Ergebnisse gespeichert. Um ohne Taktverlust (bei Branch-Vorhersage) rRISC einführen zu können, muss unter diesen Annahmen folgende Ungleichung gelten:
Testprogramme
Die nachfolgenden Testprogramme wurden mit Hilfe eines VHDL-Modells für die rRISC-Variante einer Modell-CPU zyklusgenau simuliert. Hierbei sind keinerlei Speichereffekte wie Cache-Konfiguration, langsamer Hauptspeicher et cetera berücksichtigt. Lediglich eine Von-Neumann-Konfiguration (ein Port zum Speicher) und eine Harvard-Konfiguration (zwei voneinander unabhängige Ports) sind in der Simulation berücksichtigt.
Die gewählte Konfiguration umfasst die Integration je einer I-, M- und C-Klasse-Instruktion in einer FLAB-Zeile. Dies entspricht rRISC-Level 1 und wurde mit einer gleichartigen RISC-Architektur mit dynamischer Branch-Vorhersage (1 Bit) verglichen (Level 0). Die Anzahl der gleichzeitig gespeicherten FLAB-Zeilen variierte dabei. Zum Test haben wir wieder die von Kapitel 4.6 bekannten Programme verwendet.
Eine Beschreibung der Testprogramme finden Sie im Artikel RISC-Pipelines im Detail. Alle Testprogramme zeigen IPC-Werte von etwa 0,8 für die RISC-Architektur. Die Steigerung mit wachsendem rRISC-Level und Anzahl der FLAB-Zeilen bleibt immer < 2 IPC, mit Ausnahme des Testprogramms zur Initialisierung eines Arrays. Das Programm Quicksort (rekursive Programmierung) bleibt bei einem IPC-Wert < 1. Dieses Programm zeigt einen so unregelmäßigen Verlauf, dass es selten zu einem zweiten Durchgang durch gespeicherte Programmbereiche kommt, so dass eine wesentliche Beschleunigung entfällt.
Die Werte für eine Harvard-Architektur mit getrennten Ports für Code und Daten liegen alle um zirka 0,12 IPC höher.
Schätzung der Flächeneffizienz
Aus den gegebenen Performance-Werten, gemessen in IPC und Schätzungen des Flächenbedarfs aus den VHDL-Beschreibungen lässt sich eine relative Flächeneffizienz für die einzelnen Varianten angeben. Dabei wird ein quantitativer Zusammenhang zwischen Ausführungszeit T und Flächenbedarf A zu Grunde gelegt:
Die Gleichung oben zeigt einen allgemeinen Zusammenhang, der zunächst für einzelne Operationen gültig ist, jedoch auch für komplette Mikroprozessorarchitekturen zum Einsatz kommt. Mit n = 2, dieser Wert wird bei arithmetischen Schaltungen meist angenommen, lässt sich die Flächeneffizienz so definieren:
Bild 6 zeigt die resultierenden Werte, bezogen auf die Grundversion des Mikroprozessors (L0). Diese erhält man durch Bestimmung der erzeugten Signale im Design als relative Zahl für A und 1/IPC als relativer Wert für T.
Ergebnisse
Bild 6 belegt für den simulierten 16-Bit-Mikroprozessor, dass die Werte für die Effizienz bei steigender Performance sinken. Die maximale Effizienz liegt beim Basismodell, und hierfür gibt es folgende Gründe:
Das 16-Bit-Mikroprozessormodell ist sehr kompakt ausgelegt, so dass die Anzahl der internen Signale klein ist. Insbesondere die Zahl der internen Register (13) und Operationen hält sich in Grenzen. Bezogen auf den kompakten Grundwert steigt der Aufwand für den FLAB-Speicher stark an.
Neben der Eigenschaft, die Zusammenfassung der Befehle zu Strukturen zu speichern, kann der Fetch Look-aside Buffer auch als Cache wirken. Dies ist allerdings in den Schätzungen nicht berücksichtigt.
Aus den Werten für das 16-Bit-Prozessormodell wurden Resultate für eine komplexere 32-Bit-Mikroprozessorarchitektur extrapoliert. Die Werte (Bild 6) zeigen dabei ein deutlich anderes Bild: Die Effizienz sinkt erst bei höheren Anzahlen von FLAB-Zeilen. Eine sinkende Flächeneffizienz bei gesteigerter Performance, ausgedrückt in IPC-Werten, ist beim Übergang von skalaren zu superskalaren Architekturen der Normalfall. Durch Einführung des FLAB-Konzepts lässt sich eine gleichzeitige Effizienz- und Performance-Steigerung für komplexere Mikroprozessoren beziehungsweise Mikro-Controller-Kerne erzielen oder zumindest der Effizienzverlust mindern.
Ausblick
Die s-Unit des >S<puter-Konzepts sowie der Übersetzungsalgorithmus PDSP lassen sich aus dem Konzept des superskalaren Mikroprozessors herauslösen und einzeln beziehungsweise in neuer Zusammensetzung benutzen. Hieraus ergibt sich eine interessante Mischung aus Programmier- und Ausführungsmodell. Das optimale Modell besteht - nach dem aktuellen Kenntnisstand - darin, dass die Programmkodierung einem sequenziellen Modell folgt, die Ausführung jedoch an die aktuellen Randbedingungen (auch zur Laufzeit) angepasst werden kann. Genau dies wird von dem UCB-/UCM-Modell ( Universal Confi gurable Block/Machine) unterstützt. Das soll Thema des nächsten Artikelteils sein.
| |
Teil 1 | |
|---|---|
Teil 2 | |
Teil 3 | Reconfigurable RISC |
Teil 4 | UCB/UCM;-Konzept |
Teil 5 | XPP-Architektur und Xputer |
Diesen Artikel und eine ganze Reihe weiterer Grundlagenthemen zu Prozessoren finden Sie auch in unserem tecCHANNEL-Compact "Prozessor-Technologie". Die Ausgabe können Sie in unserem Online-Shop versandkostenfrei bestellen. Ausführliche Infos zum Inhalt des tecCHANNEL-Compact "Prozessor-Technologie" finden Sie hier. (mec)
Literatur
[1] Sascha Wennekers, Christian Siemers, "Reconfigurable RISC - a New Approach for Space-efficient Superscalar Microprocessor Architecture" in: Proceedings of the International Conference on Architecture of Computing Systems ARCS 2002, Karlsruhe, Germany, April 2002. Springer Lecture Notes in Computer Science 2299, pp. 165-178.