Maximum runtime

from Wikipedia, the free encyclopedia

The maximum duration or maximum execution time ( English Worst Case Execution Time, WCET ) indicates the longest time that a computer program or program part can take on a specific platform for execution. It is determined by:

Knowledge of the WCET or at least a safe upper limit is a necessary criterion for implementing a hard real-time system . With real-time systems, it is very important to get the logically correct result at exact times. Short delays could be disastrous. The most important areas of application for real-time systems are e.g. B. Car airbag controls, aircraft controls, controls in power plants. In the case of car controls, the delayed ejection of the airbag can have fatal consequences for the occupants of the motor vehicle. It is therefore important that real-time systems provide the correct result in a specific time.

The execution time

A basic distinction is made between BCET (best case execution time) and WCET (worst case execution time). The BCET is the fastest execution time in which the program delivers a result, i.e. H. under no circumstances can the program run faster. The WCET is the longest possible execution time in which the program code provides a result.

Fundamental problems of determining the running time

Theoretical limits

In the general case it is impossible to determine the maximum execution time for any program.

In order to determine the maximum execution time, one would have to solve the following problem: A program P is given. We are looking for a further program WCET that calculates the maximum execution time of P, i.e. WCET (P). Since all those programs that run in an infinite loop have a maximum execution time, you could use the WCET program to decide whether the underlying program terminates at all and thus solve the halt problem. However, the stopping problem is demonstrably undecidable, so the WCET program cannot exist.

An upper limit of the WCET can, however, be determined for a relevant subset of all possible programs.

Practical problems

The scheduling strategies of modern operating systems prevent a reliable prediction of when a task will be due. Real-time operating systems or direct implementations without an operating system layer provide a remedy here .

On modern processor architectures, the execution time of a task depends heavily on the state of the processor cache. Even when using a real-time operating system, two tasks can be influenced by the cache.

Methods of determination

There are different methods of calculating the WCET, which only differ in terms of accuracy and applicability. It is important to know how accurately the WCET can be estimated. The methods try to get as close as possible to the real execution time, but the result must never be less than the actual execution time.

Measurement methods are one way of estimating the WCET. With these methods, various test runs on the target hardware measure the time that the code needs to deliver a result. This method is very time-consuming as it is never possible to test all states ( combinatorial explosion ).

With the WCET analysis, however, the longest execution path is determined and the execution time for a specific target hardware is calculated in this way.

Measurement-based approaches

Instead of analyzing the code, the measurement-based approaches simply execute the program on the target hardware and measure the execution time. Measurement-based approaches, however, generally lead to an underestimation of the WCET, since the execution time of programs generally depends on the input data. By analyzing the source code, however, input data records can be generated which cover all paths of the program to be tested. Although this method simplifies the porting of software, it also suffers from complex processor architectures.

WCET analysis

WCET analysis calculates the worst case scenario in the execution time of specific code in an application, but it does not guarantee the accuracy of the code's results. The WCET is also dependent on the program code and the underlying hardware, i.e. H. different program codes have different worst case execution times on different computer architectures. The analysis should therefore always be carried out with the hardware components that the target system also has. With this method, the program code is examined and the actually longest execution path is determined. Then you add the required processor cycles of all machine code commands in the path and you get the WCET.

Problems with the WCET analysis

There are three problem domains in WCET analysis. On the one hand, finding out the path to be executed, translating the source code into the machine code and performing the machine code analysis.

Determining the path to be executed (program flow ): One problem with the WCET analysis is to find out the longest path with regard to the runtime of the source code. A good example of this are loops that require a different execution time depending on the input. Each input case must be played through. However, this is impossible with more complex systems because there are too many different input options.

Translation from source code into machine code: If the path is known, the source code can be translated into machine code . The problem in this case is that the program flow in the machine code also changes with new translators. It then follows that the program flow found must also be compiled so that it corresponds to the machine code.

Machine code analysis : The duration of the execution also depends on the hardware used. The cache and the instruction pipelines determine the state of the hardware. The cache depends on the entire program that has been executed up to that point. It can therefore not be assumed that no cache exists. Furthermore, static values ​​cannot be used, as otherwise the WCET would become too imprecise.

Approaches to solving the problems

There are approaches to solving each of the three problems encountered in WCET analysis.

Program flow analysis : There are several approaches to a program flow analysis. One of them would be to use programming languages ​​that do not allow unmanageable code, such as B. recursions or indefinitely running loops. Another approach would be to give the programmer a possibility in the source code to note information about the source code. However, a special compiler would have to be developed and used for this proposal. If you don't want to use a special compiler for this, the programmer can also enter his information outside of the source code in a description language. The execution time can only be determined at the machine code level. Thus, a WCET analysis tool must map source code annotations to machine code, which is only possible with precise knowledge of the compiler behavior. This requires close cooperation with the analysis tool and compiler manufacturer.

Translation from source code into machine code: the biggest problem, however, lies in converting the program flow of the source code into the program flow of the machine code. One solution in this case would be to determine the program flow in the machine code. This eliminates the translation. However, this variant is difficult to solve because the machine code is difficult to read. The quality of the WCET estimate also suffers as a result, since precise information on the execution time can only be noted in the source code.

Machine code analysis : One of the safest approaches to determine the WCET is to always assume a cache miss until the variable is in the data cache. The machine code analysis determines the time of individual commands and the influence on other commands. Most of the time, it is known how long it takes a processor to process certain commands.

Calculation methods

The WCET is calculated from the information from the machine code analysis and program flow analysis. There are several ways to calculate the WCET. With the path-based method, all possible paths in the program are determined and their execution time is calculated. Then the maximum execution time is determined. Another method for calculating the WCET is the tree-based method. The entire program is replaced by a parse tree. An execution time is then determined for each group of commands. This method is difficult to incorporate program flow information. The last method uses an integer-linear program solver. With this method, an integer variable is specified in every possible program branch. This variable records the number of times that particular piece of code was executed. The time for a particular path in the program was determined by the machine code analysis. This method also determines the longest path.

List of maximum runtime analysis tools

  • RapiTime
  • Bound-T
  • aiT
  • OTAWA

See also

literature

  • Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, and Per Stenström: The Determination of Worst-Case Execution Times-Overview of the Methods and Survey of Tools. ACM Transactions on Embedded Computing Systems (TECS), 7 (3), 2008.

Web links