185.A04 Optimierende Übersetzer
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2020W, VU, 2.0h, 3.0EC, wird geblockt abgehalten

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Distance Learning

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage (u.a.)

  • die grundlegenden Prinzipien und Konzepte optimierender Übersetzung, ihrer theoretischen Fundierung, mathematischen Grundlagen und von Methoden zu ihrem empirischen und formalen Korrektheits-, Vollständigkeits- und Optimalitätsnachweis am Beispiel typischer praxisrelevanter Programmanalysen und -transformationen optimierender Übersetzung aufzuzeigen, zu beurteilen und wertend einzuordnen.
  • diese Prinzipien und Konzepte auf neue Aufgaben optimierender Übersetzung zu übertragen und anzuwenden und das gewählte Vorgehen sachlich und fachlich zu begründen.
  • die Möglichkeiten und Grenzen optimierender Übersetzung im Spannungsfeld von Entscheidbarkeit, Skalierbarkeit und Wirksamkeit als Ganzes, auf der Ebene von Analyse- und Optimierungsproblemen und konkreter Analyse- und Optimierungsverfahren einzuordnen, zu beurteilen und daraus Empfehlungen für die allgemeine Anwendungsprogrammierung abzuleiten.

Inhalt der Lehrveranstaltung

Die Vorlesung vertieft in Theorie und Praxis das Gebiet
Programmanalyse und -optimierung, das ein wesentliches
Forschungsgebiet im Bereich Programmiersprachen und Übersetzerbau
ist. Dabei spannt die Vorlesung den Bogen von den theoretischen
Grundlagen bis zur praktischen Anwendung und der automatischen
Generierung von Programmanalysen und Optimierungen. Im Übungsteil
werden die in der Vorlesung behandelten Themen in theoretischen und
praktischen Übungen eigenständig vertieft. Für die praktischen Übungen
wird dabei die Static Analysis Tool Integration Engine SATIrE
eingesetzt; ein System, das diverse Werkzeuge für die Analyse und
Optimierung von objektorientierten Sprachen integriert, darunter den
Program Analyzer Generator (PAG).

Teil I: Einführung

  • Motivation
  • Klassische Gen/Kill-Datenflussanalysen

Teil II: Intraprozedurale Datenflussanalyse

  • Intraprozeduraler Datenflussanalyserahmen
  • Gen/Kill-Datenflussanalysen reinspiziert
  • Konstantenausbreitung und -faltung
  • Partielle Redundanzelimination (PRE)
  • PRE: Busy Code Motion
  • PRE: Lazy Code Motion
  • PRE: Sparse Code Motion
  • PRE: Zusammenfassung, Ausblick

Teil III: Interprozedurale Datenflussanalyse

  • Grundlagen
  • Interprozeduraler Datenflussanalyserahmen
  • Funktionaler Ansatz
  • Kontextinformationsansatz
  • Anwendungen

Teil IV: Erweiterungen, andere Sprachumgebungen

  • Alias- und Heap-Analysen
  • Optimierungen für objektorientierte Sprachen

Teil V: Abschluss und Ausblick

  • Zusammenfassung, Ausblick

Literaturverzeichnis

Anhänge

  • Mathematische Grundlagen
  • Flussgraphen, Darstellungspragmatik
  • Implementierung von Busy und Lazy Code Motion
  • Lazy Strength Reduction

Ausgewählte Leseempfehlungen

  • Flemming Nielson, Hanne Riis Nielson, Chris Hankin. Principles of Program Analysis.Springer-V., 2. Auflage, 452 Seiten, ISBN 3-540-65410-0, 2005.
  • Y. N. Srikant, Priti Shankar. The Compiler Design Handbook: Optimizations & Machine Code Generation. CRC Press, 1. Auflage, 928 Seiten, ISBN 084931240X, 2002. 
  • Keith D. Cooper, Linda Torczon. Engineering a Compiler. Morgan Kaufmann, 801 Seiten, ISBN 155860698X, 2003. 
  • Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 856 Seiten, ISBN 1558603204, 1997.

Methoden

Abhaltemodus: Online

Aufgrund geltender COVID-19-Beschränkungen stehen Horsäle,
Übungsgruppenräume und Rechnerlabore im WS 2020/21 nur mit stark
eingeschränkter Sitzplatzkapazität und Belegbarkeitshäufigkeit zur Verfügung.
Die verbleibenden Raumressourcen sind vorzugsweise Lehrveranstaltungen
des 1. Studienjahrs zur Verfügung gestellt. Für die Lehrveranstaltung
Optimierende Übersetzer ist deshalb ein Online-Abhaltemodus nötig!

Ziel: Die aus der Unmittelbarkeit von Präsenzveranstaltungen resultierenden
Vorteile möglichst umfassend zu erhalten in Form von Echtzeitvideokonferenzen
als Online-Veranstaltungsformat.

Auszug aus einer Information von VR Matyas vom 31.07.2020:

  • Wir möchten [...] darauf hinweisen, dass eine Verschärfung der Sicherheitsmaßnahmen während der Sommermonate, bzw. während des Semesters notwendig werden kann.

Änderungen im Lehrveranstaltungsablaufs- und -abhaltungsplan (auch erheblicher Natur) sind daher jederzeit und auch kurzfristig möglich!

Methoden

  • Angeleitetes eigenständiges Erlernen und Einüben: Durch Vorträge (Orientierung, Einordnung) und umgekehrte Klassenzimmersitzungen (Übung, Vertiefung nach Eigenstudium) angeleitetes eigenständiges Erlernen und Einüben der in den Lernergebnissen beschriebenen Fähigkeiten mithilfe zur Verfügung gestellter Lehr- und Lernunterlagen, theoretischer und praktischer Übungsaufgaben und weiterer nach Bedarf selbstgewählter Materialien aus zur Ergänzung und Vertiefung vorgeschlagenen Lehrbüchern, Tutorien und wissenschaftlichen Originalarbeiten.
  • Vorbild- und rückmeldungsgeleitetes Lernen: Präsentieren, erläutern,
    begründen, vergleichen, wertend gegenüberstellen eigener und fremder
    Aufgabenlösungen aus sachlicher und fachlicher Sicht in geleiteten
    Übungseinheiten.
  • Selbsteinschätzungstests: Tests zur regelmäßigen Selbsteinschätzung
    und Selbstreflexion des eigenen bisherigen Lernfortschritts und Lernerfolgs.

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

Aufteilung der ECTS-Punkte:

Der Lehrveranstaltung sind 3.0 ECTS-Punkte zugeordnet. Diese
entsprechen einem durchschnittlichen Lernaufwand von 75
Stunden. Dieser durchschnittliche Lernaufwand verteilt sich in
folgender Weise auf die einzelnen Lernaktivitäten der Lehrveranstaltung
(die Angaben Teil I bis Teil V beziehen sich auf Teil I bis Teil V
der Lehrveranstaltungsunterlagen):

  • Angeleitete Lernaktivitäten (ausschließlich online, 17.25h)
    • Vortrag: 9.0h (12 Termine * 0.75h)
    • Umgekehrtes Klassenzimmer: 5.25h (7 Termine * 0.75h)
    • Übungseinheiten: 3.0h (4 Termine * 0.75h)
  • Eigenständige Lernaktivitäten (Home Universitying, 57.25h)
    • Selbstgeleitetes Erarbeiten von Lernergebnissen: 35.0h (Richtwert: Teil I/4.0h, Teil II/12.0h, Teil III/12.0h, Teil IV/6.0h, Teil V/1.0h)
    • Speziell: Lösen der Übungsaufgaben: 20.0h (Richtwert: 4 Angaben * 2.0h + 4 Angaben * 3.0h)
    • Vorbereitung auf die mündliche Prüfung: 2.25h
  • Mündliche Prüfung (ausschließlich online, Videopräsenz): 0.5h

Die Lehrveranstaltung beginnt mit Vorbesprechung und erstem Vortragsteil am Dienstag, den 06.10.2020, 15:15-17:00 Uhr (einschließlich einer 15-minütigen Pause), ausschließlich online in Form einer Echtzeitvideokonferenz. Die Zugangsinformation für die Videokonferenz wird rechtzeitig via TISS-Nachricht bekannt gegeben.

Vortragende Personen

Institut

Leistungsnachweis

  • Online/offline, ohne Präsenz: Acht beurteilte Abgaben theoretischer und praktischer Übungsaufgaben.
  • Online, Videopräsenz: Eine beurteilte 30-minütige mündliche Prüfung über Vorlesungs- und Übungsstoff.

Weitere beurteilte Leistungsnachweise gibt es nicht.

Beurteilung, Beurteilungsschema

Gesamtbeurteilung gewichtet im Verhältnis 1 zu 1 aus Beurteilungen der theoretischen und praktischen Aufgabenlösungen und der mündlichen Prüfung, falls beide Teilbeurteilungen positiv sind, sonst nicht genügend; bei halben Noten gibt die Note der mündlichen Prüfung den Ausschlag.

Beurteilungsschema Übungsaufgaben: ab 50% genügend, ab 62.5% befriedigend, ab 75% gut, ab 87.5% sehr gut.

LVA-Anmeldung

Von Bis Abmeldung bis
30.08.2020 01:00 16.10.2020 12:00 30.10.2020 12:00

Gruppen-Anmeldung

GruppeAnmeldung VonBis
Optimierende Übersetzer 105.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 205.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 305.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 405.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 505.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 605.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 705.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 805.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 905.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1005.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1105.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1205.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1305.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1405.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1505.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1605.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1705.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1805.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 1905.10.2020 12:0016.10.2020 12:00
Optimierende Übersetzer 2005.10.2020 12:0016.10.2020 12:00

Curricula

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorkenntnisse

Die Vorlesung schließt inhaltlich an die Lehrveranstaltung 185.A48
Übersetzerbau an und ergänzt die bisherige Lehrveranstaltungen 185.274
Weiterführender Übersetzerbau und die akuelle Lehrveranstaltung 185.276
Analyse und Verifikation. Sie empfiehlt sich deshalb inbesondere für
Studierende, die im Bereich von Programmiersprachen und Übersetzerbau
einen besonderen Schwerpunkt setzen, eine Seminararbeit, ein Praktikum
oder ihre Diplomarbeit anfertigen möchten.

Vorausgehende Lehrveranstaltungen

Begleitende Lehrveranstaltungen

Vertiefende Lehrveranstaltungen

Weitere Informationen

Sprache

bei Bedarf in Englisch