Worst-case execution time

Worst-case execution time

The worst-case execution time (WCET) of a computational task is the maximum length of time the task could take to execute on a specific hardware platform. Knowing worst-case execution times is of prime importance for the schedulability analysis of hard real-time systems.

Analysis structure

Timing analysis is in general performed on two levels:
* WCET analysis
* Higher-level/system-level analysis

WCET analysis considers the execution time of an isolated task. At this level, activities other than ones related to the considered task are ignored. Tasks are assumed never to block or to be interrupted (blocking is dealt with by the schedulability analysis).

At the higher level, the overall system performance is analyzed, given the results of the WCET analysis for each task or program in the system. Multiple tasks are usually assumed to execute on a single processor and compete for resources, and thus possibly block while attempting to access the resources. The most common type of analysis here is schedulability analysis: for example, fixed-priority analysis or rate-monotonic scheduling analysis. The tightness, or precision of schedulability analysis relies on the accuracy of the WCET analysis. If the WCET values are pessimistic (greater than any execution time that can occur in a running system) then the scheduler will be forced to allocate more time to those tasks than actually required.

A static WCET analysis tool should be able to work at a high-level to determine the structure of a program's task, working either on a piece of source code or disassembled binary executable. But it should also work at a low-level, using timing information about the real hardware that the task will execute on, with all its specific features. By combining those two kinds of analysis, the tool should give an upper bound on the time required to execute a given task on a given hardware platform.

At the low-level, static WCET analysis is complicated by the presence of architectural features that improve the performance of the processor: instruction/data caches, branch prediction and instruction pipelines for example. It is possible to determine tight WCET bounds if these modern architectural features are taken into account in the timing model used by the analysis.

Besides static analysis approaches, which have dominated research in the area since the late 1980s, dynamic or measurement-based approaches have recently entered the research arena. The motivation cited by researchers in this branch is that computing hardware (the CPU in particular) has reached a complexity which is extremely hard to model, in particular because the modelling process can introduce errors from several sources: errors in chip design, lack of documentation, errors in documentation, errors in model creation; all leading to cases where the model predicts a different behavior to that observed on real hardware. On the other hand, measurement based approaches are also considered to be potentially inaccurate, because they rely on observing the worst-case effects during testing. Measurement-based approaches usually try to measure the execution times of short code segments (basic blocks) and then use static analysis methods to compute the worst case behavior of the code as a whole. This is driven by the philosophy that the WCET of a basic block is easily measured, but creating a test case in which each block on the worst case path is exercised is extremely difficult.

Historically industry has either used end-to-end measurements with an added safety margin for soft-real-time systems, or manual static analysis on simple hardware for safety critical systems. Recently industry has shown more interest in research into automated methods of calculating WCET. Complexity is increasingly becoming an issue in manual analysis and safety margins have become a liability in soft-real-time systems: they are either too generous, increasing the cost of the device, or too tight, causing device failure. In the future, it is likely that a requirement for safety critical systems is that they are analyzed using both static and measurement-based approaches.

Research groups

The most active research groups are in Sweden (Mälardalen, Linköping), Germany (Saarbrücken, Dortmund, Braunschweig), France (Toulouse, Rennes), Austria (Vienna), UK (York), Italy (Bologna), Spain (Cantabria, Valencia), and Switzerland (Zurich). Recently, the topic of code-level timing analysis has found more attention outside of Europe by research groups in the US (North Carolina, Florida), Australia, and Singapore.

WCET Tool Challenge

The first international WCET Tool Challenge took place during the autumn of 2006. It was organized by the University of Mälardalen and sponsored by the ARTIST2 Network of Excellence on Embedded Systems Design. The aim of the Challenge was to inspect and to compare different approaches in analyzing the worst-case execution time. All available tools and prototypes able to determine safe upper bounds for the WCET of tasks have participated. The [http://home.versanet.de/~lt-422029/WCETToolChallengep_Extl.pdf final results] were presented in November 2006 at the ISoLA 2006 International Symposium in Paphos, Cyprus.

A second Challenge took place in 2008 [http://www.mrtc.mdh.se/projects/WCC08/] .

ee also

*Big O notation
*Optimization (computer science)
*Best and worst cases

Articles and white papers

* [http://moss.csc.ncsu.edu/~mueller/ftp/pub/mueller/papers/1257.pdf The Worst-Case Execution Time Problem - Overview of Methods and Survey of Tools]
* [http://ls12-www.cs.uni-dortmund.de/publications/papers/2007-codes+isss_1.pdf Compile-Time Decided Instruction Cache Locking Using Worst-Case Execution Paths (PDF)]
* [http://ls12-www.cs.uni-dortmund.de/publications/papers/2007-codes+isss_2.pdf Influence of Procedure Cloning on WCET Prediction (PDF)]
* [http://www.absint.com/aiT_WCET.pdf Worst-Case Execution Time Prediction by Static Program Analysis (PDF)]
* [http://artist.cs.uni-sb.de/WCET05/Papers/WCET2005Proceedings.pdf Proceedings of WCET 2005, the 5th International Workshop on Worst-Case Execution Time Analysis, Satellite Event to ECRTS'05 (PDF)]
* [http://home.versanet.de/~lt-422029/WCETToolChallengep_Extl.pdf WCET Tool Challenge 2006 final report (PDF)]
* [http://www.mrtc.mdh.se/publications/1037.pdf Static WCET Analysis of Task-Oriented Code for Construction Vehicles (PDF)]
* [http://www.mrtc.mdh.se/publications/0974.pdf Applying Static WCET Analysis to Automotive Communication Software (PDF)]
* [http://www.mrtc.mdh.se/publications/0978.pdf Evaluation of Static Time Analysis for CC Systems (PDF)]
* [http://www.mrtc.mdh.se/publications/0796.pdf Static Timing Analysis of Real-Time Operating System Code (PDF)]
* [http://www.mrtc.mdh.se/publications/0738.pdf Evaluating Static WCET Analysis for a Commercial RTOS (PDF)]
* [http://drops.dagstuhl.de/opus/volltexte/2006/673/pdf/WCET_Falk.673.pdf Design of a WCET-Aware C Compiler (PDF)]
* [http://www.absint.com/aiT_airbus.pdf Airbus France: Computing the WCET of an Avionics Program by Abstract Interpretation (PDF)]
* [ftp://ftp.irit.fr/IRIT/TRACES/6278_ERTS06.pdf OTAWA, a Framework for Experimenting WCET Computations (PDF)]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Worst Case Execution Time — Die maximale Ausführungszeit (englisch Worst Case Execution Time, WCET) gibt die längste Zeit an, die ein Computerprogramm oder Programmteil auf einer bestimmten Plattform zur Ausführung benötigen kann. Sie wird bestimmt durch: die Programmlogik… …   Deutsch Wikipedia

  • EXECUTION — (Civil), laws concerning methods of recovering a debt. Definition and Substance of the Concept In Jewish law, a debt or obligation (ḥiyyuv) creates in favor of the creditor not only a personal right of action against the debtor, but also a right… …   Encyclopedia of Judaism

  • Best, worst and average case — In computer science, best, worst and average cases of a given algorithm express what the resource usage is at least , at most and on average , respectively. Usually the resource being considered is running time, but it could also be memory or… …   Wikipedia

  • Real-time computing — In computer science, real time computing (RTC) is the study of hardware and software systems that are subject to a real time constraint i.e., operational deadlines from event to system response. By contrast, a non real time system is one for… …   Wikipedia

  • Temps d'exécution pire-cas — Le temps d exécution pire cas (en anglais : Worst case execution time, WCET) est le temps maximum que prendra un programme pour s exécuter sur un matériel donné. Connaître ce temps est primordial pour les systèmes temps réel. Portail de… …   Wikipédia en Français

  • Real time database — A real time database is a processing system designed to handle workloads whose state is constantly changing (Buchmann). This differs from traditional databases containing persistent data, mostly unaffected by time. For example, a stock market… …   Wikipedia

  • Corby toxic waste case — The Corby toxic waste contamination ruling was an official proclamation delivered by The Hon. Mr. Justice Akenhead at the High Court of Justice, London, on 29 July 2009 in the case of Corby Group Litigation v. Corby Borough Council [2009] EWHC… …   Wikipedia

  • End time — End time, End times, or End of days are the eschatological writings in the three Abrahamic religions and in doomsday scenarios in various other non Abrahamic religions. In Abrahamic religions, End times are often depicted as a time of tribulation …   Wikipedia

  • WCET — Worst Case Execution Time (Computing » Hardware) ** Western Cooperative for Educational Telecommunications (Academic & Science » Universities) * TV 48, PBS, Cincinnati, Ohio (Community » TV Stations) …   Abbreviations dictionary

  • WCET — Die maximale Ausführungszeit (englisch Worst Case Execution Time, WCET) gibt die längste Zeit an, die ein Computerprogramm oder Programmteil auf einer bestimmten Plattform zur Ausführung benötigen kann. Sie wird bestimmt durch: die Programmlogik… …   Deutsch Wikipedia