Category Archives: Real-time Systems

For compilers to be WCET-aware

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.

On the formalization and conceptualization of real-time basic concepts and methods (RMS, EDF) for robots

Nicolas Gobillot, Charles Lesire, David Doose, A Design and Analysis Methodology for Component-Based Real-Time Architectures of Autonomous Systems. Journal of Intelligent & Robotic Systems, October 2019, Volume 96, Issue 1, pp 123–138, DOI: 10.1007/s10846-018-0967-5.

The integration of autonomous robots in real applications is a challenge. It needs that the behaviour of these robots is proved to be safe. In this paper, we focus on the real-time software embedded on the robot, and that supports the execution of safe and autonomous behaviours. We propose a methodology that goes from the design of component-based software architectures using a Domain Specific Language, to the analysis of the real-time constraints that arise when considering the safety of software applications. This methodology is supported by a code generation toolchain that ensures that the code eventually executed on the robot is consistent with the analysis performed. This methodology is applied on a ground robot exploring an area.

Interesting review of time-to-digital converters with the state-of-the-art and applications

S. Tancock, E. Arabul and N. Dahnoun, A Review of New Time-to-Digital Conversion Techniques. IEEE Transactions on Instrumentation and Measurement, vol. 68, no. 10, pp. 3406-3417, DOI: 10.1109/TIM.2019.2936717.

Time-to-digital converters (TDCs) are vital components in time and distance measurement and frequency-locking applications. There are many architectures for implementing TDCs, from simple counter TDCs to hybrid multi-level TDCs, which use many techniques in tandem. This article completes the review literature of TDCs by describing new architectures along with their benefits and tradeoffs, as well as the terminology and performance metrics that must be considered when choosing a TDC. It describes their implementation from the gate level upward and how it is affected by the fabric of the device [field-programmable gate array (FPGA) or application-specific integrated circuit (ASIC)] and suggests suitable use cases for the various techniques. Based on the results achieved in the current literature, we make recommendations on the appropriate architecture for a given task based on the number of channels and precision required, as well as the target fabric.

A microprocessor designed for real-time predictability and short WCETs

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.

A new method for nonlinear optimization aimed to embedded computers, and a nice state of the art of that problem

N. Y. Chiang, R. Huang and V. M. Zavala, An Augmented Lagrangian Filter Method for Real-Time Embedded Optimization, IEEE Transactions on Automatic Control, vol. 62, no. 12, pp. 6110-6121, DOI: 10.1109/TAC.2017.2694806.

We present a filter line-search algorithm for nonconvex continuous optimization that combines an augmented Lagrangian function and a constraint violation metric to accept and reject steps. The approach is motivated by real-time optimization applications that need to be executed on embedded computing platforms with limited memory and processor speeds. The proposed method enables primal-dual regularization of the linear algebra system that in turn permits the use of solution strategies with lower computing overheads. We prove that the proposed algorithm is globally convergent and we demonstrate the developments using a nonconvex real-time optimization application for a building heating, ventilation, and air conditioning system. Our numerical tests are performed on a standard processor and on an embedded platform. We demonstrate that the approach reduces solution times by a factor of over 1000.

A novel method for hard real-time communications using the physical layer of Ethernet and a variation of TDMA

Andrzej Przybył, Hard real-time communication solution for mechatronic systems, Robotics and Computer-Integrated Manufacturing, Volume 49, 2018, Pages 309-316, DOI: 10.1016/j.rcim.2017.08.001.

The paper proposes a method to build a highly efficient real-time communication solution for mechatronic systems. The method is based on the Ethernet physical layer (PHY) and on field programmable gate array (FPGA) technology and offers a better performance when compared to commercially available communication solutions. Although it is not directly compatible with the OSI/ISO model of TCP/IP protocol, vertical integration is done with a gateway. This provides simplicity and safety. Moreover, the use of the FPGA allows for integrating the communication solution with the user algorithm of particular distributed device inside a single chip. Therefore, the proposed solution is efficient and highly integrated.

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

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.

Reducing error in time synchronization for multisensor arrangements in aerial applications, with interesting formulae for the clock drift of IMUs

J. Li, L. Jia and G. Liu, “Multisensor Time Synchronization Error Modeling and Compensation Method for Distributed POS,” in IEEE Transactions on Instrumentation and Measurement, vol. 65, no. 11, pp. 2637-2645, Nov. 2016. DOI: 10.1109/TIM.2016.2598020.

An airborne distributed position and orientation system (POS) is high-precision measurement equipment that can accurately provide multinode time-spatial reference for novel remote sensing system as multitask imaging sensors and array antenna synthetic aperture radar. However, it is difficult for multisensor to precisely acquire information at the same moment and result in data fusion error. Thus, the measurement precision is severely degraded. To solve the problem, a multisensor time synchronization error modeling and compensation method is proposed. Based on the component and operation principles of distributed POS, the time synchronization mechanism is analyzed. Multisensor time synchronization error models that include time delay error, random error, and time-varying error are established. A time synchronization error compensation method of the distributed POS is proposed. The experiment results show that the proposed method can accurately calibrate and compensate for the time synchronization error, and improve the measurement precision of the distributed POS. It verified the validity of the proposed method.

Estimating the execution time of programs before compiling

Peter Altenbernd, Jan Gustafsson, Björn Lisper, Friedhelm Stappert, Early execution time-estimation through automatically generated timing models,, Real-Time Systems, November 2016, Volume 52, Issue 6, pp 731–760, DOI: 10.1007/s11241-016-9250-7.

Traditional timing analysis, such as worst-case execution time analysis, is normally applied only in the late stages of embedded system software development, when the hardware is available and the code is compiled and linked. However, preliminary timing estimates are often needed in early stages of system development as an essential prerequisite for the configuration of the hardware setup and dimensioning of the system. During this phase the hardware is often not available, and the code might not be ready to link. This article describes an approach to predict the execution time of software through an early, source-level timing analysis. A timing model for source code is automatically derived from a given combination of hardware architecture and compiler. The model is identified from measured execution times for a set of synthetic training programs, compiled for the hardware platform in question. It can be used to estimate the execution time for code running on the platform: the estimation is then done directly from the source code, without compiling and running it. Our experiments show that, using this model, we can predict the execution times of the final, compiled code surprisingly well. For instance, we achieve an average deviation of 8 % for a set of benchmark programs for the ARM7 architecture.

Calculating (experimental) probability distributions of the execution of sequential software

Laurent David, Isabelle Puaut, Static Determination of Probabilistic Execution Times, Proceedings of the 12th 16th Euromicro Conference on Real-Time Systems (ECRTS’04). Link.

Most previous research done in probabilistic schedulability analysis assumes a known distribution of execution times for each task of a real-time application. This is however not trivial to determine it with a high level of confidence. Methods based on measurements are often biased since not in general exhaustive on all the possible execution paths, whereas methods based on static analysis are mostly Worst-Case Execution Time – WCET – oriented. Using static analysis, this work proposes a method to obtain probabilistic distributions of execution times. It assumes that the given real time application is divided into multiple tasks, whose source code is known. Ignoring in this paper hardware considerations and based only on the source code of the tasks, the proposed technique allows designers to associate to any execution path an execution time and a probability to go through this path. A source code example is presented to illustrate the method.