Titelaufnahme

Titel
Compiler backend generation from structural processor models / Florian Brandner
VerfasserBrandner, Florian
Begutachter / BegutachterinKrall, Andreas ; Hruka, Tomá
Erschienen2009
UmfangXIII, 151 Bl. : Ill., graph. Darst.
HochschulschriftWien, Techn. Univ., Diss., 2009
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
Bibl. ReferenzOeBB
DokumenttypDissertation
Schlagwörter (DE)Prozessorbeschreibungssprachen/Übersetzer/Übersetzergenerierung
Schlagwörter (EN)Processor Description Languages/Compiler/Compiler Generation
Schlagwörter (GND)Prozessor / Beschreibungssprache / Übersetzer <Informatik> / Generator <Informatik>
URNurn:nbn:at:at-ubtuw:1-32992 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Compiler backend generation from structural processor models [1.28 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

In den letzten Jahren konnte im Bereich der eingebetteten Computersysteme eine rasante Entwicklung beobachtet werden. Prozessoren, die in diesen Systemen eingesetzt werden, unterliegen seit jeher besonders hohen Anforderungen in Bezug auf den Stromverbrauch, die Chipfläche, die Rechenleistung und die Produktionskosten. Bei der Entwicklung eines neuen Prozessors in diesem Gebiet muß besonderes Augenmerk auf kurze Entwicklungszyklen, sowie hohe Flexibilität bei der Realisierung neuer Technologien gelegt werden.

Aus diesem Grund wurden in den letzten Jahren applikationsspezifische Prozessoren immer beliebter, da diese ausreichend Rechenleistung bieten, es aber trotzdem erlauben die gegebenen Einschränkungen, ob nun technischer Natur oder nicht, einzuhalten. Wesentliche Grundvoraussetzungen sind hierbei eine gute Kenntnis des geplanten Einsatzbereichs, sowie geeignete Werkzeuge um alternative Prozessorimplementierungen schnell und einfach erproben zu können.

Ein vielversprechender Ansatz, um Eigenschaften dieser Prozessoren formal zu beschreiben, sind Prozessorbeschreibungssprachen. Basierend auf entsprechenden Prozessorbeschreibungen ist es möglich eine Vielzahl von Werkzeugen abzuleiten. So ist es möglich Softwareentwicklungswerkzeuge und Prozessorsimulatoren bereitzustellen, sowie Abschätzungen des zu erwartenden Stromverbrauchs und der benötigten Chipfläche zu berechnen. Durch die automatische Bereitstellung der entsprechenden Werkzeuge können alternative Prozessorentwürfe und unterschiedliche Befehlserweiterungen eines Prozessors schnell und elegant evaluiert werden. Dies verspricht eine entscheidende Verkürzung der Produktentwicklungszyklen.

In dieser Arbeit wird die neu entwickelte Prozessorbeschreibungssprache xADL vorgestellt. Im Gegensatz zu verwandten Systemen wird durch diese Sprache ausschließlich die Struktur der Prozessorimplementierung beschrieben.

Der Befehlssatz, obwohl durch die Beschreibung nicht explizit dargestellt, ist ein integrales Grundkonzept der Sprache. Ein Extraktionsverfahren analysiert die Struktur des Prozessors und berechnet daraus eine abstrakte Darstellung der einzelnen Befehle, die durch den Prozessor unterstützt werden. Das abstrakte Modell des Befehlssatzes steht in enger Beziehung zu den zugrundeliegenden Hardwarekomponenten. Die Sprache ist daher in verschiedensten Anwendungsszenarien nutzbar. Im Vergleich zu anderen Prozessorbeschreibungssprachen bietet die xADL-Sprache eine Vielzahl nützlicher Erweiterungen, die zu besonders kurzen und intuitiv lesbaren Prozessormodellen führen. Dies umfasst beispielsweise erweiterbare Typen zur Beschreibung von Hardwarekomponenten, die Klassen und Templates der Programmiersprache C++ ähnlich sind.

Die Praxistauglichkeit dieses Ansatzes wird am Beispiel eines Übersetzergenerators untersucht. Hier werden die wesentlichen Komponenten eines Übersetzers aus einer gegebenen xADL-Beschreibung generiert. Dies umfasst im Speziellen die Registerbelegung, die Befehlsanordnung, sowie die Befehlsauswahl. Messungen zeigen, dass die generierten Übersetzer mit handgeschriebenen Produktivsystemen konkurrieren können. Für eine Beschreibung der MIPS-Architektur erzielt der generierte Übersetzer Laufzeitverbesserungen von bis zu 9% für einzelne Benchmarkprogramme. Im Durchschnitt ist eine moderate Verschlechterung der Laufzeit von lediglich 15% festzustellen. In Anbetracht der um bis zu 34% verminderten Codegröße sind diese Ergebnisse ausgezeichnet. Noch bessere Resultate wurden für zwei Konfigurationen des VLIW-Prozessors CHILI erreicht. Hier beträgt die Laufzeitverbesserung bis zu 20%, bei gleichzeitiger Reduktion der Codegröße zwischen 3% und 47%. Im Durchschnitt über alle Benchmarkprogramme ist eine minimale Verschlechterung der Laufzeit messbar, die 5% beziehungsweise 3% beträgt.

Zusätzlich wird die Vollständigkeit der generierten Übersetzer untersucht, d.h., ob der resultierende Übersetzer tatsächlich in der Lage ist für alle durch die Sprache zulässigen Eingabeprogramme entsprechenden Maschinencode zu erzeugen. Traditionelle Ansätze, basierend auf Baumautomaten, sind im Rahmen heutiger Übersetzersysteme nur bedingt einsetzbar, da häufig verwendete dynamische Überprüfungen während der Befehlsauswahl nicht dargestellt werden können. Ein neues Verfahren namens Terminal Splitting wird vorgestellt, das erlaubt diese Überprüfungen explizit durch neue Terminalsymbole darzustellen. Eine durch Terminal Splitting vorverarbeitete Spezifikation der Befehlsauswahl wird sodann mit Hilfe des traditionellen Ansatzes auf Vollständigkeit geprüft. Das vorgeschlagene Verfahren ist vollständig in den Übersetzergenerator integriert und erlaubt dem Prozessordesigner wertvolle Information in der Form von Gegenbeispielen zur Verfügung zu stellen.

Zusammenfassung (Englisch)

The embedded systems computing domain showed a tremendous development in recent years. Processors used in these systems face rigid constraints in terms of power consumption, chip area, performance, and production costs. Short development cycles and great flexibility in the adoption of new technologies are key factors for successful embedded processors. Application-specific instruction set processors have proven successful in providing the necessary computing power, while meeting the various technical and non-technical design constraints.

However, the development of such processors requires intimate knowledge of the processor's application domain and appropriate tools to evaluate design alternatives quickly.

A promising approach to formally specify processor design alternatives and automatically derive the necessary tools for design space exploration are processor description languages. These languages capture the instruction set, and often also the hardware organization of the given processor using an abstract specification. The information provided through the processor models can be used to automatically derive software development and simulation tools, as well as area and power estimates. This approach has the potential to significantly reduce the turn-around time during the evaluation phase of a new application-specific processor, because alternative instruction set extensions and hardware designs can be specified and evaluated systematically.

In this work the novel xADL language is presented, which, in contrast to most contemporary processor description languages, focuses on a structural modeling of the processor's hardware organization. The instruction set, even though not specified explicitly, is a central concept of the language and its support tools. Through instruction set extraction an abstract model of the instruction set is automatically derived from the structural specification. The instruction set view combined with the detailed hardware model provides the necessary information to derive high-quality tools for design space exploration.

The language allows the reuse of hardware components through extensible types, similar to classes and templates known from the C++ programming language. In comparison to other processor description languages, xADL specifications are thus very compact and readable.

The feasibility of the approach is demonstrated by a compiler backend generator.

It is shown how the essential processor-specific components of a compiler backend can be derived from xADL models, including the register allocator, the instruction scheduler, and the instruction selector. The automatically generated compilers are competitive to handcrafted production compilers. For a MIPS processor model speedups of up to 9% have been measured for certain benchmarks. On average a moderate slowdown of 15% has been observed, which is remarkable considering the code size reduction of up to 34%. Even better results have been measured for two configurations of the CHILI VLIW processor, where speedups of up to 20% and an average slowdown of only 5% to 3% can be reported. The code size reductions for the CHILI range from 3% up to 47%.

Further, the completeness of the generated compiler components is investigated, i.e., whether the generated compiler is able to produce machine code for all input programs possibly accepted by the compiler frontend. Traditional approaches based on tree automata are not applicable in the context of modern compilers, instruction selection process is often controlled by dynamic checks.

These checks can not be represented by tree automata. Terminal splitting is proposed to explicitly represent the dynamic checks present in the instruction selector specification. The transformed specification is then processed by a traditional completeness test. The proposed approach is integrated with the compiler generator system and thus provides valuable feedback to the processor designer in the form of counter examples.