Design und Implementierung eines Superoptimierers für Zwischencode

Student:Tobias Stoll
Title:Design und Implementierung eines Superoptimierers für Zwischencode
Type:study thesis
Advisors:Veldema, R.; Schell, D.; Philippsen, M.
State:submitted on July 21, 2004
Prerequisits:
Topic:

Hintergrund:
Beim Übersetzen von Programmen gilt meist die Faustregel: "je kleiner der Code, desto besser". Dies gilt insbesonders für eingebettete Syteme, welche mit geringen Speicherresourcen auskommen müssen. Aber auch moderne Prozessoren können die Kluft, welche sich zwischen Arbeitsspeichertakt und internen Prozessortakt auftut, nur dann überbrücken, wenn die Prozessorcaches immer optimal mit Daten gefüllt sind und nur wenige Hauptspeicherzugriffe nötig sind. Da von einem Compiler eine möglichst kurze Übersetzungszeit erwartet wird, kann an dieser Stelle keine (zeit-)aufwändige Optimierung hinsichtlich der Codegröße vorgenommen werden. Dies kann zu einem anderen Zeitpunkt durch ein anderes Werkzeug, einem Superoptimizer, nachgeholt werden. Ein Superoptimizer versucht für eine gegebene Funktion die kürzest mögliche Anweisungsfolge zu ermitteln, welche semantisch äquivalent zur Originalfunktion ist. Dies geschieht dadurch, dass beliebige kürzere Instruktionssequenzen erzeugt werden und diese auf semantische Gleichheit mit der Originalfunktion getestet werden.

Aufgabenstellung:
Im Rahmen der Arbeit soll ein Superoptimizer für Java-Bytecode unter Berücksichtigung der folgenden Punkte erstellt werden:

  • Es sollen Methoden untersucht werden, welche den Suchraum reduzieren, z. B. genetische Algorithmen
  • Der Superoptimizer soll parallel auf mehrere Rechner verteilt arbeiten
  • Die Korrektheit der Implementation muss dargestellt werden
  • Eine kurze Bewertung der erzielten Speicherplatzeinsparungen

Literatur:
Denali: A Goal-directed Superoptimizer ( http://theory.lcs.mit.edu/~randall/papers/abstracts/denali.html )

watermark seal