Die Entwicklung von Prozessoren in den letzten Jahren sowie die vermutete Entwicklung für die nächsten Jahre lassen sich durch folgende Zahlen gut darstellen:
1990 konnten Mainstream-Mikroprozessoren eine Instruktion pro Takt ausführen (typische RISC-Technologie).
1995 betrug diese Zahl bei Mainstream-Mikroprozessoren etwa vier Instruktionen pro Takt.
In naher Zukunft werden 16 Instruktionen pro Takt in paralleler Ausführung als Richtwert vermutet.
Der theoretische IPC (Instruction per Clock) von 16 wurde im Jahre 1995 für das Jahr 2000 vorhergesagt, trat bislang aber nicht ein. Die Gründe sind einfach: Man hat es noch nicht geschafft, diesen theoretischen Wert in eine praktisch verwertbare Rechenleistung umzusetzen. Allein der Fetch von 16 Instruktionen, der für eine 16fache Parallelität notwendig ist, erweist sich als schwierig. Zudem ist bei klassischen Befehlssätzen jeder fünfte bis sechste Befehl eine bedingte Verzweigung, so dass der Prozessor Instruktionen über viele Spekulationen laden müsste.
Dennoch: Die theoretische Performance der Prozessoren, bezogen auf den Takt, steigt weiter. Prozessoren und Compiler jedoch haben sich schon seit Längerem gegenseitig beeinflusst: Angepasste Registersätze sowie spezielle Assembler-Befehle (etwa für den Stackframe bei Funktionsaufrufen) zeigen solche Beeinflussungen. Die folgenden Abschnitte zeigen, warum es zukünftig neue Compiler-Technologien und -Strategien geben muss und welche Änderungen nötig sind. Einige Beispielprogramme in den Abschnitten runden den Überblick ab.
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.
Warum neue Technologien für Compiler?
Traditionelle Compiler-Technologien beruhen im Allgemeinen auf folgenden Optimierungsstrategien:
Der Compiler eliminiert nicht durchlaufene Codebereiche (Dead Code Elimination, minimiert die Programmgröße).
Er löscht unnötige Codebereiche, die zwar durchlaufen, aber nicht benötigt werden, da sie keinen Nettoeffekt erzeugen (beschleunigt das Programm).
Er legt Variablen, die häufig oder nur für Zwischenergebnisse benötigt werden, in (Highspeed-) Registern ab, um auf langsame Speicherzugriffe verzichten zu können (beschleunigt das Programm).
Diese Optimierungen sind weiterhin sinnvoll, da sie auch bei Instruktionsparallelismus Erfolge zeigen. Zusätzliche Optimierungen, bei denen die Parallelisierbarkeit im Vordergrund steht, sind jedoch dringend notwendig. Immerhin ist bei einem Prozessor, der die vierfache parallele Ausführung von Instruktionen ermöglicht, eine Performance-Steigerung um den gleichen Faktor theoretisch möglich. Eine Grundvoraussetzung dafür ist, dass der Compiler das Programm auch parallelisierbar übersetzt. Der mögliche Leistungsgewinn ist eine hohe Motivation für neue Compiler-Technologien, wie die folgenden Abschnitte zeigen.
Der folgende Beitrag stellt zunächst die Verfahren zur Optimierung von kompiliertem Code im Einzelnen vor. Hierunter fallen einige Basiskonzepte wie das Formen von Superblöcken zur Vergrößerung der unterbrechungsfreien Instruktionsblöcke, das Einfügen von bedingten Instruktionen mit Steuerungs-Flags, Register Renaming zur Compile-Zeit und das Loop Unrolling.
Der zweite Teil geht auf einen Hauptbestandteil der Technologien ein, die bedingten Befehle mit Steuerungs-Flags. Im dritten Teil folgt dann die Analyse von Speicherabhängigkeiten. Die in Teil zwei und drei beschriebenen neueren Technologien dürften Bestandteil der zukünftigen Compiler-Generationen sein.
Kompilierung für Instruction Level Parallelism: Basiskonzepte
Eine kurze Routine, die in Schleifenform einem Array b[] neue Werte in Abhängigkeit eines Arrays a[] zuweist, soll einige der Konzepte zeigen. Der Übersetzung in den Assembler-Code liegt ein Pseudocode zu Grunde, der nach dem Schema <OpCode> <DestReg>, <SourceReg1>, <SourceReg2> aufgebaut ist. Ferner sind den Assembler-Befehlen in der Schleife Nummern zugeteilt, um deren Position nach einer Optimierung identifizieren zu können. Für die Bestimmung der Laufzeit einer Schleife gelten folgende Regeln:
Es können prinzipiell beliebig viele Assembler-Befehle parallel zueinander zur Ausführung gelangen. Eine Out-of-Order-Execution wird aber nicht betrachtet.
Die Hardware des Prozessors löst sämtliche virtuellen Hazards wie WAW und WAR auf.
Jeder Speicherzugriff hat einen Zeitbedarf von zwei Takten, alle anderen Befehle von einem Takt.
Falsche Sprungvorhersagen und ihre nötige Korrektur treten im Beispiel nicht auf, der Prozessor durchläuft die Schleifen immer korrekt.
Das Assembler-Listing zeigt unter diesen Umständen folgende Struktur für das Beispielprogramm: Innerhalb der Schleife entstehen vier Basisblöcke, mit L1 bis L4 bezeichnet. Folgendes Bild stellt den Kontrollflussgraphen dar, wie ihn der IF- und der ELSE-Zweig durchlaufen. Pfeile verbinden im Kontrollflussgraph die Basisblöcke, wenn ein entsprechender Übergang möglich ist.
Abhängigkeiten
Die Abhängigkeit zwischen der Instruktion 1 und 2 (1 schreibt r2, 2 liest r2 zum Vergleich) bedeutet einen RAW- (Read-after-Write-) Hazard. Die Konsequenz daraus ist eine Verzögerung der Ausführung, da keine parallele Ausführung möglich ist. Folgendes Bild stellt die Abhängigkeiten zwischen den einzelnen Instruktionen als Graph dar, und zwar getrennt nach Register- und Speicherabhängigkeiten.
Compiler-Bauer bezeichnen die dargestellte Abhängigkeit zwischen den Instruktionen 1 und 2 als Flussabhängigkeit. Den WAR- (Write-after Read-) Hazard zwischen den Instruktionen 6 und 9 nennen sie Anti-Abhängigkeit.
Die so genannte Output Dependence ist in dem Beispiel nicht direkt zu entdecken, sie existiert allerdings zwischen zwei Hintereinander-Ausführungen der Schleife. Dabei wird zum Beispiel in Instruktion 4 der gleiche Inhalt in ein Register geschrieben wie in Instruktion 3 beim nächsten Schleifendurchlauf. Die CompilerBauer bezeichnen diesen Zusammenhang als Output-Abhängigkeit, exakter als schleifenbedingte Output-Abhängigkeit (Loop-Carried Output Dependence).
Die bisherige Analyse für das Beispiel zeigt einen nur sehr geringen Anteil an paralleler Ausführung auf Instruktions-Level: Der IF-Teil führt pro Schleife neun Befehle in sechs Takten aus, die Performance beträgt also 1,5 Instruktionen pro Takt. Der Grund hierfür ist, dass die Kompilation viele Basisblöcke mit jeweils nur wenigen Befehlen geliefert hat.
Superblöcke
Zwei Ansätze zur Vergrößerung dieser Basisblöcke werden im Folgenden diskutiert. Der erste Ansatz versucht, die Größe des wesentlichen Basisblocks zu erweitern. Das Zusammenfassen eines Zweiges zu einem Superblock, der innerhalb der Ausführung möglichst häufig durchlaufen wird, soll die Performance verbessern. Voraussetzung dafür ist, dass der andere Zweig eine seltene Ausnahme ist.
In dem Beispiel sei nun angenommen, dass der Prozessor den ELSE-Zweig nur selten durchläuft. Dann variiert man den Assembler-Code und den Kontrollflussgraphen so, dass man den Block L4 kopiert und aus den Blöcken L1, L2 und L4 einen Superblock (punktiert eingerahmt) erzeugt.
Die eigentliche Optimierung für den Assembler-Code besteht nun darin, dass die Ladeoperationen parallel zueinander ausgeführt werden, wodurch die CPU zwei Takte spart. Diese Ladeoperationen erfolgen für den ELSE-Teil unnötig. In diesem Beispiel führt dies aber zu keiner Verschlechterung der Geschwindigkeit, der ELSE-Zweig benötigt weiterhin drei Takte. Das Beispiel berücksichtigt jedoch gemäß den Voraussetzungen keine Verzögerungen durch falsche Sprungvorhersagen. Dies gilt im Allgemeinen jedoch nicht, teilweise erfolgt die Optimierung der Hauptschleife auf Kosten des Sonderfalls.
Das Resultat dieser Bemühungen ist eine Verbesserung der Performance auf 2,0 Instruktionen pro Takt und ein Zeitverbrauch von nur noch vier Takten pro Schleifendurchlauf. Diese als Global Acyclic Scheduling bezeichnete Beschleunigung beruht im Beispiel vor allem auf der parallelen Ausführung der Load-Befehle. Das Attribut global entstammt dabei dem Vorgehen, über die bisherigen Basisblockgrenzen hinweg Befehle zu verschieben, während die Bezeichnung azyklisch für die Begrenzung innerhalb des azyklischen Teils stammt. Die Verschiebung der Load-Befehle aus dem Bereich nach dem Branch-Befehl in den Block davor, der ja in jedem Fall eine garantierte Ausführung bewirkt, bezeichnet man als Speculative Code Motion.
Die Verschiebungen sind zulässig, wenn die Ausführung des ELSE-Teils dadurch keine falschen Resultate hervorruft. Dies muss der Compiler zusätzlich prüfen, im Beispiel führt es nicht zu Problemen. Zusammenfassend gilt, dass das Einfügen von Superblöcken den größten Gewinn erzielt, wenn ein Pfad des Codes besonders häufig durchlaufen wird. Bei mehreren Pfaden kann dieses Verfahren jedoch eher das Gegenteil bewirken, da die Optimierungen dann eventuell an falscher Stelle erfolgen.
Predication und Hyperblöcke
Für die zweite Methode zur Vergrößerung der Basisblöcke benötigt die CPU neue Assembler-Befehle, was die Wechselwirkung zwischen Compiler-Bau und CPU-Befehlssatz einmal mehr verdeutlicht. Das Kernstück des Verfahrens besteht im Ersatz der Branch-Befehle durch bedingte "normale" Befehle. Die Ausführung mit diesen Vorhersage-Flags bezeichnet man auch als Predicated Execution.
Der Compiler muss dazu einen Branch-Befehl (mit oder ohne integrierten Vergleichsbefehl) in mehrere Instruktionen zur Belegung der Aussage-Flags und zur Ausführung der bedingten Befehle umsetzen. Dieser Vorgang wird If-Conversion genannt. Die mögliche parallele Ausführung gleicht dabei den Aufwand der zusätzlichen Befehle aus.
Zudem entstehen im Beispiel dadurch nicht mehrere kleine Basisblocks, sondern lediglich noch ein einziger großer Basisblock. Einen derartigen, aus der If-Conversion entstandenen Block von Befehlen bezeichnen Compiler-Bauer als Hyperblock. Die bedingten Befehle, die sich im obigen Beispiel gegenseitig ausschließen, arbeitet die CPU parallel zueinander ab. Allerdings führt nur einer der beiden wirklich zu einem Ergebnis.
Durch den Ersatz der Branches durch bedingte Befehle sinkt die Ausführungszeit auf vier Takte bei zwei Instruktionen pro Takt. Sie unterscheidet sich somit nicht von der vorhergehenden Optimierung, muss aber keine Annahmen über den wahrscheinlichsten Weg treffen.
Kompilierung für Instruction LevelParallelism: Loop Unrolling
Die bisherigen Maßnahmen dienten der Vergrößerung der Basisblöcke durch die Eliminierung von bedingten Verzweigungen. Die entsprechenden Befehle im Sourcecode sind Einfach- oder Mehrfachverzweigungen.
Als weitere Maßnahme zur Verbesserung der Performance von superskalaren Prozessoren müssen die Compiler die Schleifen optimieren. Da der Prozessor den Code einer Schleife meist sehr oft durchläuft, liefert hier eine Optimierung einen entscheidenden Performance-Gewinn für das gesamte Programm.
Den Branch-Befehl am Ende einer Schleife, den Rückwärtssprung, kann man kaum vermeiden. Es sei denn, der Compiler setzt die Schleife auf Kosten der Codelänge in linearen Code um. Diesen kann die CPU dann - unter Berücksichtigung von Datenabhängigkeiten - parallel ausführen.
Das Verfahren des Loop Unrolling, wie es in der Praxis angewendet wird, betrachtet eine kleine Anzahl von Schleifendurchläufen. So versucht es zwei bis vier Durchläufe zusammenzulegen und eventuelle Datenabhängigkeiten zu beseitigen. Die geringe Anzahl hat durchaus Gründe: So ist oft zur Compile-Zeit nicht entscheidbar, wie viele Schleifen tatsächlich durchlaufen werden. Dies ist aber unabdingbar für ein komplettes Unrolling ohne weitere Branch-Befehle, die den Code wieder in kleine Basisblöcke aufteilen. Zudem bedeutet eine Zusammenfassung von vielen Schleifendurchläufen eine extreme Vergrößerung des Codes bei nur noch minimalem Performance-Gewinn.
Beseitigung der Abhängigkeiten
Das Bild zeigt das Unrolling von zwei Durchläufen des Beispielcodes. Die Hyperblocks der Durchläufe stehen direkt hintereinander und laufen (meist) ohne Branch-Befehl hintereinander ab. Das Beispiel zeigt aber, dass dieses einfache Verfahren nicht zu einer Performance-Steigerung führt. Ursache hierfür sind die Datenabhängigkeiten in den Registern und im Speicher, da die beiden (ehemaligen) Schleifen nur als einfache Kopien hintereinander aufgereiht sind.
Eine Beseitigung der Abhängigkeiten für eine höhere Performance durch eine mögliche parallele Ausführung ist das Ziel dieses Abschnitts. Hierzu müssen die durch Loop Unrolling entstandenen Abhängigkeiten zunächst analysiert werden:
WAR-Hazards bzw. Anti-Abhängigkeiten entstehen durch Aneinanderfügung zweier Schleifen. Dies fiel bisher nicht ins Gewicht, da ein Vergleich und ein anschließender Sprung (ein Takt Bedarf) die Schleifendurchläufe trennte.
Speicherabhängigkeiten können denselben Effekt erzeugen. Während bei Registern eine Analyse der Abhängigkeiten durch den Compiler möglich ist (die Register werden immer direkt adressiert), kann dies je nach Adressierungsmodi für Speicherzugriffe nicht mehr möglich sein. Dies gilt insbesondere bei einem indirekten Speicherzugriff. In einem solchen Fall muss der Compiler in konservativer Weise annehmen, dass Abhängigkeiten vorliegen, um garantiert korrekte Ergebnisse zur Laufzeit zu produzieren.
Im Bild sind die Speicherabhängigkeiten sichtbar: Die Instruktionen 6 respektive 8 (eine davon führt der Prozessor in jedem Fall aus) bezeichnen zum Teil dieselben Speicherstellen wie die neu hinzugekommenen Instruktionen 21, 23 und 24. Die Problematik besteht in der Bestimmung, ob diese Speicherstellen nun tatsächlich übereinstimmen.
Die Abhängigkeit zwischen 6/8 und 21 ist relativ einfach zu bestimmen, falls a[] und b[] voneinander unabhängige, nicht überlappende Arrays darstellen. Schwieriger liegen die Dinge bei 23 und 24 in Verbindung mit 6/8. Hier muss eine Abhängigkeitsanalyse die Adressfindung über die Register r1 und r3 mit allen möglichen Fällen durchlaufen.
Im Beispiel ist es möglich, eine Unabhängigkeit dieser Load- und Store-Instruk-tionen zu finden. Weiterhin kann der Compiler identische Ladezugriffe aus zwei Schleifendurchläufen entdecken (b[i+1] der ersten Teilschleife und b[i] der zweiten). Diese kann er beim Unrolling zu einem Zugriff zusammenfassen. Mit diesem Wissen kann der Compiler dann eine Umstellung der Befehle und ein entsprechendes Renaming vornehmen. Den optimierten Code, der nahezu eine Verdoppelung der Performance bietet, zeigt Teil b) im Bild.
Kompilierung für bedingte Befehle mit Steuerungsbits
Zwei wichtige Bereiche, die beide mit relativ neuen Techniken (im Sinn des Compiler-Baus) verbunden sind, soll der folgende Abschnitt näher behandeln: Den Ersatz bedingter Sprungbefehle durch bedingte "normale" Befehle und die Analyse von Speicherabhängigkeiten beim Loop Unrolling.
Für die Einführung bedingter Befehle dient als Beispiel die Übersetzung des Sourcecodes der inneren Schleife von wc (word count, zählt Zeichen, Wörter und Zeilen eines Textes unter Unix). Diesen Code stellt folgendes Bild dar.
Die erste Übersetzung in einen "klassischen" Assembler-Code zeigt die starke Abhängigkeit dieses Codes von Branch-Befehlen: Acht der 28 Befehle sind bedingte Branches, weitere vier Sprungbefehle zerstückeln den Code zusätzlich.
Bild 6.8 zeigt neben der "klassischen" Assembler-Übersetzung (a) auch den Kontrollflussgraphen mit den Messergebnissen bei einem Lauf über einen Text mit rund 105.000 Zeichen. Diese Laufzeitanalyse ergibt (leider), dass kein Weg innerhalb des Codes wirklich dominant ist. Mit 58 Prozent noch am häufigsten nimmt der Prozessor den Weg A B D E F H A.
Dies entspricht dem Fall, dass ein Buchstabe nicht der erste oder der letzte Buchstabe in einem Wort ist, wodurch die CPU lediglich den Zähler für die Anzahl der gelesenen Character erhöhen muss. Für diese Aktion führt die CPU aber immerhin neun Instruktionen aus, darunter fünf Branch-Befehle.
Verhinderung von Branches
Hier wird die Problematik für Instruction Level Parallelism deutlich sichtbar: Der Prozessor muss die Branches richtig vorhersagen, um den Instruktionsfluss parallel abarbeiten zu können. Bei dem Beispielprogramm kommen nun zwei Effekte zum Tragen, die eine Bearbeitung mit hoher Performance verhindern:
Die Branch Prediction muss die Richtung eines bedingten Sprungs möglichst akkurat vorhersagen. Die Problemstellung verhindert diese Möglichkeit jedoch, wie aus den Wahrscheinlichkeiten im Bild hervorgeht.
Die Möglichkeiten von superskalaren Prozessoren zur Vorhersage und Ausführung von Branches sind zumeist sehr begrenzt. Die Vorhersage bezieht sich auf eine gewisse Tiefe, die Ausführung dabei auf das Commitment der ausgeführten Befehle. Meist ist die parallele Ausführung von vier Instruktionen mit nur einer Verzweigung möglich.
Eine reine Hardware-Lösung, die vom Prozessor die spekulative Durchführung mehrerer Branch-Befehle fordert, ist nicht praxisgerecht. Sie bedeutet, dass eine Mehrfachvorhersage mit einem komplexen Entscheidungsnetzwerk existieren muss, die bewertet, bis zu welchem Teil die Vorhersage gültig war. Die dafür nötige Hardware würde die Taktfrequenz des Prozessors begrenzen - eine sicher negative Nebenwirkung.
Optimal ist die generelle Verhinderung von bedingten Branch-Befehlen. So sind etwa bedingte Moves wesentlich besser parallel zu anderen Befehlen auszuführen. Zwei Verfahren zur Einführung von Predicated Instructions bieten sich deshalb an: Kompilierung für Predicate-Befehle sowie einzelne Optimierungen.
Predicated Instructions
Für die Kompilierung führt man ein Hyperblock-Netzwerk ein. Jeder Hyperblock besteht aus mehreren Basisblöcken, zwischen denen Übergänge durch Kontrollflussbefehle existieren. Der Hyperblock kann nur einen Startblock als Zugang haben, darf aber an mehreren Stellen verlassen werden.
Der Compiler übersetzt den Hyperblock nun so, dass er mit Hilfe der if-Conver-sion alle Übergänge zwischen den Basisblöcken durch bedingte Befehle ersetzt. Ausnahmen hiervon bilden die Sprünge nach außen, also zum EXIT des Hyperblocks. Theoretisch ist dies ein gutes Verfahren, in der Praxis tun sich jedoch neue Problemfelder auf:
Die Formierung von langen Blöcken kann neue Hazards erzeugen.
Die Anzahl der benötigten Register übersteigt bei paralleler Ausführung die Ressourcen der CPU.
Die Länge des kritischen Codes, bevor wieder ein sicherer Berechnungszustand erreicht wird, kann zu groß werden.
Dies sind zwar zumindest zum Teil gewollte Effekte. Bei zu intensiver Nutzung der Predication können diese Nachteile den Gewinn aber wieder aufbrauchen. Der Compiler muss daher Hyperblock-Synthese, Registerbenutzung, Hazard-Vermeidung und kritische Pfadlänge miteinander ausbalancieren. Der Code im Bild setzt den gestrichelt gezeichneten Teil aus dem vorangegangenen Bild mit Nutzung der Predicated Instructions um.
Teil a) nutzt einfache pxx-Befehle (handoptimiert), Teil b) nutzt doppelte pxx-Befehle, die auf Vorhersage-Flags wirken und diese mit den vorhergehenden Inhalten verknüpfen. Der allgemeine Befehlstyp für das Listing sieht wie folgt aus:
p<ycmp> Pout1(<ytype>), Pout2(<ytype>), src1, src2 (Pin);
Dieser Befehl verfügt also über zwei Ziel-Flags, die via Verknüpfung in <ytype> (zum Beispiel: U entspricht Unconditional, OR dem ODER und so weiter) aus dem Vergleich von src1 und src2 entstehen. Dieser Befehl selbst ist wieder konditionierbar über Pin.
Klassische Weiteroptimierung
Als Ergebnis bleiben nur noch zwei Branch-Befehle übrig: Zum einen auf den Abschnitt C, auf den die Abschnitte D bis M dann als Codekopie folgen, zum anderen als EXIT-Sprung. Bei Verwendung eines 2-Bit-Zähler für die Branchvorhersage ergeben sich im konkreten Fall bei 14 Einsprüngen in den C-Teil maximal 56 Fehlvorhersagen - gegenüber vorher 52.000!
Als positiven Nebeneffekt der neu geschaffenen Hyperblocks hat der Compiler anschließend bessere Möglichkeiten zur klassischen Optimierung. Die Instruction-Level-Parallelisierung sortiert beispielsweise den Code nach parallelisierbaren Instruktionen um. Eine weitere Optimierung ist die gemeinsame Nutzung von Unterausdrücken (Common Subexpression Elimination).
Das vorhergehende Beispiel zeigt sich deshalb so freundlich, weil ein Block existiert, der sehr dominant und zu einem Hyperblock zusammenfassbar ist. Bei anderen Verzweigungen und Schleifen lässt sich dies nicht so einfach bewerkstelligen, vor allem nicht, wenn man die Möglichkeiten der superskalaren CPU nicht übersteigen will. Die Formung eines Hyperblocks ist zwar immer möglich. Dieser muss jedoch im Rahmen der realen CPU-Ressourcen ausführbar sein, da ansonsten die gewünschten Beschleunigungseffekte ausbleiben. So kann zum Beispiel eine Vielzahl von Austrittspunkten die Branch-Vorhersage so sehr in Anspruch nehmen, dass durch fehlerhafte Vorhersagen kein optimaler Code entsteht.
Realer Performancegewinn
Das nächste Beispiel zeigt eine übersetzte grep-Routine, in der eine Menge von Verzweigungen zum EXIT auffällt. Bei 15 Befehlen sind immerhin acht Branches und ein Sprungbefehl vorhanden, so dass bei Ausführung von einem BranchBefehl pro Takt nur noch eine theoretische Performance von 1,67 Instruktionen pro Takt möglich wäre. Die diversen EXIT-Branches kann der Compiler zusammenfassen, indem pxx-Befehle das Flag p1 bestimmen und der bedingte Sprungbefehl jmp (p1) erfolgt. Diese Technik wird Branch Combining genannt und bietet sich an, wenn sehr viele Austrittspunkte aus einem Block existieren.
Das Beispiel ist natürlich deshalb sehr gut geeignet, da sich die gesamten Branches durch eine Kette von Vorhersagevergleichen mit OR-Kombinationen überführen lassen. Die CPU durchläuft die Branches im Fall des Austritts aus der Schleife zwar nochmals, der Schleifendurchlauf selbst ist aber stark beschleunigt. Eine experimentelle Evaluation dieser Optimierungen ergibt folgendes Bild:
Fünf der gezeigten Beispiele entstammen gängigen Benchmarks (SPEC CFP92: 052.alvinn, 056.ear, SPEC CINT92: 008.espresso, 023.eqntott, 072.sc), die anderen stellen gebräuchliche Unix-Utilities dar.
Generierung von Aussagen zu Speicherabhängigkeiten
Die zweite Optimierungsmethode, die Umsortierung von Instruktionen zur besseren Nutzung der parallelen Ressourcen, benötigt Aussagen zu Abhängigkeiten der Instruktionen untereinander. Während Registerabhängigkeiten leicht zu detektieren sind, wenn man wie üblich auf eine indirekte Adressierung der Register verzichtet, gilt dies für Speicherzugriffe keinesfalls: Deren Abhängigkeiten sind teilweise nur schwer zu erkennen. Gewöhnlich konzentriert sich die Analyse von Datenabhängigkeiten auf die Ebene des Sourcecodes. Folgende Maßnahmen sind dabei relativ einfach und in vielen Compilern vorhanden:
Detektierung der Unabhängigkeit beim Zugriff auf einzelne, globale Variablen
Detektierung der Unabhängigkeit beim Zugriff auf einzelne Stack-Variablen an unterschiedlichen Stack-Positionen
Die interessante und häufig notwendige Frage ist jedoch, ob Zugriffe innerhalb eines Arrays voneinander abhängig sind. Zwei Fragestellungen sind dabei von besonderem Interesse:
Wie kann man durch andere Variablen indizierte Zugriffe auf Mitglieder eines Arrays auf Abhängigkeit untereinander untersuchen?
Wie kann man die insbesondere in C genutzten Aliasnamen auf Pointer und Array-Mitglieder hierbei berücksichtigen?
Die letzte Frage bedeutet, dass die Analyse insbesondere über Funktionsgrenzen hinweg global durchgeführt werden muss. Derartige Codeanalysen sind sehr komplex und zeitaufwendig. Daher versucht der Compiler, den Code so früh wie möglich mit wenig Aufwand möglichst akkurat zu analysieren. Die gewonnenen Informationen trägt er dann an die nachfolgenden Stufen weiter. Das Bild zeigt das prinzipielle Vorgehen dieser Methode der frühen Sourcecode-Analyse.
Im Unterschied zum klassischen Ansatz, mit Hilfe einer Sourcecode-Analyse eine Sourcecode-Transformation durchzuführen, zeigt diese Abbildung, dass die gewonnenen Sourcecode-Informationen zu einer Low Level Transformation führen.
Abhängigkeiten in Schleifen
Folgendes Bild zeigt drei verschiedene Abhängigkeiten im Code. Hieran sieht man bereits, dass das azyklische Codescheduling nur dann parallelisiert und in der Reihenfolge vertauscht werden kann, wenn schleifenunabhängige (loop-independent) Abhängigkeiten nicht existieren. Diese Abhängigkeit besteht aber im Bildteil a), da die CPU bei jedem Schleifendurchlauf mehrfach auf A[i] zugreifen muss. Im Übrigen darf in keinem Fall eine Datenabhängigkeit möglich sein, um ein Reordering durchzuführen. Diese Analyse kann aber zur Compile-Zeit eventuell unmöglich sein.
Bei schleifenabhängiger Datenabhängigkeit wie im Bildteil b) bezeichnet man die Anzahl der Schleifen, die Zugriffe auf die gleiche Speicherstelle erzeugen, als Abhängigkeitsdistanz (dependence distance). Im obigen Beispiel beträgt diese relevante Größe zwei Schleifen.
Deshalb kann der Compiler zwei Schleifen bequem zusammenfassen und im Code umstellen, sofern keine weiteren Abhängigkeiten existieren. Wie in Bildteil c) dargestellt, ist dabei die tragende Schleife relevant: Für die innere Schleife (Index i) besteht eine Abhängigkeitsdistanz von 1, da die Schreib- und Lesevorgänge immer auf dieselbe Stelle zeigen, während in der äußeren Schleife die Distanz 2 beträgt. Beim Codescheduling muss jeweils nur die momentane Schleife berücksichtigt werden, also die zyklischen und nicht zyklischen Abhängigkeiten innerhalb der aktuellen Schleife.
Abhängigkeitsnotationen
Die für eine Optimierung notwendigen Abhängigkeitsnotationen sind in der Tabelle dargestellt. Es müssen sichere Informationen zur Codeoptimierung existieren, oder der Compiler muss die Annahme der unlösbaren Abhängigkeit treffen. Folgendes Bild zeigt ein Beispiel für eine einfache, aber wirksame Optimierung. Dabei kann er redundante Ladeoperationen vermeiden.
Kategorie | Mögliche Werte |
|---|---|
| |
type | flow, anti, output, input |
distance | (integer), unknown |
carrying loop | none, (loop identifier) |
certainty | definite, maybe |
Zwei Bedingungen müssen für die Eliminierung der Load-Instruktion erfüllt sein: Es muss eine definitiv schleifenunabhängige Speicherabhängigkeit sein (i darf sich nicht ändern), und es darf keine Veränderung des Speicherinhalts geben: Alle Speicheroperationen zwischen den Load-Befehlen müssen definitiv auf andere Stellen zeigen. Die Akkuratheit der Abhängigkeitsanalyse begrenzt die Optimierungsmöglichkeiten durch Reordering des Codes entscheidend. Da im Sourcecode eine Analyse noch am besten durchführbar ist, gewinnt der Compiler dort die meisten Ergebnisse und führt sie bis auf das Assembler-Niveau mit allen Codetransformationen mit.
Die Pflege der Abhängigkeitsdarstellungen ist ein wichtiges Thema im Optimierungsteil von Compilern. Die Abhängigkeitspfeile innerhalb eines Schleifenkörpers sind bei Codeumstellungen trivial nachzuführen. Bei ausschließlich schleifenabhängiger Datenabhängigkeit bewirkt ein Reordering der Befehle beispielsweise keine Änderung der Abhängigkeitsdistanz und somit keine Änderung der Verhältnisse. Ändert die Codeoptimierung allerdings die Schleifenstruktur, ist die Nachführung der Abhängigkeiten weniger trivial. Eine der wichtigsten Änderungen ist das Loop Unrolling . Bei Nutzung der Abhängigkeitsdistanz kann der Compiler größere Schleifen gewinnen und den Code entsprechend umsortieren.
Loop Unrolling
Folgendes Bild zeigt ein Beispiel zum Loop Unrolling und zu den daraus resultierenden Abhängigkeiten im Code. Durch die Nutzung der Abhängigkeitsdistanz (hier 2) in der Originalschleife kann der Compiler die neuen Abhängigkeitsdistanzen einfach bestimmen.
Hierzu geht er von dem ersten Befehl mit Abhängigkeitsinformation aus und bestimmt zwei Größen für jeden anderen Befehl: Die Schleifennummer der Kopie, in der sich der Befehl befindet, und die neue Abhängigkeitsdistanz.
Falls der Compiler die Distanzinformationen nicht nutzen kann, muss er hier immer eine 1 annehmen (bei einer Abhängigkeitsdistanz von 0 handelt es sich um schleifenunabhängige Informationen). Damit sind größere Reordering-Maßnahmen für den Compiler verbaut. Deshalb sind Distanzinformationen sehr wichtig für eine durchgreifende Optimierung.
Das Diagramm zeigt abschließend die Wirkung der Datenabhängigkeitsanalyse mit anschließendem Code-Reordering. Die Programme benutzen alle Integer-Arithmetik und laufen zum Test auf einer superskalaren CPU mit achtfacher Parallelität. Dabei ergibt sich durchwegs eine Beschleunigung von 20 Prozent über alle Programme mit signifikanten Ausreißern nach oben.
Ausblick
Die Entwicklung einer superskalaren Hardware und deren optimiere Unterstützung durch Compiler hat für eine signifikant schneller Programmausführung gesorgt. Die nächste Stufe für noch mehr Leistung stellen VLIW-Prozessoren dar. Deren Befehle enthalten mehrere Felder, mit denen sie unabhängige Funktionseinheiten in der CPU steuern. Mehr dazu lesen Sie im nächsten Kapitel CPU-Grundlagen: VLIW-Architekturen & Intels Itanium.
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. (ala)