HOME | ENGLISH | IMPRESSUM | KIT

Studienarbeit (abgeschlossen): SSA-basierte Registerzuteilung mit integrierter Kopienminimierung

Aktuelle Forschung auf dem Gebiet der SSA-basierten Registerzuteilung ermöglichen eine Aufteilung des Problems in drei Phasen:

  • Auslagern
  • Färben
  • Kopienminimierung

Der an der Universität Karlsruhe entwickelte Compiler libFirm ist der weltweit einzige, der diesen SSA-basierten Ansatz zur Registerzuteilung umsetzt. Während Auslagern und Färben in Linearzeit realisiert sind, können die bisherigen Heuristiken der Kopienminimierung diese Skalierbarkeit nicht bieten.

Ein vielversprechender Ansatz für eine lineare Heuristik ist die Modellierung als Partitioned Boolean Quadratic Problem (PBQP), das bereits erfolgreich für traditionelle Registerzuteilung erprobt wurde. Ziel der Studienarbeit ist es, dieses Verfahren auf das Kopienminimierungsproblem zu übertragen.

Aufgabe

  • Entwicklung einer linearen Heuristik zur Kopienminimierung unter Benutzung des PBQP-Ansatzes
  • Evaluierung des Verfahrens in Bezug auf die bereits vorhandenen Heuristiken

Literatur

Voraussetzungen

  • Spaß am Übersetzerbau
  • Gute Programmierkenntnisse in C


Veröffentlichungen

Veröffentlichung
SSA-basierte Registerzuteilung mit integrierter Kopienminimierung

Betreuer

Wissenschaftliche Mitarbeiter
Sebastian Buchwald

Studenten

Ehemalige Studenten
Thomas Bersch