Zusammen mit Sebastian Buchwald habe ich meine Diplomarbeit am IPD Goos geschrieben. Hier die Zusammenfassung in deutsch und englisch:
Das PBQP (Partitioned Boolean Quadratic Problem) ist ein geeignetes Optimierungsproblem zur Modellierung einer Befehlsauswahl. Eine solche Befehlsauswahl zeichnet sich durch die direkte Verarbeitung komplexer Befehlsmuster und einen linearen Lösungsalgorithmus aus, der ein Befehlsauswahlproblem auf seinen Kern reduziert. Allerdings ist das Finden einer PBQP-Lösung NP-vollständig und wurde im Rahmen der Befehlsauswahl bisher nur empirisch untersucht.
Diese Arbeit gibt zur Verifikation des Verfahren eine Formalisierung für den Aufbau und die Lösung eines Befehlsauswahl-PBQP an. Mit zwei einfach prüfbaren Voraussetzungen wird gezeigt, dass eine Lösung garantiert werden kann. Anhand der Implementierung einer IA-32-Befehlsauswahl in libFirm wurden Anforderungen an eine Spezifikationssprache dokumentiert. Die Leistungsfähigkeit dieser Befehlsauswahl wurde mittels der SPEC-Testsammlung bestätigt.
PBQP (Partitioned Boolean Quadratic Problem) is a suitable optimization problem to model instruction selection. Such an instruction selection features direct processing of complex instruction patterns and a linear-time solving algorithm, which reduces an instruction selection problem to its core. However finding a PBQP-solution is NP-complete and was only empirically investigated in the context of instruction selection.
This thesis presents a formalization of the construction and solving of PBQP instruction selection for the verification of this technique. With two easily testable preconditions there is proof that solving can be guaranteed. With an implementation of an IA-32 instruction selection in libFirm requirements of a specification language were documented. The capabilities of this instruction selection were confirmed using the SPEC benchmark suite.
Ein Download als pdf ist verfügbar, genauso wie die Folien des Abschlussvortrags. Für die bib-Verwaltung auch als Artikel auf CiteULike zu finden. Um unsere Arbeit zu referenzieren, benutze folgendes bibtex:
@mastersthesis{Buchwald2008,
abstract = {Das PBQP (Partitioned Boolean Quadratic Problem) ist ein geeignetes Optimierungsproblem zur Modellierung einer Befehlsauswahl. Eine solche Befehlsauswahl zeichnet sich durch die direkte Verarbeitung komplexer Befehlsmuster und einen linearen L\"{o}sungsalgorithmus aus, der ein Befehlsauswahlproblem auf seinen Kern reduziert. Allerdings ist das Finden einer PBQP-L\"{o}sung NP-vollst\"{a}ndig und wurde im Rahmen der Befehlsauswahl bisher nur empirisch untersucht. Diese Arbeit gibt zur Verifikation des Verfahren eine Formalisierung f\"{u}r den Aufbau und die L\"{o}sung eines Befehlsauswahl-PBQP an. Mit zwei einfach pr\"{u}fbare Voraussetzungen wird gezeigt, dass eine L\"{o}sung garantiert werden kann. Anhand der Implementierung einer IA-32-Befehlsauswahl in libFirm wurden Anforderungen an eine Spezifikationssprache dokumentiert. Die Leistungsf\"{a}higkeit dieser Befehlsauswahl wurde mittels der SPEC-Testsammlung best\"{a}tigt.},
author = {Buchwald, Sebastian and Zwinkau, Andreas},
citeulike-article-id = {6095592},
citeulike-linkout-0 = {http://www.info.uni-karlsruhe.de/papers/da_buchwald_zwinkau.pdf},
keywords = {code-generation, compiler, firm, instruction-selection, pbqp},
month = {December},
posted-at = {2009-11-10 18:11:30},
priority = {0},
school = {Universit\"{a}t Karlsruhe (TH), IPD Goos},
title = {Befehlsauswahl auf expliziten Abh\"{a}ngigkeitsgraphen},
url = {http://www.info.uni-karlsruhe.de/papers/da_buchwald_zwinkau.pdf},
year = {2008}
}
Sat Nov 28 11:51:41 2009
