«Faculty of Computer Science Chair for Real Time Systems Diploma Thesis Timing Analysis in Software Development Author: Martin Däumler Supervisors: ...»
Faculty of Computer Science
Chair for Real Time Systems
Timing Analysis in Software Development
Author: Martin Däumler
Supervisors: Jun.-Prof. Dr.-Ing. Robert Baumgartl
Dr.-Ing. Andreas Zagler
Date of Submission: March 31, 2008
Timing Analysis in Software Development
Diploma Thesis, Chemnitz University of Technology, 2008
Rapid development processes and higher customer requirements lead to increasing integration of software solutions in the automotive industry’s products. Today, several electronic control units communicate by bus systems like CAN and provide computation of complex algorithms. This increasingly requires a controlled timing behavior.
The following diploma thesis investigates how the timing analysis tool SymTA/S can be used in the software development process of the ZF Friedrichshafen AG. Within the scope of several scenarios, the beneﬁts of using it, the difﬁculties in using it and the questions that can not be answered by the timing analysis tool are examined.
Contents List of Figures iv List of Tables vi 1 Introduction 1 2 Execution Time Analysis 3
2.1 Preface................................... 3
2.2 Dynamic WCET Analysis......................... 4 2.2.1 Methods.............................. 4 2.2.2 Problems.............................. 4
2.3 Static WCET Analysis........................... 6 2.3.1 Methods.............................. 6 2.3.2 Problems.............................. 7
2.4 Hybrid WCET Analysis........................... 9
2.5 Survey of Tools: State of the Art...................... 9 2.5.1 aiT................................. 9 2.5.2 Bound-T...............
3.14 SymTA/S asynchronous FlexRay-communication Gantt-chart....... 55
3.15 SymTA/S synchronous FlexRay-communication Gantt-chart....... 57
3.16 SymTA/S resource speed sensitivity analysis................ 58
3.17 SymTA/S jitter dependency diagram.................... 58
3.18 SymTA/S design space exploration loop.................. 59
3.19 SymTA/S scenario 1: system model.................... 62
3.20 SymTA/S scenario 1: observed paths using task execution times derived from hardware-traces............................ 62
3.21 SymTA/S scenario 1: observed paths using process execution times derived from hardware-traces......................... 64
3.22 SymTA/S scenario 1: observed paths using process execution times measured by INCA............................... 65
3.23 SymTA/S scenario 1: Gantt-chart of the 10ms-task’s critical instant leading to its WCRT (the white bubbles are the task’s processes)....... 65
3.24 SymTA/S scenario 1: sensitivity analysis results with WCRT constraint of 8000 µs for the 10ms-task (from report ﬁle RPF05)............ 68
3.25 SymTA/S scenario 2: system model, the surrounded area represents the new functionality to be investigated.................... 72
3.26 SymTA/S scenario 2: cycle Gantt-chart extract which does not display all blocking CAN-frames due to readability reasons.............. 75
3.27 SymTA/S scenario 2: cycle WCRT using First Through semantic (the ﬁrst WCRT does not take the delay determined by SymTA/S between frame_8 and the 10ms-task on OSEK-ECU0 into account)............. 76
3.28 SymTA/S scenario 2: sensitivity analysis results for First Through and Maximum Age semantic........................... 77
3.29 SymTA/S scenario 2: processor utilization after assigning the maximum WCET to the 10ms-task on OSEK-ECU0 that is determined by sensitivity analysis using the First Through semantic................. 77
3.30 SymTA/S scenario 2: end-to-end path Gantt-chart extract from scheduling analysis with optimized conﬁguration First Through semantic (blocking CAN-frames are not displayed due to readability reasons)......... 80
3.31 SymTA/S scenario 2: Gantt-chart extract where the maximum WCET of the 10ms-task on OSEK-ECU0 is assigned to it while using the optimized system conﬁguration and First Through semantic (blocking CAN-frames are not displayed due to readability reasons)................ 81
3.32 SymTA/S scenario 2: Gantt-chart extract where a WCET of the 10ms-task on OSEK-ECU0 is assigned to it that is greater than the maximum possible while using the optimized system conﬁguration and First Through semantic (blocking CAN-frames are not displayed due to readability reasons).. 81
4.1 Example of a chronSim task model with speciﬁed execution times and operating system system calls (from chronSim presentation material)... 87
2.1 WCETs determined by aiT for TriCore v2.0 build 73031, values in brackets are determined by using the annotation snippet "sub-function5" is never executed; (mb = manually build, sb = small binary, bb = big binary) 23
2.2 Summary of the obtained WCETs using different methods respectively tools 31
3.1 SymTA/S scenario 1: WCRTs resulting from design space exploration, values in brackets results from rounded activation offsets (compare with initial system conﬁguration (ﬁgure 3.22), ∑ WCRT: 1030960.23 µs)... 69
3.2 SymTA/S scenario 2: activation offset optimization results for OSEK-ECU0 79 vi 1 Introduction Nowadays, one can not imagine modern vehicles without microcontrollers controlling the engine, transmission, safety relevant systems like electronic brake or comfort features like power window lifts. Several Electronic Control Units (ECUs) are networked by several bus system like CAN (Controller Area Network) , FlexRay  or LIN (Local Interconnect Network) . Especially for safety relevant systems a well known timing behavior is necessary.
AUTOSAR  is the result of efforts that are made to develop an open and standardized system architecture for the automotive industry. Due to the lack of modeling timing issues, the TIMMO (Timing Model) project  was created in April 2007 in order to investigate methods to handle timing information of embedded real-time systems.
The timing analysis tool SymTA/S by Symta Vision  is a scheduling analyzer customized for automotive industry. It provides end-to-end analysis as well as an optimization function and a sensitivity analysis. In order to evaluate SymTA/S for ZF Friedrichshafen AG  (ZF in the following), three scenarios will be examined which investigate an efﬁcient way of integrating the timing analysis tool in the software development process (V-Model , see ﬁgure 1.1) of ZF. The ﬁrst scenario is the timing analysis of an existing
ECU. Second, the analysis of function expansion on an ECU and the distribution of functions to several ECUs considering the communication between. The last scenario is about 1 INTRODUCTION analyzing how the tool can help to give a timing budget early in the development process.
For each scenario, it has to be examined how to get the necessary input and put it into the tool as efﬁcient as possible, which improvements in optimization and efﬁciency the tool provides, when it can be used in development and which problems can not be solved with the tool.
The remainder of this thesis is organized as follows: Chapter 2 describes several methods to gain (worst-case) execution times from code used in software development of ZF.
Chapter 3 describes SymTA/S internals and investigates the named use scenarios. Chapter 4 describes another timing analysis tool, chronSim. Chapters 5 and 6 complete this work with an outlook of further work respectively a recapitulating conclusion.
2 Execution Time Analysis
2.1 Preface A crucial input for timing analysis with a tool like SymTA/S is the worst-case execution time (WCET) of the software that is investigated. The WCET is the longest execution time of code that runs on particular hardware given a particular input. Thus, the input has to be considered as well as the hardware behavior. This chapter should be considered as general overview of several analysis methods and their problems, independent from a speciﬁc timing tool fed with this values.  gives an extensive summary.
For safety relevant systems, very precise results are necessary in order to guarantee the timing behavior of such a system. So, a given WCET has to be safe, i.e. above or equal to the real WCET, and tight, i.e. close to the real WCET. Figure 2.1 illustrates the WCET problem. It is desirable to determine the WCET of code efﬁciently early in development.
This would help to detect timing problems as early as possible. There are two WCET analysis approaches: the measurement-based approach called dynamic analysis and the static analysis.
2 EXECUTION TIME ANALYSIS
2.2 Dynamic WCET Analysis 2.2.1 Methods The measurement-based determination of the WCET is widespread in industrial settings [22, p. 2]. The execution time of the binary code on the target is measured for several inputs. In general, each input leads to the execution of one certain path through the code.
The execution time of this path is measured.
There are several measurement methods which can be divided into hardware-based and software-based ones [22, p. 2]. Hardware-based methods use amongst others an oscilloscope, logic analyzer or in-circuit emulator, see ﬁgure 2.2. [22, p. 5] describes that the
Figure 2.2: Tools for dynamic execution time-analysis, from [22, p. 3]
oscilloscope has a labor-intensive setup and the source code has to be instrumented in order to take a certain path through the code. The logical analyzer listens to the address-bus and records a trace of the accessed addresses along with time stamps. Another possibility is to use an in-circuit emulator. It also records traces and provides non-intrusive execution time measuring depending on its features.
Software-based methods comprise amongst others timing measurement functions provided by the operating system, a cycle-accurate simulator or the instrumentation of the source code with timing measurement code that runs on the target. A cycle-accurate simulator has the advantage that it could be installed on the software developer’s host system and therefor could be used for measurement early in the implementation phase without the need to perform the test on the target hardware.
2.2.2 Problems In order to measure the WCET, the input for the path that leads to the longest execution time has to be known. If the code is very complex, i.e. it is a black-box, this WCET input often is unknown. Measuring the code with all possible inputs usually is infeasible due to the huge state space when there are many input parameters with a wide range. Therefor, often only a subset of all possible inputs is measured. So, one risks not measuring the worst-case input. The complexity might be reduced by using a divide-and-conquer strategy similar to unit-testing , e.g. measuring each single function separated from the
2.2 DYNAMIC WCET ANALYSIS
whole system and hence testing a straightforward amount of test inputs. This requires system knowledge and black-box testing seems not to be suitable, see section 2.6. The global WCET has to be calculated sophistically on the basis of the measured local WCETs.
The execution times of the processes are case-sensitive, e.g. the worst-case input might exclude the simultaneous occurrence of the WCET of several functions or no function of the software has its WCET in this situation. However, this worst-case input respectively this worst-case situation is unknown in general, e.g. if the software is a black-box. Therefor, using the divide-and-conquer approach and calculating the global WCET by simply adding local ones assumably leads to a safe but pessimistic global WCET.
Additionally, there are interdependencies of the code on hardware level. Interdependencies can be caused by features of modern CPUs like multi-level caches with a certain replacement policy, translation look-aside buffer (TLB) entries for memory protection or even virtual memory, pipelines, superscalarity with out-of-order execution, (speculative) branch prediction and maybe even multiple cores. So, the worst initial state of the hardware for each measurement has to be known, otherwise possibly yielding a too optimistic result. However, this worst initial state is case-sensitive, i.e. it depends on the code executed before. Regarding and measuring the system as a whole implicitly takes these issues into account but often brakes down on the complexity which causes more test cases than feasible.
A further problem is that instrumenting the source code with measurement code affects the timing behavior of the whole system, e.g. by changing the cache contents and extra execution time. When storing the execution time of each process in a separate variable, the number of measured processes is implicitly limited to the available memory. Unfortunately, memory is short in embedded systems. The more precise the measurement software is, i.e. it ﬁlters interruptions, the more overhead it has the more it affects the timing behavior of the system. Besides this, the operating system also might inﬂuence the execution time because it also uses the hardware.
Code, e.g. a process or a task, that runs on a system might be interrupted by higher priority tasks or interrupts. This duration could be calculated by more complex measurement code that is added to the source code. In embedded systems, this method is not a suitable solution due to the hardware restrictions and disabling interrupts is not always possible.