Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00)
Using measurements to derive the worst-case execution time
Cheju Island, South Korea
December 12-December 14
ISBN: 0-7695-0930-4
M. Lindgren, Real-Time Res. Centre, Malardalen Univ., Sweden
H. Hansson, Real-Time Res. Centre, Malardalen Univ., Sweden
H. Thane, Real-Time Res. Centre, Malardalen Univ., Sweden
Execution time analysis is used in the development of real time and embedded systems to derive the timing estimates required for schedulability analysis. The execution time of the analyzed program is typically obtained by combining results from program flow analysis (such as number of iterations in loops) with low level timing information. The paper proposes a method for low level timing analysis based on measurements of execution times of programs executing on the actual target architecture. The essence of the method is to derive a system of linear equations from a limited number of timing measurements of an instrumented version of the considered program. The solution to these equations give execution times for program fragments, from which execution time measures for the entire program can be derived. The main advantage with this approach is that architectural modeling is not needed, hence the risk of a discrepancy between model and real system is avoided. Also, compared to the non-exhaustive measurements performed in industry today, our approach is more structured and gives complete coverage in terms of the program paths considered. We present our method in the context of a simple, but reasonably realistic processor model and show how it can be extended to architectures with pipelines.
Index Terms:
real-time systems; program diagnostics; scheduling; flow graphs; pipeline processing; worst-case execution time; execution time analysis; embedded systems; timing estimates; schedulability analysis; program flow analysis; low level timing information; low level timing analysis; program execution times; target architecture; system of linear equations; timing measurements; instrumented version; program fragments; architectural modeling; non-exhaustive measurements; program paths; realistic processor model; pipeline architectures; real time systems
Citation:
M. Lindgren, H. Hansson, H. Thane, "Using measurements to derive the worst-case execution time," rtcsa, pp.15, Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00), 2000