Instruction set extensions for time-predictable code execution

Abstract

Hochzuverlässige Echtzeitsysteme sind heutzutage Teil vieler Anwendungen im Bereich der Luft- und Raumfahrt, sowie der Automobilindustrie. Die Anforderungen betreffen dabei nicht nur die Korrektheit der gelieferten Ergebnisse, sondern auch den konkreten Zeitpunkt, wann diese der Anwendung zur Verfügung stehen. Im Falle eines so genannten harten Echtzeitsystems kann es zur Katastrophe, zum Beispiel einem Flugzeugabsturz, kommen, wenn eine Anwendung zu lange für ihre Berechnungen benötigt. Deshalb ist es wichtig, schon im Vorhinein die maximalen Ausführungszeiten eines Programms zu kennen.<br />Die Worst-case execution time Analysis (WCET analysis) befasst sich mit der Berechnung der längst möglichen Ausführungszeiten eines Programms.<br />Dabei müssen theoretisch alle Aspekte eines Prozessors, wie aktueller Speicherzustand, das zu Grunde liegende Caching Modell etc., berücksichtigt werden. Um die Analyse des Assembler-Codes zu vereinfachen, wurde von Puschner und Burns eine Transformation vorhandener Algorithmen vorgeschlagen, sodass nur mehr ein möglicher Ausführungspfad existiert. Allerdings unterstützen nicht alle Prozessoren die dazu nötigen Instruktionen.<br />Im Rahmen dieser Diplomarbeit wurde das Instruction Set des SPARC V8 um Befehle erweitert, die die Analysierbarkeit des resultierenden Assembler-Codes vereinfachen sollen. Weitere Ziele waren eine einfache Umsetzung der zusätzlichen Befehle in Hardware, eine möglichst leichte Integration in vorhandene Codegeneratoren, sowie eine Verbesserung der Worst-case Performance. Um ein möglichst unverfälschtes Ergebnis zu erhalten, wurde ein vorhandener Compiler so angepasst, dass die vorgeschlagenen Erweiterungen bei der Übersetzung berücksichtigt werden.<br />Außerdem wurde ein Simulator entwickelt, sodass die Performance der zusätzlichen Befehle anhand mehrerer Benchmark-Algorithmen erhoben werden konnte. Auf Grund der Messergebnisse war es möglich, die vielversprechendsten Kombinationen der Befehlserweiterungen zu identifizieren und sie als Grundlage für zukünftige Prozessoren im Echtzeitbereich vorzuschlagen.<br />

Nowadays, highly dependable real-time systems are part of many applications in the aerospace and automotive industries. The requirements of real-time applications do not only include the correctness of results, but also the instant of time, when a result is available. In case of a so-called hard real-time system, the whole system may crash if a task does not finish within a given period of time. Thus, knowing worst-case execution times of programs in advance is of utmost importance.<br />Worst-case execution time analysis (WCET analysis) calculates the longest possible duration an application may take to finish. To do so, all external and internal influences have to be considered, for example, processor and memory load, the implemented caching strategy, etc. In order to simplify the analysis of assembler code, Puschner and Burns presented the so-called single-path transformation of algorithms. It is based on the idea to eliminate conditional branches such that just one possible execution path remains which is trivial to analyze.<br />Nevertheless, this is only possible if the processor provides certain kinds of instructions.<br />Within the current thesis, the instruction set of the SPARC V8 processor has been extended so that the analysis of assembler code is simplified.<br />Additional goals included that it should be easy to implement these instructions in hardware and adapt existing code generators to support the instruction set extension. Moreover, the resulting worst-case performance should be improved. In order to evaluate the feasibility of the additional instructions, new code generating passes have been added to an existing compiler and an instruction set simulator has been implemented. Based on the results of numerous simulated benchmark algorithms, the most promising instruction set extensions have been identified and suggested to be part of future processors used in real-time systems.<br />