35 research outputs found
WCET Analysis: The Annotation Language Challenge
No full textWorst-case execution time (WCET) analysis is indispensable for the successful design and development
of systems, which, in addition to their functional constraints, have to satisfy hard real-time constraints. The
expressiveness and usability of annotation languages,
which are used by algorithms and tools for WCET analysis in order to separate feasible from infeasible program paths, have a crucial impact on the precision
and performance of these algorithms and tools. In
this paper, we thus propose to complement the WCET
tool challenge, which has recently successfully been
launched, by a second closely related challenge: the
WCET annotation language challenge. We believe that
contributions towards mastering this challenge will be
essential for the next major step of advancing the field
of WCET analysis
Measurement-based timing analysis of superscalar processors
No full textIn 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.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.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: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.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.Diese besteht neben einer Zufallssuche und Heuristik aus der neuartigen Verwendung von Bounded Model Checking für diesen Zweck.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.Berechnungsschritt: Aus den gemessenen Laufzeiten wird mittels herkömmlicher WCET Berechnungsmethoden eine sichere WCET Schranke berechnet.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.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.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: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).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.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.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.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 /
Measurement-Based Timing Analysis
No full textIn this paper we present a measurement-based worst-case execution time (WCET) analysis method. Exhaustive end-to-end execution-time measurements are computationally intractable in most cases. Therefore, we propose to measure execution times of subparts of the application code and then compose these times into a safe WCET bound.
This raises a number of challenges to be solved. First, there is the question of how to define and subsequently calculate adequate subparts. Second, a huge amount of test data is required enforcing the execution of selected paths to perform the desired runtime measurements.
The presented method provides solutions to both problems. In a number of experiments we show the usefulness of the theoretical concepts and the practical feasibility by using current state-of-the-art industrial case studies from project partners.
This work has been supported by the FIT-IT research project "Model-based Development of Distributed Embedded Control Systems (MoDECS)"
Interface Design for Hardware-in-the-Loop Simulation
No full textThis paper presents a scalable approach to interface between a time-triggered distributed hardware-in-the-loop (HIL) simulator and the system under test (SUT) via Smart Virtual Transducers (SVTs). An SVT is an element of an HIL simulator and implements two interfaces -- a standardized digital interface to a time-triggered transducer network and a transducer-specific interface.
The main contribution of the approach is a separation of the execution of the simulation model and the deterministic interaction via an arbitrary transducer interface. The benefit of such separation is the temporal decoupling between simulation model execution and interaction with the SUT. Furthermore, the approach leads to a reduction of complexity of the simulation setup.
The application of the approach is shown by an SVT prototype that is used to simulate a temperature sensor
Using Model Checking to Derive Loop Bounds of General Loops within ANSI-C Applications for Measurement Based WCET Analysis
No full textKnowing the boundaries of loops is an important prerequisite for both, static and dynamic Worst Case Execution Time (WCET) analysis. However, loop bound calculation is a complex task of its own, and often more effort than planned has to be put into it. This paper describes a simple and quick method for loop bound calculation using a model checker that cannot only find loop bounds for integer iterator variables but works with practically all kind of loops
Using model checking to derive loop bounds of general loops within ANSI-C applications for measurement based WCET analysis
No full textPrinciples of Timing Anomalies in Superscalar Processors
No full textThe counter-intuitive timing behavior of certain features in superscalar processors that cause severe problems for existing worst-case execution time analysis (WCET) methods is called timing anomalies. In this paper, we identify structural sources potentially causing timing anomalies in superscalar pipelines. We provide examples for cases where timing anomalies can arise in much simpler hardware architectures than commonly supposed (i.e., even in hardware containing only in-order functional units).We elaborate the general principle behind timing anomalies and propose a general criterion (resource allocation criterion) that provides a necessary (but not sufficient) condition for the occurrence of timing anomalies in a processor. This principle allows to state the absence of timing anomalies for a specific combination of hardware and software and thus forms a solid theoretic foundation for the time-predictable execution of real-time software on complex processor hardware
