Diplomarbeit

[1]	Sebastian Buchwald, Andreas Zwinkau, Befehlsauswahl auf expliziten Abhängigkeitsgraphen, Universität Karlsruhe (TH), IPD Goos, Dec 2008.

Zusammenfassung

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üfbare 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.

Autoren

Ex-Studenten Sebastian Buchwald Andreas Zwinkau