The determination of upper bounds on execution times, commonly called worst-case execution times (WCETs), is a necessary step in the development and validation process for hard real-time systems. This problem is hard if the underlying processor architecture has components, such as caches, pipelines, branch prediction, and other speculative components. This article describes different approaches to this problem and surveys several commercially available tools 1 and research prototypes.

Upper bounds on worst-case execution times, which are commonly called WCET, are a prerequisite for validating the temporal correctness of tasks in a real-time system. Due to the execution history sensitive behavior of components like caches, pipelines, buffers and periphery, the static determi-nation of safe upper execution-time bounds is a challenging task.A successful timing analysis approach developed at Saarland University/AbsInt GmbH uses abstract interpretation to derive safe WCET bounds based on timing models of the processor and periphery in a system. So far, WCET research has focused on processor timing behavior. System performance depends heavily on the performance of the periphery, namely the system controller, which includes the memory access logic. This paper is the first to describe experience in deriving a timing model for such a system con-troller. The starting point is the VHDL description from which the controllers FPGA implementation is synthesized. By a sequence of simplifications and abstractions we obtain an abstract VHDL model which can be translated easily into a timing model.The evaluation of the derived WCET tool shows that the approach leads to a precise and efficient analysis. This opens up the perspective of automatically deriving timing models from VHDL descriptions also for processors.

Hard real-time avionics systems like flight control software are expected to always react in time. Consequently, it is essential for the timing validation of the software that the worst-case execution time (WCET) of all tasks on a given hardware configuration be known. Modern processor components like caches, pipelines, and branch prediction complicate the determination of the WCET considerably since the execution time of a single instruction may depend on the execution history. The safe, yet overly pessimistic assumption of no cache hits, no overlapping executions in the processor pipeline, and constantly mispredicted branches results in a serious overestimation of the WCET. Our approach to WCET prediction was implemented for the Motorola ColdFire 5307. It includes a static prediction of ∗ This work was partly supported by the RTD project IST-1999-20527 “DAEDALUS” of the European FP5 program. cache and pipeline behavior, producing much tighter upper bounds for the execution times. The WCET analysis tool works on real applications. It is safe in the sense that the computed WCET is always an upper bound of the real WCET. It requires much less effort, while producing more precise results than conventional measurement-based methods.

The architecture of tools for the determination of worst case execution times (WCETs) as well as the precision of the results of WCET analyses strongly depend on the architecture of the employed processor. The cache replacement strategy influences the results of cache behavior prediction; out-of-order execution and control speculation introduce interferences between processor components, e.g., caches, pipelines, and branch prediction units. These interferences forbid modular designs of WCET tools, which would execute the subtasks of WCET analysis consecutively. Instead, complex integrated designs are needed, resulting in high demand for memory space and analysis time. We have implemented WCET tools for a series of increasingly complex processors: SuperSPARC, Motorola ColdFire 5307, and Motorola PowerPC 755. In this paper, we describe the designs of these tools, report our results and the lessons learned, and give some advice as to the predictability of processor architectures.