[ main page ] [ back ]

2003 : Experimental Assessment of Worst-Case Program Execution Times

Author(s)
Pavel Atanassov
Abstract
Real-time systems are subject to timing constraints. The tasks of a real-time system must execute within predefined time intervals in order to meet their deadlines. Missing a deadline can lead to malfunction of the whole system, which can have disastrous effects, and may even mean the loss of human lives. Real-time systems must, therefore, be both functionally and temporally correct.
The knowledge of the Worst-Case Execution Time (WCET) of the tasks of a real-time system is crucial for the validation of the temporal correctness of the system. An upper bound on the WCET of each task must be provided, representing a safe estimate of the actual WCET. The WCET estimates are used to demonstrate that the deadlines will be met, as well as to guide scheduling decisions, and to allocate resources. WCET estimates should also be tight, i.e., the overestimation of the actual WCET should be kept reasonable, in order to construct a feasible temporal schedule for the system. Tight estimates enable a better utilization of the resources, and can reduce the overall costs of the real-time system.
In recent years, the method of static WCET analysis has been developed by researchers from academia to establish an analytical approach to the problem of obtaining estimates of the WCET of real-time programs. Static WCET analysis produces an upper bound on the WCET of a program statically, i.e., without ever executing the program. To this end, the source code of the program is analyzed to determine the possible control-flow paths, and the temporal behavior of the target hardware is modeled in order to estimate the low-level instruction execution times. The analysis then identifies the program execution path that yields the longest execution time, i.e., the WCET of the program.
Static WCET analysis has proved to be a powerful and flexible method to yield WCET bounds. Still, it is hard to convince industry partners to deploy static WCET analysis tools instead of the more primitive and expensive approaches currently used. This is mainly due to the lack of clear evidence, that a particular WCET tool is indisputably relevant to the target hardware, and that its WCET estimates are really safe and sufficiently tight.
This thesis substantiates sufficient confidence in the results of static WCET analysis and the results of a static WCET analysis tool for a particular target hardware, the Infineon C167CR microcontroller. This is performed by experimental assessment of execution times on real hardware. The main outcome of the thesis is an accurate timing model of the target hardware, and the successful validation of the results of a WCET analysis tool based on the created timing model. It is demonstrated that the WCET estimates made by the tool are always safe compared to actual execution times measured on real hardware, and that the estimates are tight enough their overestimation is always below 5%. A further contribution of the thesis is the assessment of the impact of DRAM refresh cycles on the execution time and execution-time analysis of real-time programs.
Bibtex
@phdthesis{ atanassov:2003,
  author =      "Pavel Atanassov",
  title =       "Experimental Assessment of Worst-Case Program Execution Times",
  address =     "Treitlstr. 3/3/182-1, 1040 Vienna, Austria",
  school =      "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  year =        "2003"
}
Download
Get Diss_Atanassov_Pavel.pdf - Adobe PDF-format, (3106.4277 KB; posted at July 09 2013)


[ main page ] [ back ]