Das Partitioned Boolean Quadratic Problem (PBQP) ist ein NP-vollständiges mathematisches Optimierungsproblem. Für das PBQP existieren eine Reihe effizienter Reduktionsschritte, die die Optimalitätsstruktur erhalten. In Kombination mit heuristischen Reduktionsschritten lässt sich eine Unterklasse von Problemen sehr effizient lösen.

Diese Unterklasse von PBQP tritt insbesondere bei (SSA-basierter) Registerallokation auf. Dazu wird zusätzlich zum (harten) Färbeproblem auf dem Interferenzgraph eine zusätzliche Optimalitätsbedingung gestellt, die die Kosten für Registerconstraints berücksichtigt.

Aufgabe:

Im Rahmen dieser Arbeit soll eine gut dokumentierte Bibliothek zum Lösen von PBQP mit hinreichend benutzbaren Werkzeugen entwickelt werden. Bisherige Lösungen, wie etwa der in libFirm integrierte PBQP-Solver oder einem Solver der TU Wien, sind entweder nicht wiederverwendbar, undokumentiert, unvollständig oder lassen Werkzeuge zum Analysieren und Exportieren von Probleminstanzen vermissen.



Veröffentlichungen

Veröffentlichung

Development of a library for solving and analyzing PBQP

Betreuer

Wissenschaftliche Mitarbeiter
Sebastian Graf

Studenten

Studenten
Max Baumstark