Optimale Codegenerierung für Explizit-Parallele Prozessoren

Entwickler von Embedded Systems stehen heute Rechenanforderungen gegenüber, die vor nicht allzu langer Zeit noch Stand der Technik im Supercomputing-Bereich waren. Mit herkömmlichen Techniken und bei gleicher Technologie erfordert eine zwei bis dreifache Geschwindigkeitssteigerung etwa die achtzigfache Chipfläche und etwa die zwölffache Energie -- eine oftmals nicht akzeptable Größenordnung für mobile Anwendungen. Ein vielversprechender Ansatz diese Probleme zu lösen sind VLIW Architekturen mit einer großen Anzahl an parallelen Recheneinheiten und Datenpfaden sowie applikationsspezifische irreguläre Architekturerweiterungen, die für eine bestimmte Anwendung maßgeschneidert werden. Hoch optimierende Übersetzer und spekulative Transformationen sind nötig, um das hohe Maß an Parallelismus in entsprechende Rechenleistung umsetzen zu können. Diese Optimierungen müssen in der Regel unterschiedliche Aspekte sorgfältig gegeneinander abwägen. Vielfach eingesetzte heuristische Techniken sind dabei oft nicht in der Lage dies zufriedenstellend umzusetzen. Darüber hinaus ergeben sich weitere Herausforderungen durch - oftmals applikationsspezifische - irreguläre Architekturerweiterungen und Asymmetrien. Einerseits resultiert daraus ein erheblicher Wartungs- und Entwicklungsaufwand, der mit traditionellen statischen Codegeneratoren nur schwer zu bewältigen ist. Andererseits sind heuristische Übersetzungstechniken oftmals nur unzureichend geeignet um applikationsspezifische Erweiterungen effektiv auszunützen. Optimale Ansätze basierend auf ganzzahliger linearer Programmierung haben das Potential diese Problemstellungen zu bewältigen. Mathematische Formulierungen erlauben eine kombinierte Optimierung unterschiedlicher Teilprobleme und ermöglichen die Modellierung komplexer architektureller Einschränkungen. Letztere können automatisch aus einer generischen Architekturbeschreibung abgeleitet werden. Trotzdem erreichten optimale Verfahren bisher keine wesentliche praktische Bedeutung. Zahlreiche Teilprobleme wie Instruktionsauswahl, Registerallokation oder Instruktionsanordnung sind NP vollständig - naive mathematische Formulierungen führen daher unausweichlich zu inakzeptablen Übersetzungszeiten. Ziel dieses Projektes ist die Entwicklung neuartiger Algorithmen und mathematischer Formulierungen, die die wesentlichen Vorteile von integrierten Codeerzeugungstechniken bewahren und gleichzeitig praktikable Laufzeiten aufweisen. Dazu gehört sowohl die Anwendung von mathematischen Verfahren zur Verringerung der Laufzeit linearer Optimierungssysteme, wie zum Beispiel Cutting-Plane Ansätze, Column-Generation Techniken oder Lagrange Relaxierung. Aufgrund der erheblichen Komplexität einzelner Teilbereiche planen wir darüber hinaus, die entwickelten Modelle zur Identifikation von Schwachstellen existierender Heuristiken und zur Entwicklung effizienter Approximationsalgorithmen zu verwenden. Unsere Schwerpunkte sind die Entwicklung von integrierten Verfahren zur gemeinsamen Behandlung von Instruktionsanordnung und Registerallokation, integrierte Befehlsanordnung für zyklische Programmregionen (Software Pipelining) und Unterstützung von irregulären Architekturen und asymmetrischen Datenpfaden. Ein neuartiges Übersetzungsschema erlaubt uns Teilbereiche der Registerallokation zu separieren und dadurch die Komplexität integrierter Verfahren entscheidend zu verringern.

Der Fokus dieses Forschungsprojekts war optimale und beinahe optimale Maschinencodeerzeugung für Prozessoren mit explizitem Parallelismus. Prozessoren mit explizitem Parallelismus können innerhalb eines Befehlszyklus mehrere Befehle gleichzeitig ausführen, der Programmierer (oder der Übersetzer) muss allerdings explizit angeben, welche Befehle voneinander unabhängig sind und gleichzeitig ausgeführt werden können. Diese Prozessoren werden meistens in eingebetteten Systemen wie Mobiltelefonen verwendet und sie haben oft Hardwareeinschränkungen wie gruppierte Funktionseinheiten und Registersätze, bedingte Ausführung oder rotierbare Registersätze. Maschinencodeerzeugung ist der letzte maschinenabhängige Teil eines Übersetzers und besteht aus Befehlsauswahl, Registerzuteilung, Befehlsanordnung, Softwarepipelining, Bedingungskonvertierung und Gruppierung. Aufgrund der Komplexität der Probleme ist es oft nicht möglich eine optimale Lösung zu finden. Weiters werden die Teilprobleme unabhängig voneinander gelöst, was zu weiteren nicht optimalen Lösungen führt. Das Ergebnis dieses Projekts waren neue heuristische und exakte Methoden für optimale und beinahe optimale Maschinencodeerzeugung. Die heuristischen Methoden liefern fast genauso gute Ergebnisse wie die optimalen Methoden und sind schnell genug, um in Übersetzern zur täglichen Programmentwicklung eingesetzt zu werden.