Integrating Path and Timing Analysis using Instruction-Level Simulation Techniques

Abstract

Previously published methods for estimation of the worst-case execution time on contemporary processors with complex pipelines and multi-level memory hierarchies result in overestimations owing to insufficient path and/or timing analysis. This not only gives rise to poor utilization of processing resources but also reduces the schedulability in real-time systems.

This paper presents a new method that integrates path and timing analysis to address these limitations. First, it is based on instruction-level architecture simulation techniques and thus has a potential to perform arbitrarily detailed timing analysis of hardware platforms. Second, by extending the simulation technique with the capability of handling unknown input data values, it is possible to exclude infeasible (or false) program paths in many cases, and also calculate path information, such as bounds on number of loop iterations, without the need for annotating the programs. Finally, in order to keep the number of program paths to be analyzed at a manageable level, we have extended the simulator with a path-merging strategy. This paper presents the method and particularly focuses on its path and timing analysis capabilities. It does this in the context of pipelined processors employing instruction and data caches.

Keywords

Real-time systems, timing analysis, path analysis, architecture simulation, worst-case execution time.

This report is a preliminary version of the conference paper with the same name.

Download copy:

• archsim_a4.ps (732 KB)
• archsim_letter.ps (732 KB)

• archsim_a4.ps.gz (179 KB)
• archsim_letter.ps.gz (179 KB)