A Tool for the Computation of Worst Case Task Execution Times

P. Puschner and A. Schedl

Institut f?ur Technische Informatik

Technical University of Vienna

Vienna, A-1040 Austria

Abstract

In modern programming environments for real-time software the presence of task timing analysis tools has become state of the art. Upon the results produced by these tools programmers judge whether software being developed meets the specified timing requirements. In this paper we present a new task timing analysis tool for MARS. This tool not only allows to compute worst case execution time bounds of high quality. It also produces detailed information about the extent to which every statement contributes to this bound and allows to experiment with hypothetical times. These properties of the timing analysis tool allow to make execution time information an integral part of the entire programming process.

1 Introduction

One of the central parameters in the design and implementation of predictable real-time applications is the maximum execution time (MAXT) of the tasks involved. During the design estimates for the MAXTs of tasks are used to make feasibility studies, to determine the needed resources, to plan the timing of interactions between tasks, and to allocate tasks to processing units. In the implementation phase, these estimates become time budgets that have to be met by the tasks. The MAXTs of those tasks must not exceed the allotted times.

Several research projects yielded methodologies and tools for the computation of task execution time bounds [1, 3, 4, 6, 7]. While these approaches are very valuable to compute the execution time of entire, fully implemented tasks, we want to give the programmer more detailed information about the code's timing. Also, we want to let the programmer know about the timing during the whole programming process, not just at the end.
A promising way to achieve the above-mentioned

goal is to provide a programming environment that allows an easy exchange of information about a task's behavior and detailed timing information between the user and the environment. This demand establishes requirements for the task timing analysis tool of the programming environment: This timing analysis tool must be able to a) process programs supplemented with constructs which describe restrictions on the possible execution paths, b) compute bounds for the worst case execution times of programs and program parts that are close to the real execution times, and c) provide information to identify those parts of a program whose improvements are most promising to get along with the given amount of time.

This paper describes a novel task execution time analysis tool, the MAXT analyzer , which fulfills the above-mentioned requirements. It takes into account knowledge about limitations of the control flow through a program, such as loop bounds, break- and return-statements, and additional user-supplied information about impossible paths. From this input it does not only compute tight execution time bounds, but it also shows to which extent every single piece of code contributes to the overall worst case execution time.

The paper is structured as follows: In Section 2 we describe our assumptions about the task model. Section 3 sketches the requirements for the MAXT analyzer. In Section 4 and 5, the main part of this work, we describe the representation of timing data and the MAXT calculation algorithm. The paper is concluded in Section 6.

2 Framework and Assumptions

The described timing analysis tool is part of the MARS programming environment [5] for the MARS system [2]. It makes the following assumptions about tasks: