Tag Archives: Wcet Analysis

For compilers to be WCET-aware

October 20, 2020 15:47 ,

Heiko Falk, Paul Lokuciejewski, A compiler framework for the reduction of worst-case execution times, Real-Time Systems volume 46, pages251–300(2010), DOI: 10.1007/s11241-019-09337-9.

The current practice to design software for real-time systems is tedious. There is almost no tool support that assists the designer in automatically deriving safe bounds of the worst-case execution time (WCET) of a system during code generation and in systematically optimizing code to reduce WCET. This article presents concepts and infrastructures for WCET-aware code generation and optimization techniques for WCET reduction. All together, they help to obtain code explicitly optimized for its worst-case timing, to automate large parts of the real-time software design flow, and to reduce costs of a real-time system by allowing to use tailored hardware.

Posted in: Computer science, Real-Time Systems , Tagged:

A microprocessor designed for real-time predictability and short WCETs

March 26, 2018 08:58 ,

Schoeberl, M., Puffitsch, W., Hepp, S. et al, Patmos: a time-predictable microprocessor, Real-Time Syst (2018) 54: 389, DOI: 10.1007/s11241-018-9300-4.

Current processors provide high average-case performance, as they are optimized for general purpose computing. However, those optimizations often lead to a high worst-case execution time (WCET). WCET analysis tools model the architectural features that increase average-case performance. To keep analysis complexity manageable, those models need to abstract from implementation details. This abstraction further increases the WCET bound. This paper presents a way out of this dilemma: a processor designed for real-time systems. We design and optimize a processor, called Patmos, for low WCET bounds rather than for high average-case performance. Patmos is a dual-issue, statically scheduled RISC processor. A method cache serves as the cache for the instructions and a split cache organization simplifies the WCET analysis of the data cache. To fill the dual-issue pipeline with enough useful instructions, Patmos relies on a customized compiler. The compiler also plays a central role in optimizing the application for the WCET instead of average-case performance.

Posted in: Electronics, Real-Time Systems , Tagged: , ,

A new method to obtain WCET from binary code and to analyze the execution paths

September 3, 2017 08:25 ,

Thomas Sewell, Felix KamGernot Heiser, High-assurance timing analysis for a high-assurance real-time operating system, Real-Time Systems, Volume 53, Issue 5, pp 812–853, DOI: 10.1007/s1124.

Worst-case execution time (WCET) analysis of real-time code needs to be performed on the executable binary code for soundness. Obtaining tight WCET bounds requires determination of loop bounds and elimination of infeasible paths. The binary code, however, lacks information necessary to determine these bounds. This information is usually provided through manual intervention, or preserved in the binary by a specially modified compiler. We propose an alternative approach, using an existing translation-validation framework, to enable high-assurance, automatic determination of loop bounds and infeasible paths. We show that this approach automatically determines all loop bounds and many (possibly all) infeasible paths in the seL4 microkernel, as well as in standard WCET benchmarks which are in the language subset of our C parser. We also design and validate an improvement to the seL4 implementation, which permits a key part of the kernel’s API to be available to users in a mixed-criticality setting.

Posted in: Real-Time Systems , Tagged: ,

Pdf form of the WCET of code execution

April 29, 2016 10:26 ,

S. Edgar and A. Burns, Statistical analysis of WCET for scheduling, Real-Time Systems Symposium, 2001. (RTSS 2001). Proceedings. 22nd IEEE, 2001, pp. 215-224. DOI: 10.1109/REAL.2001.990614.

To perform a schedulability test, scheduling analysis relies on a known worst-case execution time (WCET). This value may be difficult to compute and may be overly pessimistic. This paper offers an alternative analysis based on estimating a WCET from test data to within a specific level of probabilistic confidence. A method is presented for calculating an estimate given statistical assumptions. The implications of the level of confidence on the likelihood of schedulability are also presented.

Posted in: Real-Time Systems , Tagged: ,

Interesting and gentle introduction to WCET analysis and synchronous design for hard real-time systems

March 11, 2015 11:32 ,

Pascal Raymond, Claire Maiza, Catherine Parent-Vigouroux, Fabienne Carrier, Mihail Asavoae, 2015, Timing analysis enhancement for synchronous program, Real-Time Systems, Volume 51, Issue 2, pp 192-220, DOI: 10.1007/s11241-015-9219-y.

Real-time critical systems can be considered as correct if they compute both right and fast enough. Functionality aspects (computing right) can be addressed using high level design methods, such as the synchronous approach that provides languages, compilers and verification tools. Real-time aspects (computing fast enough) can be addressed with static timing analysis, that aims at discovering safe bounds on the worst-case execution time (WCET) of the binary code. In this paper, we aim at improving the estimated WCET in the case where the binary code comes from a high-level synchronous design. The key idea is that some high-level functional properties may imply that some execution paths of the binary code are actually infeasible, and thus, can be removed from the worst-case candidates. In order to automatize the method, we show (1) how to trace semantic information between the high-level design and the executable code, (2) how to use a model-checker to prove infeasibility of some execution paths, and (3) how to integrate such infeasibility information into an existing timing analysis framework. Based on a realistic example, we show that there is a large possible improvement for a reasonable computation time overhead.

Posted in: Real-Time Systems , Tagged: , ,