Thomas Lundqvist - Licentiate Thesis

Abstract

When constructing high-performance real-time systems, safe and tight estimations of the worst case execution time (WCET) of programs run on pipelined processors with caches are needed. To obtain tight estimations both path and timing analyses need to be done. Path analysis is responsible for eliminating infeasible paths in the program and timing analysis is responsible for accurately modeling the timing behavior of dynamically scheduled processors employing pipelining and caching.

This thesis presents a new method, based on cycle-level symbolic execution, that combines path and timing analyses for programs on high-performance processors. An implementation of the method has been used to estimate the WCET for a suite of programs running on a high-performance processor. The results show that by using a combined analysis, the overestimation is significantly reduced compared to previously published methods. The method automatically eliminates infeasible paths and derives path information such as loop bounds, and performs accurate timing analysis for a multiple-issue processor with an instruction and data cache. The thesis also identifies timing anomalies in dynamically scheduled processors. These anomalies invalidate the basic assumption made in previously published timing analysis methods: that the maximum instruction execution time represents the worst-case behavior. To handle these anomalies, a method based on program modifications is suggested that makes it possible to safely use all previously published timing analysis methods even for architectures where timing anomalies can occur. Finally, the use of data caching in real-time systems is examined. For data caching to be fruitful, data accesses must be predictable when estimating the WCET. The results from an empirical study show that many accesses are indeed predictable. Thus, data caching can be expected to be efficient in real-time systems.

Keywords

Real-time systems, worst-case execution time, timing analysis, path analysis, symbolic execution, multiple-issue, pipeline, caches, timing anomaly, dynamically scheduled processor.

Download copy:

• lic_tot_a4.pdf (559 KB)