453 Works

WCET 2007 Abstracts Collection -- 7th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis

Christine Rochange
The workshop on Worst-Case Execution Time Analysis is a satellite event to the annual Euromicro Conference on Real-Time Systems. It brings together people that are interested in all aspects of timing analysis for real-time systems. In the 2007 edition, 13 papers were presented, organized into four sessions: methods for WCET computation, low-level analysis, system-level analysis and flow-analysis. The workshop was also the opportunity to report from the 2006 WCET tool challenge.

Merging Techniques for Faster Derivation of WCET Flow Information using Abstract Execution

Jan Gustafsson & Andreas Ermedahl
Static Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component in static WCET analysis is to derive flow information, such as loop bounds and infeasible paths. We have previously introduced abstract execution (AE), a method capable of deriving very precise flow information. This paper present different merging techniques that can be used by AE for trading analysis...

Analysis of path exclusion at the machine code level

Ingmar Stein & Florian Martin
We present a method to find static path exclusions in a control flow graph in order to refine the WCET analysis. Using this information, some infeasible paths can be discarded during the ILP-based longest path analysis which helps to improve precision. The new analysis works at the assembly level and uses the Omega library to evaluate Presburger formulas.

Analysing Switch-Case Tables by Partial Evaluation

Niklas Holsti
Tracing the flow of control in code generated from switch-case statements is difficult for static program analysis tools when the code contains jumps to dynamically computed target addresses. Analytical methods such as abstract interpretation using integer intervals can work for some forms of switchcase code, for example a jump via a table of addresses indexed 1 .. n, but fail when the target compiler encodes the switch-case structure in a ROM table with a complex...

WCET 2007 -- Report from the WCET Tool Challenge 2006 Ideas for the WCET Tool Challenge 2008

Jan Gustafsson
The purpose of the WCET Tool Challenge is to be able to study, compare and discuss the properties of different WCET tools and approaches, to define common metrics, and to enhance the existing benchmarks. The WCET Tool Challenge has been designed to find a good balance between openness for a wide range of analysis approaches, and specific participation guidelines to provide a level playing field. This should make results transparent and facilitate friendly competition among...

WCET Analysis: The Annotation Language Challenge

Raimund Kirner, Jens Knoop, Adrian Prantl, Markus Schordan & Ingomar Wenzel
Worst-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...

Timing Analysis of Body Area Network Applications

Liang Yun, Abhik Roychoudhury & Tulika Mitra
Body area network (BAN) applications have stringent timing requirements. The timing behavior of a BAN application is determined not only by the software complexity, inputs, and architecture, but also by the timing behavior of the peripherals. This paper presents systematic timing analysis of such applications, deployed for health-care monitoring of patients staying at home. This monitoring is used to achieve prompt notification of the hospital when a patient shows abnormal vital signs. Due to the...

Finding DU-Paths for Testing of Multi-Tasking Real-Time Systems using WCET Analysis

Daniel Sundmark, Anders Petterson, Christer Sandberg, Andreas Ermedahl & Henrik Thane
Memory corruption is one of the most common software failures. For sequential software and multi- tasking software with synchronized data accesses, it has been shown that program faults causing memory cor- ruption can be detected by analyzing the relations be- tween defines and uses of variables (DU-based testing). However, such methods are insufficient in preemptive systems, since they lack the ability to detect inter-task shared variable dependencies. In this paper, we propose the use of...

Data-Flow Based Detection of Loop Bounds

Christoph Cullmann & Florian Martin
To calculate the WCET of a program, safe upper bounds on the number of loop iterations for all loops in the program are needed. As the manual annotation of all loops with such bounds is difficult and time consuming, the WCET analyzer aiT originally developed by Saarland University and AbsInt GmbH uses static analysis to determine the needed bounds as far as possible. This paper describes a novel data-flow based analysis for aiT to calculate...

Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis

Andreas Ermedahl, Christer Sandberg, Jan Gustafsson, Stefan Bygde & Björn Lisper
Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for static derivation of precise WCET estimates is upper bounds on the number of times different loops can be iterated. In this paper we present an approach for deriving upper loop bounds based on a combination of standard program analysis techniques. The idea...

Automatic Amortised Worst-Case Execution Time Analysis

Christoph A. Herrmann, Armelle Bonenfant, Kevin Hammond, Steffen Jost, Hans-Wolfgang Loidl & Robert Pointon
Our research focuses on formally bounded WCET analysis, where we aim to provide absolute guarantees on execution time bounds. In this paper, we describe how amortisation can be used to improve the quality of the results that are obtained from a fully-automatic and formally guaranteed WCET analysis, by delivering analysis results that are parameterised on specific input patterns and which take account of relations between these patterns. We have implemented our approach to give a...

Measurements or Static Analysis or Both?

Stefan M. Petters, Patryk Zadarnowski & Gernot Heiser
To date, measurement-based WCET analysis and static analysis have largely been seen as being at odds with each other. We argue that instead they should be considered complementary, and that the combination of both represents a promising approach that provides benefits over either individual approach. In this paper we discuss in some detail how we aim to improve on our probabilistic measurement-based technique by adding static cache analysis. Specifically we are planning to make use...

A Framework for Static Analysis of VHDL Code

Marc Schlickling & Markus Pister
Software in real time systems underlies strict timing constraints. These are among others hard deadlines regarding the worst-case execution time (WCET) of the application. Thus, the computation of a safe and precise WCET is a key issue1 for validating the behavior of safety-critical systems, e.g. the flight control system in avionics or the airbag control software in the automotive industry. Saarland University and AbsInt Angewandte Informatik GmbH have developed a successful approach for computing the...

Towards Symbolic State Traversal for Efficient WCET Analysis of Abstract Pipeline and Cache Models

Stephan Wilhelm & Björn Wachter
Static program analysis is a proven approach for obtaining safe and tight upper bounds on the worst-case execution time (WCET) of program tasks. It requires an analysis on the microarchitectural level, most notably pipeline and cache analysis. In our approach, the integrated pipeline and cache analysis operates on sets of possible abstract hardware states. Due to the growth of CPU complexity and the existence of timing anomalies, the analysis must handle an increasing number of...

2006 WCET Preface -- Proceedings of the 6th Intl. Workshop on Worst-Case Execution Time Analysis (WCET'06)

Frank Mueller
On the 4th of July, 2006, the 6th International Workshop onWorst-Case Execution Time Analysis (WCET'06) was held in Dresden, Germany, co-located with the 18th Euromicro International Conference on Real-Time Systems (ECRTS'06), both with support of Euromicro Technical Committee. The goal of the workshop was to bring together people from academia, tool vendors and users in industry that are interested in all aspects of timing analysis for real-time systems. The workshop provided a relaxed forum to...

2006 WCET Abstracts Collection -- 6th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis

Frank Mueller
On the 4th of July, 2006, the 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06) was held in Dresden, Germany, co-located with the 18th Euromicro International Conference on Real-Time Systems (ECRTS'06), both with support of Euromicro Technical Committee. The goal of the workshop was to bring together people from academia, tool vendors and users in industry that are interested in all aspects of timing analysis for real-time systems. The workshop provided a relaxed forum...

Clustering Worst-Case Execution Times for Software Components

Johan Fredriksson, Thomas Nolte, Andreas Ermedahl & Mikael Nolin
For component-based systems, classical techniques for Worst-Case Execution Time (WCET) estimation produce unacceptable overestimations of a componentsWCET. This is because software components more general behavior, required in order to facilitate reuse. Existing tools and methods in the context of Component-Based Software Engineering (CBSE) do not yet adequately consider reusable analyses. We present a method that allows different WCETs to be associated with subsets of a components behavior by clustering WCETs with respect to behavior. The...

Towards Formally Verifiable WCET Analysis for a Functional Programming Language

Kevin Hammond, Christian Ferdinand, Reinhold Heckmann, Roy Dyckhoff, Martin Hofman, Steffen Jost, Hans-Wolfgang Loidl, Greg Michaelson, Robert Pointon, Norman Scaife, Jocelyn Sérot & Andy Wallace
This paper describes ongoing work aimed at the construction of formal cost models and analyses to yield verifiable guarantees of resource usage in the context of real-time embedded systems. Our work is conducted in terms of the domain-specific language Hume, a language that combines functional programming for computations with finitestate automata for specifying reactive systems. We outline an approach in which high-level information derived from source-code analysis can be combined with worst-case execution time information...

A Framework for the Busy Time Calculation of Multiple Correlated Events

Simon Schliecker, Matthias Ivers, Jan Staschulat & Rolf Ernst
Many approaches to determine the response time of a task have difficulty to model tasks with multiple memory or coprocessor accesses with variable access times during the execution. As the request times highly depend on system setup and state, they can not be trivially bounded. If they are bounded by a constant value, large discrepancies between average and worst case make the focus on single worst cases vulnerable to overestimation. We present a novel approach...

PapaBench: a Free Real-Time Benchmark

Fadia Nemer, Hugues Cassé, Pascal Sainrat, Jean-Paul Bahsoun & Marianne De Michiel
This paper presents PapaBench, a free real-time benchmark and compares it with the existing benchmark suites. It is designed to be valuable for experimental works in WCET computation and may be also useful for scheduling analysis. This bench is based on the Paparazzi project that represents a real-time application, developed to be embedded on different Unmanned Aerial Vehicles (UAV). In this paper, we explain the transformation process of Paparazzi applied to obtain the PapaBench. We...

Combining Symbolic Execution and Path Enumeration in Worst-Case Execution Time Analysis

Djemai Kebbal & Pascal Sainrat
his paper examines the problem of determining bounds on execution time of real-time programs. Execution time estimation is generally useful in real-time software verification phase, but may be used in other phases of the design and execution of real-time programs (scheduling, automatic parallelizing, etc.). This paper is devoted to the worst-case execution time (WCET) analysis. We present a static WCET analysis approach aimed to automatically extract flow information used in WCET estimate computing. The approach...

PLRU Cache Domino Effects

Christoph Berg
Domino effects have been shown to hinder a tight prediction of worst case execution times (WCET) on real-time hardware. First investigated by Lundqvist and Stenström, domino effects caused by pipeline stalls were shows to exist in the PowerPC by Schneider. This paper extends the list of causes of domino effects by showing that the pseudo LRU (PLRU) cache replacement policy can cause unbounded effects on the WCET. PLRU is used in the PowerPC PPC755, which...

Design of a WCET-Aware C Compiler

Heiko Falk, Paul Lokuciejewski & Henrik Theiling
This paper presents techniques to tightly integrate worst-case execution time information into a compiler framework. Currently, a tight integration of WCET information into the compilation process is strongly desired, but only some ad-hoc approaches have been reported currently. Previous publications mainly used self-written WCET estimators with very limited functionality and preciseness during compilation. A very tight integration of a high quality industry-relevant WCET analyzer into a compiler was not yet achieved up to now. This...

Loop Nest Splitting for WCET-Optimization and Predictability Improvement

Heiko Falk & Martin Schwarzer
This paper presents the influence of the loop nest splitting source code optimization on the worst-case execution time (WCET). Loop nest splitting minimizes the number of executed if-statements in loop nests of embedded multimedia applications. Especially loops and if-statements of high-level languages are an inherent source of unpredictability and loss of precision for WCET analysis. This is caused by the fact that it is difficult to obtain safe and tight worst-case estimates of an application's...

Comparing WCET and Resource Demands of Trigonometric Functions Implemented as Iterative Calculations vs. Table-Lookup

Raimund Kirner, Markus Grössing & Peter Puschner
Trigonometric functions are often needed in embedded real-time software. To fulfill concrete resource demands, different implementation strategies of trigonometric functions are possible. In this paper we analyze the resource demands of iterative calculations compared to other implementation strategies, using the trigonometric functions as a case study. By analyzing the worst-case execution time (WCET) of the different calculation techniques of trigonometric functions we got the surprising result that the WCET of iterative calculations is quite competitive...

Registration Year

  • 2010

Resource Types

  • Text

Data Centers

  • Dagstuhl