#################################################################################################### # Codegeneratoren relevante Fragen # #################################################################################################### ######################################## Prozessorarchitekturen #################################### CISC vs. RISC: CISC: - variable Befehlslänge - komplexe Addressierung - komplexe Befehle wie zB string compare RISC: - fixe Befehlslänge - wenige Addressierungsarten (Register + offset) ein Speicherzugriff pro Befehl (LOAD/STORE) - einfache Befehle - viele Register und eigene Vektorregister Mikroarchitektur ist eine Implementierung der Instruction Set Architektur. RISC ISC muss nicht RISC Mikorarchitektur bedeuten. Pipelining: - überlappende Ausführung der einzelnen Stufen - Erhöht sich mit Taktfrequenz - Es gibt eine Grenze, welcher bei diesen 4-5 GHz ist die wir jetzt haben, wegen Abwärme usw. - Maximal 50 Stufen sinnvoll - Abhängigkeiten können problematisch sein Abhängigkeiten: - existieren zwischen operand fetch, execute und write-back - durch Result forwarding kann man zB das write-back umgehen (bypassen) => bei Sprüngen problematisch -> erst beim execute das nächste fetch klar - deswegen Branch prediction: mit historischen Daten den Sprung vorhersagen. Mit 2 Bits schon 70/80% bei INT und 90% bei FLOAT ops. Mit einer größeren History zur Mustererkennung in Sprüngen schon 98% bei INT und 99% bei FLOAT ops. - Für dynamische Sprünge kann man einen branch target address cache verwenden Superskalare Ausführung: - vervielfachte Ausführung unabhängiger Befehle - braucht eine Abhängigkeitsanalyse mit einem Graphen OOO execution: - Instruktionen warten in reservation stations auf operanden - Realisiert durch Register Renaming: - Reduziert Abhängigkeiten (vor allem Anti-Dependencies) - Mit Precize Interrupts (In-Order-Completion) - In-Order-Dispatch - OOO execution - In-Order-Write-Back VLIW: Very Long Instruction Word - Ziel ist die Beschleunigung der Abarbeitung von sequentiellen Programmen durch Ausnutzung von Parallelität auf Befehls-Ebene. - Im Gegensatz zu superskalaren Prozessoren werden bei VLIW die Befehle nicht dynamisch zur Laufzeit vom Prozessor den einzelnen Funktionseinheiten zugewiesen, sondern der Compiler gruppiert parallel ausführbare Befehle. VLIW schließt die Verwendung einer Pipeline-Architektur nicht aus. EPIC: Explicitly Parallel Instruction Computing - Eine EPIC-CPU arbeitet nach dem Prinzip der in-order Execution, im Gegensatz zur out-of-order execution der superskalaren CPUs. - Kombiniert mit VLIW Cache: - Weil Prozessor mittlerweile 1000 mal schneller als Speicher (kleiner und mehr Transistoren) - Mehrere Layers L1, L2, L3 - Datencache und Instruktionscache ######################################## Optimierungen ############################################# Skalare: - Konstanten Evaluieren - Konstanten Propagieren - Abwechselnd in Schleife bis Fixpunkt erreicht - Kopien Propagieren - Common-Subexpression-Elimination / Partial Redundancy Elimination (Verallgemeinerung) - Es wird dabei nach Teilausdrücken gesucht, die zuvor bereits berechnet wurden. Wenn solche gefunden werden, wird das vorherige Ergebnis in einer Variable gespeichert und die wiederholte Berechnung durch die Variable ersetzt. - PRE für verschiedene Pfade in zB IFs Programm: - Dead-Code-Elimination (entstanden z.B. durch andere Optimierungen) - Function Inlining (eliminiert Function calls) vs. Procedural Abstraction (sinnvoll ohne Argumente) - Ersetzung von Rekursion durch Schleifen (einfach geht es bei tail-recursion) - Peephole: kurze Befehlssequenzen ersetzt durch einfachere Schleifen: - Induction Variable Elimination -> vereinfacht Addressberechnung -> wird mit invariant code motion Kombiniert - Unrolling - Schleifenrumpf vervielfachen um Kosten zu sparen - Vektorisierung - Strip Mining - abarbeitung in Streifen im Speicher - Parallelisierung - Aufteilen der Schleife auf mehrere Prozessoren - Fission/Fusion (invers zueinander) - für weitere optimierungen - Interchange - innere und äußere Schleife tauschen - für lineare Speicherzugriffe - Collapsing - geschachtelte Schleifen vereinen - Peeling - Erste/Letzte Iteration entfernen - für weitere Optimierungen - Software Pipelining (Siehe letzten Teil) - Überlappende Ausführungen - Sehr wichtig für VLIW Datenabhängigkeiten: - true dependence - anti dependence - output dependence - control dependence - TODO Graph Convex: - Hat Vektorisierungsoptimierungen - auch partiell - Loop distribution und Interchange dafür - Parallelisierung - Lokale Skalare Optimierungen - Globale Skalare Optimierungen HP: - Level 0 Optimierungen: Datenflussanalyse/Dead-Code-Elimination, Register-Allokation, NOP-Elimination - Level 1 Optimierungen: Datenflussanalyse/Dead-Code-Elimination, Register-Allokation, Peephole, Branch, Instruction Scheduling - Level 2 Optimierungen: Wie 1 aber noch common subexpression elimination, usage analysis, loop invariant motion, graph coloring. ######################################## Befehlsauswahl ############################################ Man kreiert einen Zwischencodebaum und versucht mit einer Baumgrammatik den Zwischencodebaum mit einem Maschinencodebaum darzustellen Unterschied zwischen burg und iburg: burg: - verwendet tree pattern matching und dynamic programming in compile-compile time(Methode zum algorithmischen Lösen eines Optimierungsproblems durch Aufteilung in Teilprobleme und systematische Speicherung von Zwischenresultaten) - zwei passes über den subject tree. erster pass bottom-up (von den blattknoten) und findet matching mit minimalen kosten. - Nachteil ist dass Kosten konstant sein müssen iburg: - nimmt burg spezifikation und macht dynamic programming bei compile time - dadurch dynamische kosten möglich, Fast/Flexible Selection with constraints: - Nachteil von dynamischen Kosten ist dass wir nicht mehr die Baumgrammatik gut in einen Automaten umbauen können für schnelle Befehlsauswahl - Stattdessen kann man aber Constraints einführen die dynamische Kosten simulieren - Die Kosten sind weiterhin quasi-statisch aber für bestimmte übergänge im Automaten gibt es dynamische Checks bei der Befehlsauswahl. Generalized Instruction selection using SSA graphs: - Die meisten Techniken limitiert auf basic blocks und kommen nicht mit embedded systems klar - Kann komplexe Patterns lösen welche mehrere Resultate liefern (address + inc, div/mod) - Verwendung von SSA Graphen als Programmrepresentation und verwendet Partitioned Boolean Quadratic Programming. - PBQP: NP-vollständiges Optimierungsproblem, aber trotzdem gut lösbar mit Heuristiken. - Instanz: - mehrere diskrete variablen x in deren eigenen Domänen - Funktion h wo für jede variable ein wert aus der Domäne gewählt wird. - Auswertung ob optimale Lösung: - lokale Kosten: c(x,d) kosten von variable wenn wert gewählt - benachbarte kosten: c(x1,x2,d1,d2) wenn variablen abhängig sind - Summe beider Kosten für alle Variablen - Reduktion von Befehlsauswahl auf PBQP: - Jeder Knoten im SSA Graph ist eine Variable - Die Domäne der Variable sind die möglichen Base Rules - lokale Kosten sind dann abhängig von clock-cycle, speicherverbrauch der base rules - Kanten im SSA Graph (also von Operand zu Operation) stellen die Nachbarschaft der Variablen dar. - Lösung von PBQP entscheidet dann die Auswahl der base und chain rules - Für Komplexe Patterns: - Nicht mehr tree-shaped sondern DAG-shaped: mehrere inputs mehrere outputs - Extra rules für die grammatik, wo auch zB angenommen werden muss dass die inputs für div und mod identisch sein müssen. Diese rules/patterns haben dann ihre eigene Kostenfunktion welche in PBQP verwendet werden kann - Es muss eine topologische Ordnung zwischen den pattern gefunden werden um zyklen zu vermeiden - Solver: - Heuristischer Solver welcher Subklasse von PBQP optimal in O(nm^3) löst n: Variablen m: maximale Domänengröße ######################################## Registerallokation ######################################## für Minimierung von Speicherzugriffen Generelle Funktionsweise Chaitin: - Man verwendet Konfliktgraph, welchen man aus dem Kontrollflussgraphen bekommen hat - Blockhäufigkeiten wichtig für Kosten - Phase 1: Konfliktgraph bauen - Phase 2: Vereinfachung des Graphen: - Entferne Knoten die kleineren Grad haben als Registeranzahl und setze auf Stack - Wenn keins vorhanden dann wähle knoten mache einen Spill und entferne vom graphen. Knoten gewählt via niedrigste Kosten durch Knotengrad. - Wiederhole bei 1 wenn gespilled - Phase 3: nimm knoten von stack und gib farbe die nicht bei nachbarn sind. Erweiterung durch Briggs: - Chaitin nicht minimal, findet nicht immer beste Lösung - Statt irgendeinen Knoten zu entfernen entferne Knoten mit kleinstem Grad. - Spilling erst beim Coloring. Wenn node nicht gecolored werden kann dann wird sie gespilled. Alternative von Chow/Hennessy: - Priority based Scheduling - Statt Kosten zu berechnen, wird die Ersparnis berechnet. Dadurch wird overallocation vermieden. Ist bei LOAD/STORE egal aber bei komplexeren addressierungen vielleicht nicht. - Life range splitting: Man kann Variablen vielleicht auch während der Life-range spillen. - Life-range unterschiede bei callee und caller saved registern: Callee-saved kann über calls hinaus leben. Caller-saved ist immer nur zwischen function calls. Es ist etwas wichtiger caller saved register zu haben. - Algorithmus: 1. Entferne unconstrained life ranges 2. Gib life ranges farben bis alle eine farbe haben oder keine farbe mehr übrig: a) mache eine priority für alle constrained life ranges b) wähle farbe für life range mit höchster Priorität welche gewählt werden darf. diese farbe darf nicht mehr für interferierende Life ranges gewählt werden c) schau ob splitting nötig ist. es ist nötig wenn alle möglichen register nicht mehr wählbar sind. 3. Färbe unconstrained mit farben die gewählt werden dürfen Unterschiede Chaitin-Briggs und Chow/Hennessy: 1) Chaitin auf Instruktionslevel, Hennessy auf Basic Block Level (Chaitin Graph größer) 2) Chaitin verwendet alle Register, Chow reserviert 4 3) Chaitin spilled wenn kein Platz da ist. Chow nimmt in Register auf wenn Platz da ist 4) Chow kann globale Variable halten 5) Chow kann live ranges splitten -> weniger register 6) Chow ist one-pass Coalescing: - Vereinigung von Copy-Related Liferanges - Aggressive Coalescing kann Färbbarkeit verringern - Deswegen Idee von Briggs zum Konservativen Coalescing -> nur wenn Färbbarkeit nicht schlechter - Rematerialisierung: Errechnung von Wert aus einem anderen - ABER: coalescing kann sogar verbessern. - Idee: aggressive coalescing, aber wenn verbundener Knoten gespillt werden soll, dann reversiert man das coalescing und spilled nur einen Knoten Optimal Register Allocation: - macht ein 0-1 Integer Programming problem - hat: copy elimination, live range splitting, rematerialization, callee und caller register spilling, special instruction operand requirements und paired register - Experimentell ist die Laufzeit n^3 - Optimal unter folgenden Annahmen: - Kein Instruction reordering - Nur Spill und rematerialization hinzugefügt - nur copy und symbolische register removed - alle pfade können potentiell ausgeführt werden - spillkosten sind fixiert mal der ausführungshäufigkeit - execution stoppt nicht mitten im block - Analyse, Solver und Rewrite + Decision variable table - Analyse: Kontrollgraph produziert binäre entscheidungen über registerallokationen. - Solver: Löst das kreierte integer programming problem - Rewrite: nimmt die variablen die auf 1 gesetzt wurden und alloziert Register - Optimiert: 1000 mal schneller (10xCPU, 10xSolver, 10x Algo) - Führt Lemmata ein die zeigen dass bestimmte aktionen nicht nötig sind. Entfernt dadurch 80% der Decision variablen. Dadurch entfallen dann auch einige Constraints. Das Problem wird viel kleiner und dadurch wird das solven schneller. Interprozedural: 1. Globale Register Allokation zu Linkzeit - produziert objektmodule welche globale register nicht alloziert haben und die erst zu linkzeit alloziert - annotiert instruktionen mit registeraktionen - Dann macht es usage informationen - Anhand dessen werden zur Linkzeit globale register alloziert 2. Feedback-directed Compilation - Arbeitet auf netzen von variablen die sich nicht überlappen. diese webs kann man dann für promotion von variablen zu globalen registern verwenden. - local reference set: variable in set wenn in procedure gecalled - parent reference set: wenn im local set vom caller - child reference set: wenn im local set von gecallter procedure - dann kann man die webs einfach registern zuordnen - Spill Code Motion: save und restore wird im callgraphen elevated sodass es free ist für die child nodes (?) ######################################## Befehlsanordnung ########################################## List-Scheduling - Zuerst Dependency graph - Dann Zyklen von Ende bis Anfang aufaddieren - Zuerst die mit größtem Delay auswählen - update current time usw. Komplexität - durch dependency graph n^2 laut Paper - laut Prof. Krall, kann man das auch in n machen. Prepass vs. Postpass - wenn man zuerst scheduled dann hat man mehr spills - wenn man zuerst alloziert dann ist man vielleicht langsamer IPS - Prepass mit sicht auf Registerbelegung - behält freie register im Auge und wählt code sequenzen um registerdruck klein zu halten - switcht dadruch zwischen zwei heuristiken DAG driven - Postpass scheduling - Verwendet dependency graph während allocation - verwendet earliest finish times und earliest issue times um registerbelegung zu machen - scheduling nur freie antidependencies einfügen RASE - macht schedule cost estimates für allocator damit der effekt klar ist von entscheidung. durch mapping auf quadratische funktion - prescheduler vor global register allocator für schedule cost info - lokale und globale registerallokation ist verteilt - Komplizierter als IPS => nicht viel benefit Trace Scheduling - lineare sequenz von instruktionen von basic blöcken mit erlaubten Sprüngen - diese traces werden nach häufigkeit gewichtet - die Virtuellen register der traces werden dann nach Maschinenregister gemapped in VLM - Binding passiert spät: erst wenn value zum ersten mal vorkommt wird das gemapped ###################################### Software Pipelining ######################################### Überlappende Instruktionsausführung Epilog vor dem steady state, Prolog danach Initiation Interval - 1 z.B. jeder cycle neue Iteration - 2, jeder zweite cycle Modulo Variable Expansion - verwende verschiedene Register um initiation interval zu verkürzen und Datenabhängigkeiten zu minimieren Hierarchical Reduction - Zuerst innere schleife als einzelne instruktion behandeln und die äußere pipelinen - in schritten zur mitte IF conversion: - Wandle Kontrollabhängigkeiten zu Datenabhängigkeiten um mittels predicated execution Resource Constrained Software Pipelining: - verwendet resource constraints für pipelining - Kreiere einen automaten aus den Abhängigkeiten - Praktisch nicht so gut anwendbar weil die Heuristiken fehlen Iterative Modulo Scheduling: - Nimm minimales initiation interval (darf zu niedrig sein) - constraints können von der maschine kommen oder von Abhängigkeiten mit latencies - versuche schedule mit software pipeline - wenn es geht super, wenn nicht erhöhe initiation interval und arbeite weiter - arbeitet mit budget SIMD: - Same instruction multiple data - aligned vs. unaligned Zugriffe - Loop Unrolling mit acyclic dada dependence graph zwischen statements (können immer oder auch nicht immer ausgeführt werden) - Alignment Analyse für LOAD STORE - check pointer wo alignment nicht klar und mach zwei loops, ein mal vektorisiert und einmal mit bekannten informationen