Von Prof. Dr. Christian Siemers, tecChannel.de
Fortsetzung von ComputerPartner-Ausgabe 14/05, Seite 33
FLAB-Zeile
Mit einem 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 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, sodass 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 Aufeinanderfolgen mit identischem Zielregister wird als Instruktionspaar gewertet und entsprechend übersetzt.
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.
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, sodass 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.
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. 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.
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.
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.
Die Abhängigkeit von vorangegangenen Instruktionen bewirkt allerdings, dass zwei Takte Verlust bei Fehlvorhersage auftreten. Die Verlusttakte für FLAB-Zeile und normale Branch-Instruktion stimmen in diesem Fall überein, sodass 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:
kexe >= kst-kf
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 (Webcode: a1383). 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.
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:
A*Tn=Const. mit n=1…2
Die Gleichung 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:
E= 1/A1/2
Die resultierenden Werte 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.
Für den simulierten 16-Bit-Mikroprozessor sinken die Werte für die Effizienz bei steigender Performance. Die maximale Effizienz liegt beim Basismodell, und hierfür gibt es folgende Gründe:
w Das 16-Bit-Mikroprozessor-modell ist sehr kompakt ausgelegt, sodass die Anzahl der internen Signale klein ist. Besonders 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.
w 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 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.
Der vorliegende Artikel stammt von tecChannel.de, dem Webzine für technikorientierte Computer- und Kommunikationsprofis. Unter www.tecChannel.de finden Sie weitere Beiträge zu diesem Thema.