Alternative Rechnerarchitekuren (Teil 2)

24.11.2004 von PROF. DR. CHRISTIAN SIEMERS 
Der Architekturansatz aller aktuellen PC-Prozessoren hat viele Nachteile. Diese Artikelserie beschreibt alternative Modelle. Im zweiten Teil widmen wir uns dem >S<puter.

Die UCB-Klasse der rekonfigurierbaren Architekturen eignet sich - zumindest aus Operationssicht - gut als weiter führende Architektur für Mikroprozessoren. Dies erläutern wir anhand des (auch an der TU Clausthal entwickelten) UCB-/UCM-Konzepts. Es beinhaltet blockorientierte Strukturen (UCB: Universal Configurable Block) mit übergeordneten Maschinen (UCM: Universal Configurable Machine) zur Verwaltung der Blöcke, Scheduling et cetera.

Wir beginnen mit dem >S<puter, der aus der Variation des Instruction Scheduling der superskalaren Prozessoren stammt und aus dem schließlich auch die UCBs weiterentwickelt wurden.

Serie: Alternative Rechnerarchitekturen

Teil 1

Einführung in Reconfigurable Computing

Teil 2

>S<puter

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.

Einführung in das >S<puter-Prinzip

Bild 1 zeigt den Aufbau eines superskalaren Prozessors bei bewusster Weglassung der Floating-Point-Einheit. Die im Folgenden dargestellten Eigenschaften der ausführenden Einheit für den Integerteil des Rechners lassen sich jedoch auf die Floating-Point-Unit 1:1 übertragen.

Innerhalb des Prozessors werden das Integer Register File, die Functional Units und die Re-order-and-Commit-Unit zu einer neuen Einheit (in Bild 1 grau unterlegt), der s-Paradigmen-Unit oder abgekürzt s-Unit, zusammengefasst. Diese Architektur wird im s-Paradigmen-Modell wie in Bild 2 variiert.

Das s-Paradigmen-Modell kennt vier Klassen von Maschinenbefehlen:

Während die Befehlsklassen zur Kontrollflusssteuerung so belassen und entsprechend dem Standard in superskalaren Rechnern ausgeführt werden, nehmen die Load-/Store- und die arithmetisch/logischen Befehle eine neue Stellung ein.

Load-/Store-Befehle werden entweder mit Hilfe einer oder mehrerer Load-/Store-Pipeline(s) zum Datentransfer zwischen dem Integer Register File und dem Datenspeicher (Cache, Hauptspeicher) eingesetzt und dann auch wie bisher bearbeitet. Oder sie werden zu den arithmetisch/logischen Befehlen hinzugefügt und in das nun beschriebene Kernstück des s-Paradigmen-Modells integriert. Die Entscheidung hierüber obliegt dem System-Designer der CPU. Move-Befehle hingegen, die einen Datentransfer zwischen den Registern des Prozessors bewirken, gehören grundsätzlich zu diesem Modell.

Die arithmetisch/logischen Befehle (und die hinzugefügten Load-/Store-Befehle) werden ihrer Programmiersequenz zufolge in eine Struktur von aufeinander folgenden Hardware-Verknüpfungen übersetzt. Zu diesem Zweck bietet die Func-tional Unit im >S<puter eine programmierbare Struktur und fest verdrahtete arithmetisch/logische Verknüpfungen (sowie gegebenenfalls Zugriffsfunktionen wie Load-/Store-Pipelines). Diese lassen sich durch die Struktur miteinander verknüpfen und werden in der Reihenfolge der Strukturierung bearbeitet. Bild 3 erläutert diese Funktionalität.

Teileinheiten der Functional Unit I

Die Teileinheiten der Functional Unit und das Register File (Bild 3) sind durch eine Vielzahl von Datenverbindungen und Multiplexern verbunden.

Die Datenverbindungen sind dabei als Busse mit der jeweiligen internen Datenbusbreite ausgeführt (zum Beispiel mit 32 Bit). Eine Ausnahme bilden die Condition Codes, die als Bitleitungen implementiert sind. Innerhalb der Functional Unit existieren fünf Typen von Teileinheiten:

Die Verbindungen zwischen den Teileinheiten können komplett oder teilweise ausgeführt sein, abhängig von der Anzahl der zur Verfügung stehenden Konfigurationsbits in der Gesamtheit. In einer Beispielarchitektur auf den nächsten Seiten wird eine vollständige Verbindbarkeit gezeigt und die Zahl der notwendigen Bits daraus berechnet.

Teileinheiten der Functional Unit II

Der Sinn der strukturierbaren Functional Unit, der s-Paradigmen-Unit, liegt nun darin, die Struktur entsprechend den Maschinenbefehlen in einem (Basis-, Super- oder Hyper-)Block eines Programms anzupassen.

Die Programmierung erfolgt im s-Paradigmenmodell durch das Laden von Konfigurationsbits für die Teileinheiten. Diese werden im Programmable Structure Buffer zwischengespeichert und bei Bearbeitung des Blocks in die s-Unit geladen. Die Einheit ist dadurch entsprechend strukturiert und kann den Block bearbeiten. Die Bearbeitung bezieht sich dabei lediglich auf die arithmetischen und logischen Verknüpfungen zwischen Registerinhalten, gegebenenfalls auch mit Speicherinhalten (falls eine entsprechende Load-/Store-Pipeline zur Verfügung steht). Alle anderen Kommandos, insbesondere Load/Store und Kontrollflussbefehle laufen wie bisher üblich ab.

Die Generierung der Konfigurationsbits kann im Assembler erfolgen (Compile-time-basierte Generierung). Es ist auch prinzipiell möglich, sie in der CPU zur Laufzeit erzeugen zu lassen (Runtime-basierte Generierung), etwa durch einen funktionell erweiterten Programmable Structure Buffer.

Beispiel für die Realisierung eines >S<puters

Die Struktur der s-Unit mit fest verdrahteten AUs sowie CoUs und konfigurierbaren Wegen zwischen diesen Teileinheiten legt zunächst fest, dass die Multiplexer das programmierbare Element sind. Die feste Verdrahtung insbesondere der AUs hält die Anzahl der zu ladenden Bits gering. In einer weiteren Stufe der Flexibilisierung könnten auch die AUs programmierbar sein. Auf einfachen Strukturen wie NAND-Gattern oder disjunktiven Normalformen (DNF) aufbauend wäre eine nahezu beliebige Funktionalität bereits in einer AU integrierbar.

Arithmetic Units beinhalten beispielsweise folgende Funktionalitäten:

Die Basis für die Programmierung der Struktur, also der beiden Multiplexer-Typen, besteht in RAM-Zellen. Damit ist eine sehr schnelle Konfigurierung gewährleistet, während andere Technologien wie EEPROM längere Zeit benötigen und eher für den Einsatz von programmierbaren AUs denkbar wären. Mit n Bit lassen sich 2n Wege schalten. Für einen Mul_C bei 32 Eingängen wären somit 2 x 5 Bit und für einen Mul_D fünf Bit zur Konfigurierung notwendig.

Register der Modellarchitektur

In der Modellarchitektur implementieren wir folgende Teileinheiten und Register:

Dies ergibt 32 zu verbindende Teile innerhalb der s-Unit. Bei vollständiger Verbindbarkeit wären die Multiplexer mit fünf beziehungsweise 2 x 5 Bit zu konfigurieren. Zur Verbindung aller Einheiten benötigen wir zehn Multiplexer Typ C, 12 vom Typ D und sechs Demultiplexer vom Typ E. Die Konditionierung durch Vergleichsoperationen soll sich dabei nur auf AUs beziehen. Daher benötigen die Demultiplexer nur 3 Bit zur Konfiguration. Damit ergibt sich eine Gesamtzahl der Konfigurationsbits (für Multiplexer und konfigurierbare AUs) von 200. Diese Zahl soll lediglich die Komplexität der Konfiguration zeigen. Für die Zahl der real benötigten AUs und CoUs sind umfangreiche Simulationen notwendig. Dem Modell fehlt außerdem eine Behandlung von Flags, die durch gesonderte AUs mit Auswerteeigenschaften möglich wäre. Um einen Überlauf bei arithmetischen Operationen zu verhindern/erkennen, sind ausreichend dimensionierte Datenbusse und Auswerteeinheiten notwendig, die wir aus Übersichtsgründen weglassen.

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, so dass die entsprechende Befehlssatzerweiterung an dieser Stelle erfolgt. Für den Maschinenbefehlssatz des >S<puters werden zusätzlich folgende Befehle angenommen:

PEQ <Dest>, <Source>, <Zielbit> (Gleichheit)

PNE <Dest>, <Source>, <Zielbit> (Ungleichheit)

PGE <Dest>, <Source>, <Zielbit> (größer oder gleich: <Dest> >= <Source>)

PGT <Dest>, <Source>, <Zielbit> (größer als)

PLE <Dest>, <Source>, <Zielbit> (kleiner oder gleich)

PLT <Dest>, <Source>, <Zielbit> (kleiner als)

Eine Erweiterung dieses Befehlssatzes 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 des-halb 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 <Prediction_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):

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, so dass 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, so dass 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:

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.

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 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 prinzipiell 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.

Ausblick

Das >S<puter-Prinzip - die Aufsplittung der ALU in atomare Operationseinheiten und die Konfiguration von Datenpfaden - lässt sich natürlich auch auf eine RISC-CPU anwenden. Das soll Thema des nächsten Artikelteils sein.

Serie: Alternative Rechnerarchitekturen

Teil 1

Einführung in Reconfigurable Computing

Teil 2

>S<puter

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] Wen-Mei W. Hwu et. al.: Compiler Technology for Future Microprocessors. Invited Paper in Proceedings of the IEEE, Special Issue on Microprocessors, Vol. 83 (12), p. 1625 .. 1640, 1995.