[ main page ] [ back ]

2006 : Measurement-Based Timing Analysis of Superscalar Processors

Author(s)
Ingomar Wenzel
Abstract
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 laced 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 alculation step makes use of the structural information acquired in the static analysis step (see above).
Bibtex
@phdthesis{ wenzel:2006,
  author =      "Ingomar Wenzel",
  title =       "Measurement-Based Timing Analysis of Superscalar Processors",
  address =     "Treitlstr. 3/3/182-1, 1040 Vienna, Austria",
  school =      "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  year =        "2006"
}
Download
Get abgegeben.pdf - Adobe PDF-format, (5877.8818 KB; posted at July 09 2013)


[ main page ] [ back ]