Two concrete problems in timing analysis of embedded software

Static timing analysis is crucial for the design of real-time embedded systems. Static analysis methods analyze a program statically to give an upper bound on the worst case execution time (WCET) of the program. The problem of determining WCET of a program by static analysis methods has to be solved at the following two levels (1) Programming language level, to determine the longest path in the program and (2) Micro-architectural level, to take into account the effect of features such as pipeline, cache and branch prediction. At the programming language level it is required to detect the infeasible paths in the program and use that information for giving a tight bound on the WCET of the program. At the micro-architectural level, the presence of caches in a real-time system with multiple tasks, results in additional delay in the execution time of the task due to preemption by a higher priority task. Such delays are called as cache related preemption delay (CRPD). It is important to derive an upper bound on the CRPD for the schedulability analysis of tasks running in a real-time system. In this thesis we present two approaches for static analysis. One tries to model the caches to give a tight bound on the CRPD and the other gives a program path analysis technique to determine the WCET of loops in the program. We further present an approach to reduce the number of paths in the program, such that the complexity of WCET analysis could be reduced.

Author dc:creator

• HEMENDRA SINGH NEGI

• Timing Analysis of Embedded Software