Optimierungen in Übersetzern (UE2)
Optimierungen in Übersetzern
Dozent/in
Details
Zeit/Ort n.V.:
Corona-Hinweis: Die Lehrveranstaltung findet online über StudOn statt. Voraussetzung zur Teilnahme an der Prüfung ist die erfolgreiche Bearbeitung der Übungsaufgaben.
- Mi 8:15-9:45, Raum H4
Studienfächer / Studienrichtungen
- WPF CE-MA-INF ab Sem. 1
- WPF INF-MA ab Sem. 1
Inhalt
In der Vorlesung werden ausgewählte Kapitel aus dem Übersetzerbau besprochen.
Schwerpunktmäßig werden Optimierungstechniken für die Übersetzung imperativer Programmiersprachen diskutiert, insbesondere solche, die für Hochleistungsrechner und Parallelrechner von Bedeutung sind. Begleitend dazu werden einige oft verwendere Techniken und Repräsetationsformen vorgestellt, die erforderlich sind, um die zur Optimierung benötigten Informationen geeignet zu berechnen bzw. zu verwalten.
Die folgenden Stichworte geben einen Überblick über die in der Vorlesung angesprochenen Einzelthemen:
- Abhängigkeitsanalyse, Abhängigkeitsgraph, Array-Index-Analyse, SSA Graph, Steuerungsflußgraph, Dominatoren,
- datenflußbasierte Schleifentransformationen: Strength Reduction, Elimination von Induktionsvariablen, Verschiebung von schleifeninvariantem Code, Schleifenentzweigung,
- Schleifenumordnungen: Schleifenvertauschung, Wellenparallelisierung, Schleifenumkehr, Strip Mining, Kachelbildung, Schleifenaufspaltung, Schleifenvereinigung,
- Schleifenrestrukturierung: Ausrollen, Schleifenzusammenfassung, Schleifenersetzung: Reduktion, Schleifenmustererkennung,
- Speicherzugriffstransformationen: Array-Padding, Speicherbank-Konflikte, Skalarexpansion und Array-Kontraktion,
- Partielle Auswertung: Konstantenpropagierung, Konstantenfaltung, Algebraische Vereinfachungen, Strength Reduction,
- Redundanzentfernung: unerreichter Code, unnötiger Code, tote Variablen, gemeinsame Teilausdrücke,
- Prozeduraufruftransformationen: Blattprozeduren, Inlining, Prozedurduplizierung, Prozedureinbettung, Rekursionselimination, Funktionsvorauswertung,
- Optimierungen für Parallelrechner: Datenaufspaltung, Skalarreplikation, Arrayreplikation, Daten- und Aktivitätsausrichtung, Guards, Botschaftenkombination, Latenzzeitverbergung, Prefetch und Poststore, Synchronpunktelimination,
- Pointer- und Aliasanalyse
Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt.
ECTS-Informationen
Titel
Optimizations in Compilers
Credits
7,5
Inhalt:
As a main focus the lecture gives an overview of optimizing techniques applicable to procedural programming languages. In particular, optimization techniques that are of importance to high performance computers and parallel computers are covered. Techniques and representations are introduced that are necessary to compute and to manage information required for optimization are covered as well.
The following list of key words provides an overview of the topics covered in this lecture:
- dependence analysis, dependence graph, array subscript analysis, SSA, control flow Graph, dominators.
- loop transformations: strength reduction, induction variable elimination, loop-invariant code motion, loop unswitching.
- loop reordering: loop interchange, loop skewing, loop reversal, strip mining, loop tiling, loop distribution, loop fusion.
- loop restructuring: loop unrolling, loop coalescing, loop replacement (reduction), loop idiom recognition.
- memory access transformations: array padding, cache miss jamming, scalar expansion, array contraction.
- partial evaluation: constant propagation, constant folding, algebraic simplification, strength reduction.
- redundancies removal: unreachable-code elimination, useless-code elimination, dead-variable elimination, common-subexpression elimination.
- procedure call transformations: leaf procedure optimization, procedure inlining, procedure cloning, function memoization, tail recursion elimination.
- transformations for parallel machines: data decomposition, scalar privatization, array privatization, data partitioning and computation partitioning, guard introduction, message aggregation, message pipelining, prefetch and poststore, syncronization elimination.
- pointer analysis, alias analysis
Zusätzliche Informationen
Erwartete Teilnehmerzahl: 80
Übungen zu Optimierungen in Übersetzern
Dozent/in
Details
Zeit/Ort n.V.:
Corona-Hinweis: Die Lehrveranstaltung findet online über StudOn statt. Zeit und Ort für die Übungen werden in der ersten Vorlesungsstunde vereinbart.
- Di 12:15-13:45, Raum 02.224 CaÜbung (UE)rstr.9
- Do 12:15-13:45, Raum 00.151-113
- Fr 12:15-13:45, Raum 02.133-113
Studienfächer / Studienrichtungen
- WPF CE-MA-INF ab Sem. 1
- WPF INF-MA ab Sem. 1
Inhalt
In der Übung werden die in der Vorlesung vorgestellten Konzepte und Algorithmen zur Optimierung von Programmen durch einen Übersetzer wiederholt und vertieft.
Im Rahmen der Projektübungen erweitern die Übungsteilnehmer den in Übersetzerbau 1 implementierten Übersetzer um eine Auswahl der vorgestellten Algorithmen.
Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt.
Zusätzliche Informationen
Erwartete Teilnehmerzahl: 90