Measurement-based timing analysis of superscalar processors

Abstract

In den letzten Jahren hat die Anzahl der elektronischen Kontroll- und Steuersysteme stark zugenommen. Damit die Wettbewerbsfähigkeit der Hersteller von elektronischen Steuergeräten erhalten werden kann, wird zunehmend mehr Funktionalität in leistungsstarke und komplexe Computerhardware integriert. Aufgrund dieses Trends in der Kontrollsystementwicklung ergeben sich neue Herausforderungen an die Analyse des Zeitverhaltens von Echtzeitcomputersystemen.<br />Aus der Anforderung an das korrekte Zeitenverhalten eines Echtzeitsystems ergibt sich die Notwendigkeit der genauen zeitlichen Vorhersagbarkeit eines Echtzeitcomputersystems. Daher ist es notwendig, das Zeitverhalten der Tasks eines Echtzeitcomputersystems richtig vorhersagen zu können. Das Forschungsgebiet Worst-Case Execution Time (WCET) Analyse beschäftigt sich mit den Methoden zur Laufzeitbestimmung von Echtzeitprogrammen. Ein zentraler Teil jeder WCET Analyse ist die Modellierung des Hardwarezeitverhaltens.<br />Die detaillierte manuelle Erstellung eines Zeitmodells für neue Hardware ist zeitaufwändig und fehleranfällig. Um diesen Aufwand zu reduzieren und das Portabilitätsproblem auf elegante Weise zu lösen, wurde in dieser Arbeit eine neue hybride WCET Analysemethode entwickelt. Dabei werden Laufzeitmessungen an instrumentierten Tasks verwendet, um das Hardwarezeitmodell zu bestimmen. Im Detail werden von der messbasierten Zeitanalysemethode (MBTA) die folgenden Schritte ausgeführt:<br />Statische Analyse: Im ersten Schritt wird eine statische Analyse des C Quellcodes vorgenommen um die Programmstruktur festzustellen. Im Gegensatz zu anderen Methoden, die auf Objektcodeebene arbeiten, erlaubt dies eine hohe Portabilität aufgrund der weiten Verbreitung von C Code in der Entwicklung von Kontrollsystemen. Weiters wird C Code auch von stark verbreiteten Codegeneratoren (z. B. TargetLink, Real-Time Workshop) erzeugt. Partitionierung des Kontrollflussgraphen: Im zweiten Schritt wird die Komplexität durch automatische Programmzerlegung in analysierbare Teile reduziert. Diese Programmteile werden als Programmsegmente bezeichnet.<br />Testdatengenerierung: Als nächstes werden die Laufzeiten bestimmt, die ein Task zur Ausführung der jeweiligen Programmsegmente benötigt. Dazu ist es erforderlich, die Ausführung in die jeweils benötigten Pfade zu lenken, die für die Bestimmung des Zeitmodells benötigt werden. Da die Ausführung des Programms von den Eingabedaten abhängig ist, müssen entsprechende Testdatenvektoren für diese Pfade erzeugt werden. Dieses Problem wird mittels einer automatischen Testdatengenerierung gelöst.<br />Diese besteht neben einer Zufallssuche und Heuristik aus der neuartigen Verwendung von Bounded Model Checking für diesen Zweck.<br />Laufzeitmessungen: Die erzeugten Testdaten werden zur Ausführung der benötigten Pfade innerhalb der Programmsegmente verwendet. Die Laufzeiten der Programmsegmente werden durch Instrumentierungen an den Programmsegmentgrenzen ermittelt. Diese Instrumentierungen verändern die Laufzeit nicht oder nur auf vorherbestimmbare Weise.<br />Berechnungsschritt: Aus den gemessenen Laufzeiten wird mittels herkömmlicher WCET Berechnungsmethoden eine sichere WCET Schranke berechnet.<br />

In the last years the number of electronic control systems has increased rapidly. In order to stay competitive, more and more functionality is integrated into an increasing number of powerful and complex computer hardware. Due to these advances in control systems engineering, new challenges for analyzing the timing behaviour of real-time computer systems arise.<br />Resulting from the temporal constraints required for the correct operation of a real-time system, predictability in the temporal domain is a stringent imperative to be satisfied. Therefore, it is necessary to determine the timing behaviour of the tasks running on a real-time computer system. Worst-case execution time (WCET) analysis is the research field investigating methods to assess the timing behaviour of real-time tasks. A central part in WCET analysis is to model the timing behaviour of the target platform. However, manual hardware modelling is a time-consuming and error prone task for each new type of processor hardware. In order to avoid this effort and to address the portability problem in an elegant manner, a new hybrid WCET analysis approach has been developed.<br />Execution time measurements on the instrumented application executable are used to obtain the required hardware timing model. In more detail, the newly introduced measurement-based timing analysis method (MBTA) involves the following steps:<br />Static Analysis: In the first step, static analysis of the C source code allows a concise and safe analysis of the overall program structure. In contrast to common methods working on object code level, this ensures a high level of portability because C is a well established programming language standard in control systems engineering. Additionally, C is also used as output format by code generation tools like Real-Time Workshop (Mathworks Inc.) or TargetLink (dSpace GmbH).<br />Control-Flow Graph Partitioning: In the second step, the method allows to reduce the complexity by means of automatically decomposing the program into custom-size well-manageable subparts called program segments. Test Data Generation: Next, the execution times that a task spends within each of the identified program segments have to be obtained.<br />Therefore, the task's execution has to be guided exhaustively into those paths that are needed for acquiring timing information. Since the taken execution paths depend on the input data to the task, suitable test data vectors that enforce exactly these paths have to be found. This problem is solved by automatic test data generation. Besides random test data vectors and some heuristics, the novel use of bounded model checking for test data generation is introduced.<br />Execution Time Measurements: The generated test data is used to execute the calculated paths within the program segments. The timing information is captured by code instrumentations that are automatically generated and placed at program segment boundaries. The used modifications either do not change the timing behaviour or at least modify it in a predictable way.<br />Calculation Step: The obtained execution times can be safely combined by commonly known methods; thus yielding the overall WCET bound in a final calculation. This calculation step makes use of the structural information acquired in the static analysis step (see above).<br />