Category Archives: Real-time Systems

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.

Pdf form of the WCET of code execution

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.

Improvement on the classical regression-based estimation algorithm of the relative clock frequency of two remotely connected clocks for better behaviour under outliers, and a good related works section on the estimation of clock relative frequency

Oka Saputra, K.; Wei-Chung Teng; Tsung-Han Chen, Hough Transform-Based Clock Skew Measurement Over Network, in Instrumentation and Measurement, IEEE Transactions on , vol.64, no.12, pp.3209-3216, Dec. 2015, DOI: 10.1109/TIM.2015.2450293.

The accurate clock skew measurement of remote devices over network connections is crucial to device fingerprinting and other related applications. Current approaches use the lower bound of offsets between the target device and the measurer to estimate clock skew; however, the accuracy of estimation is severely affected when even a few offsets appear below the crowd of offsets. This paper adopted the Hough transform to develop a new method, which searches for the densest part of the whole distribution. This method is effective in filtering out the upper and lower outliers such that the skew values derived from the remaining offsets are stable, even when lower outliers occur, or when the measuring time is not long enough for current approaches to achieve stable results. The experimental evaluation of the proposed method has been conducted in order to compare its performance with that of linear programming algorithm (LPA) and two other approaches. During the five consecutive measurements of 1000 offsets each, skews of the proposed method varied within the range of 0.59 ppm, whereas LPA resulted in the range of 0.89 ppm. Both ranges increased to 1.34 and 63.93 ppm, respectively, when the lower bounds encountered interference from lower outliers.

Notes:

  • They assume there is no NTP running in the background; however, their results seem to come from a conventional TCP/IP network, where it is difficult not to find NTP enabled.

Scheduling of communications between several nodes for better achieving real-time constraints in a distributed control system, and also a very detailed dynamical model of a wheeled vehicle

Naim Bajcinca, Wireless cars: A cyber-physical approach to vehicle dynamics control, Mechatronics, Volume 30, September 2015, Pages 261-274, ISSN 0957-4158, DOI: 10.1016/j.mechatronics.2015.04.016.

A non-conventional drive-by-wireless technology for guidance and control of a redundantly actuated electric car supported by an on-board wireless network of sensors, actuators and control units is proposed in this article. Several optimization-based distributed feedforward control schemes are developed for such powertrain infrastructures. In view of the limitations of the commercial off-the-shelf wireless communication technologies and the harshness of the in-vehicle environments, a pressing design and implementation aspect, in addition to the robustness against information loss, refers to fulfilling the hard real-time computational requirements. In this work, we address such problems by introducing several distributed event-based control schemes in conjunction with adaptive scheduling at the protocol level. Hereby we obtain a simple tuning mechanism to compromise between the outcome accuracy and computation efficiency (i.e., communication traffic intensity). Using simulative evaluations, we demonstrate the viability of the proposed algorithms and illustrate the impact of external interferences in an IEEE 802.15.4 based wireless communication solution.