Achieving an enhanced worst-case timing prediction and performance for hard real-time code

Abstract

Harte Echtzeitsysteme gewinnen in unserer Gesellschaft immer mehr an Bedeutung, da sich bis heute bereits eine beträchtliche Anzahl von komplexeren computergesteuerten Systemen, die speziellen sicherheitskritischen Bedingungen unterliegen, etabliert hat.<br />Inzwischen findet man harte Echtzeitsysteme besonders häufig in sicherheitskritischen Bereichen, zu welchen unter anderem der Flugzeug- und Automotivbereich, Atomkraftwerke, Robotertechnik sowie die Militärtechnologie zählen.<br />Der Programmcode solcher harten Echtzeitsysteme unterliegt bestimmten Anforderungen bezüglich der worst-case Performance bzw. der worst-case Ausführungszeit (Worst-Case Execution Time, abk.: WCET) und setzt bestimmte Eigenschaften voraus, um eine effiziente WCET - Analyse zu ermöglichen.<br />Trotz der Anforderungen an das zeitliche Verhalten von Programmcode harter Echtzeitsysteme ist es teilweise nach wie vor üblich, mit traditionellen Algorithmen und Programmstrukturen zu arbeiten, die gewöhnlicherweise in Nicht-Echtzeitsysteme Verwendung finden. Das Ziel dieser traditionellen Ansätze ist vor allem, einen hohen Durchsatz für den Durchschnittsfall zu erzielen, wohingegen die worst-case Performance dabei als nicht so sehr relevant erachtet wird. Dennoch ist die WCET von Programmcode bzw. den Tasks harter Echtzeitsysteme eine der wichtigsten zeitlichen Grössen und macht somit eine elementare Eigenschaft eines Echzeitsystems aus.<br />Hinsichtlich der WCET soll diese Arbeit einen Einblick in eine unkonventionelle Programmierstrategie ermöglichen, welche speziell für harte Echtzeitsysteme geeignet ist. Diese Strategie macht es sich zum Ziel, die traditionellen Priorit\"aten von Durchschnittsausführungszeit (Average Execution Time, abg.: AVG) und WCET zu vertauschen.<br />Die in diesem Gebiet besonders wichtige WCET ist stark mit der WCET-Analyse verbunden, in welche die Pfadanalyse ebenfalls stark miteinfliesst. Um hierbei die Komplexität der WCET-Analyse reduzieren zu können, existiert daher ein spezielles Programmier-Paradigma mit der Haupteigenschaft, Single-Path Code zu erzeugen. Dieses Paradigma soll ermöglichen, dass das entsprechende Programm auf einem einzigen Ausführungspfad ausgeführt wird. Diese Arbeit demonstriert diesen Ansatz anhand einiger ausgewählter Algorithmen, auf welche sowohl diese Methode als auch die bereits angesprochene Strategie angewendet wird.<br />Darüber hinaus werden auch Ergebnisse und Vergleiche von den Varianten der entsprechenden Algorithmen präsentiert und die Sinnhaftigheit dieser Vorgehensweise beurteilt. Die Arbeit erforscht unter anderem auch die Ausweitung dieser Konzepte auf andere Klassen von Algorithmen und zeigt dafür auch neue Ansätze für die Vereinheitlichung des Ausführungspfades und der Ausführungszeiten.<br />

Hard real-time computing systems play a crucial role in our society since a considerable number of complex systems rely on processor control which must satisfy specific safety conditions. Meanwhile, hard real-time computing has established itself extensively in the area of safety critical systems, including applications such as nuclear power plants, air traffic control, automotive electronics, robotics, military systems and others.<br />The programming code of such hard real-time systems has to deal with specific demands with respect to worst case performance, its so-called execution time (WCET) and, moreover, requires specific properties in order to enable an efficient Worst-Case Execution-time Analysis (WCET Analysis). Despite these demands on the temporal behaviour of hard real-time programming code, it is still common to operate with traditional algorithms and programming structures which are usually applied to non real-time applications. The objective of these traditional approaches is to obtain high temporal performance for the average case, whereas the worst-case performance is considered to be of less importance.<br />As a matter of fact, however, the WCET of hard real-time code is one of the most important time constants and represents a temporal basic parameter of a real-time system. In my thesis I want to provide an insight into an unconventional progamming strategy that enables a programming code which is well suited for hard real-time systems, swapping the traditional priorities between Average Execution Time (AVG) and WCET.<br />The highly prioritised Worst-Case Execution-time (WCET) is strongly associated with WCET Analysis which involves path analysis of the code which is executed. In order to reduce the complexity of WCET analysis there exists a special progamming paradigm where the key property is to write single-path code. As as consequence, the paradigm makes it possible to obtain a single execution path which makes path analysis and thus WCET analysis trivial. The thesis demonstrates how to apply both, the progamming strategy mentioned above as well as the programming paradigm for single execution path by exploring several pieces of code, respectively algorithms. Furthermore, the results and comparisons of the different variants of algorithms will be presented and evaluated.<br />The thesis also explores how the concepts mentioned above can be applied to other classes of algorithms and by doing so presents new strategies that achieve unification of the execution path as well as the excection times.