In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a real-time program is addressed. The analysis is focused on straight-line code (i.e. code without loops and recursive function calls) which is quite common

Complete Worst-Case Execution Time Analysis of

Straight-line Hard Real-Time Programs

Friedhelm Stappert, Peter Altenbernd

C-LAB, Fürstenallee 11, D-33095 Paderborn, Germany

Fax: ++49-5251-60-6065

e-mail: {fst, peter}@c-lab.de

Abstract

In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a real-timeprogram is addressed. The analysis is focused on straight-line code (i.e. code without loops and recursive func-tion calls) which is quite commonly found in synthesised code of hard real-time embedded systems. The anal-ysis exploits the very simple structure of these programs, resulting in a considerable processing timeimprovement compared to general-case analysis techniques. A comprehensive timing analysis system, calledthe Program Timing Analyser (PTA), covering low-level aspects (on the assembler instruction level) as well ashigh-level aspects (on the programming language level) is presented.The concepts of PTA are demonstratedwith a detailed example. Also some experimental results are given.

On one hand the low-level analysis covers all speed-up mechanisms used for modern superscalar processors:pipelining, instruction-level parallelism and caching. It can handle a unified cache as well as separate cachesfor data and instructions. The pipelined and parallel execution of assembler instructions is analysed a-priori.Also, the analysis predicts whether memory accesses will hit the caches at run-time.

On the other hand the high-level analysis addresses the problem of using the results from the low-level to com-pute the final estimate on the WCET. This is done by a heuristic for searching the longest really executablepath in the control flow, i.e. by taking into account functional dependencies between various program parts.The heuristic represents a reasonable trade-off between accuracy and effort. By exploiting the simple structureof the input code, no user-annotations are necessary, resulting in a safe and efficient analysis.

Keywords: worst case execution time, cache memory, pipelined execution, hard real-time, longest execut-able path.

1. Introduction

Predicting the worst-case execution time (WCET) of a program is an important task in real-time systemsengineering. The WCET has to be determined for several reasons, e.g. system configuration, schedulabilityanalysis or assuring response times. In order to guarantee the response time of a program, it is useful toknow its WCET, so the cost of the necessary hardware can be minimised. Furthermore, most algorithms forschedulability analysis assume that the maximum execution times of the involved tasks are known [5], [19],

[24]. Hence WCET analysis must be performed in order to guarantee that they will always meet their dead-line. Especially in ahard real-time environment –i.e. an environment where the missing of a deadline willresult in a catastrophic failure– it is important to make safe prognoses about the WCET.

Exact prediction of worst-case execution times is in general impossible, since this would mean solving theundecidable halting problem. Hence the WCET can only be estimated for programs that are known to termi-nate. Nevertheless, the estimation should be as tight as possible: On one hand the WCET must not be under-

– 1 –