Germany

Ensuring real-time properties on current heterogeneous multiprocessor systems on a chip is a challenging task. Furthermore, online artificial intelligent applications –which are routinely deployed on such chips– pose increasing pressure on the memory subsystem that becomes a source of unpredictability. Although techniques have been proposed to restore independent access to memory for concurrently executing virtual machines (VM), providing predictable inter-VM communication remains challenging. In this work, we tackle the problem of predictably transferring data between virtual machines and virtualized hardware resources on multiprocessor systems on chips under consideration of memory interference. We design a “broker-based” real-time communication framework for otherwise isolated virtual machines, provide a virtio-based reference implementation on top of the Jailhouse hypervisor, assess its overheads for FreeRTOS virtual machines, and formally analyze its communication flow schedulability under consideration of the implementation overheads. Furthermore, we define a methodology to assess the maximum DRAM memory saturation empirically, evaluate the framework’s performance and compare it with the theoretical schedulability.

IEEE RTSS 2021

A Real-Time virtio-based Framework for Predictable Inter-VM Communication

packet scheduling

virtio

virtual machine

predictable systems

virtual machining

random access memory

virtual machine monitors

task analysis

real time

partitioning

interference

hardware

communication

real-time systems

 **RTSS 2021** has successfully concluded. Hope you have enjoyed it, and look forward to seeing you next year in person.
    Announcement for the Awards:
 * Best Paper Award goes to: Monte Carlo Response-Time Analysis, Sergey Bozhko, Georg von der Brüggen, and Björn Brandenburg
 * Best Student Paper Award goes to: Automatic Energy-Hotspot Detection and Elimination in Real-Time Deeply Embedded Systems, Mohsen Shekarisaz, Lothar Thiele, and Mehdi Kargahi.
 * Best Solution Award for Industry Session goes to: Toward Real-Time Guaranteed Scheduling for Autonomous Driving Systems. Jinghao Sun, Tianyi Wang, Kailu Duan, Bin Lu, Jiankang Ren, Zhishan Guo, and Guozhen Tan.



The IEEE Real-Time Systems Symposium (RTSS) is the premier conference in the field of real-time systems, and is a venue for researchers and practitioners to showcase innovations covering all aspects of real-time systems, including theory, design, analysis, implementation, evaluation, and experience. 

technical paper

Robots are commonly subject to real-time constraints. To ensure that such constraints are met, recent work has analyzed the response times of processing chains under ROS 2, a popular robotics framework. However, prior work supports only scalar worst-case execution time bounds and does not exploit that the ROS 2 scheduling mechanism is starvation-free. This paper proposes a novel response-time analysis for ROS 2 processing chains that accounts for both the high execution-time variance typically encountered in robotics workloads and the starvation freedom of the default ROS 2 callback scheduler. Experimental results from both synthetic callback graphs and a real ROS 2 workload empirically show the proposed analysis to be much more accurate (often by a factor of 2x or more).

A ROS 2 Response-Time Analysis Exploiting Starvation Freedom and Execution-Time Variance

This paper presents a task synchronization mechanism, called co-runner locking, to address the timing interference problem in multi-core real-time systems. It prevents certain subsets of tasks from executing simultaneously on different cores in order to avoid large performance penalties from inter-core interference. We provide the general properties of the co-runner locking mechanism and discuss the runtime control policies that determine the execution order of tasks in a co-runner locking relationship. For schedulability analysis, we derive a response-time test that upper-bounds the delay from co-runner locking and the slowdown imposed by permitted co-runners by combining two new analytic approaches: job-oriented and load-oriented. In evaluation, we demonstrate that the co-runner locking mechanism is an effective alternative to address the “one out-of-m” problem and brings about a significant improvement in real-time taskset schedulability.

Addressing Multi-Core Timing Interference using Co-Runner Locking

Determining a soft or firm real-time task’s probabilistic worst-case response time is a central goal when quantifying and bounding the probability of deadline misses, but current approaches are either (i) fast, but coarse-grained analytical bounds without precision guarantees, (ii) based on convolution and suffer from high space and time complexity, or (iii) combine convolution with resampling techniques that accrue pessimism in an uncontrolled manner. As a new alternative, this paper provides the first probabilistic response-time analysis method based on Monte Carlo simulation, which provides a controlled trade-off between analysis runtime, the desired degree of accuracy, and the permissible probability of a misestimate. An evaluation shows the proposed Monte Carlo analysis to routinely provide more accurate worst-case deadline failure probability (WCDFP) estimates than prior approaches, especially when considering large task sets (where prior methods struggle). In particular, it is shown to scale to workloads with up to 500 tasks while achieving one to three orders of magnitude better precision than analytical or convolution-based approaches (given an equivalent time budget).

Monte Carlo Response-Time Analysis

Time synchronization of devices in Internet-of- Things (IoT) networks is one of the challenging problems and a pre-requisite for the design of low-latency applications. Although many existing solutions have tried to address this problem, almost all solutions assume all the devices (nodes) in the network are faultless. Furthermore, these solutions exchange a large number of messages to achieve synchronization, leading to significant communication and energy overhead. To address these shortcomings, we propose C-sync, a clustering-based decentralized time synchronization protocol that provides resilience against several types of faults with energy-efficient communication. Csync achieves scalability by introducing multiple reference nodes in the network that restrict the maximum number of hops any node can have to its time source. The protocol is designed with a modular structure on the Contiki platform to allow application transitions. We evaluate C-sync on a real testbed that comprises over 40 Tmote Sky hardware nodes distributed across different levels in a building and show through experiments the fault resilience, energy efficiency, and scalability of the protocol. Csync detects and isolates faults to a cluster and recovers quickly. The evaluation makes a qualitative comparison with state-ofthe- art protocols and a quantitative comparison with a class of decentralized protocols (derived from GTSP) that provide synchronization with no/limited fault-tolerance. Results also show a reduction of 56.12% and 75.75% in power consumption in the worst-case and best-case scenarios, respectively, compared to GTSP, while achieving similar accuracy.

Cluster-based Network Time Synchronization for Resilience with Energy Efficiency

We present a middleware-based protocol that reliably synchronizes large samples consisting of multiple frames efficiently and within application level QoS requirements over a lossy wireless channel. The protocol uses a custom retransmission scheme, exploiting the latency requirements on sample level for frame level scheduling. It can be integrated into the popular DDS middleware. We investigate some technical limits of such a protocol and compare it to existing error protocols in the software stack and in the wireless protocol and combinations thereof. The comparison is based on an Omnet++ simulation using an established wireless channel error model. For evaluation, we take a use case from automated valet parking where infrastructure data provided via a wireless link augments in-vehicle sensor data. The use case respects the related safety requirements. Results show that the application awareness of the presented protocol, significantly improves service availability by transmitting data efficiently in time even under higher frame error rates.

A middleware protocol for time-critical wireless communication of large data samples

The Clock Constraint Specification Language (CCSL) has become popular for modeling and analyzing timing behaviors of real-time embedded systems. However, it is dicult for requirement engineers to accurately figure out CCSL specifications from natural language-based requirement descriptions. This is mainly because: i) most requirement engineers lack expertise in formal modeling; and ii) few existing tools can be used to facilitate the generation of CCSL specifications. To address these issues, this paper presents a novel approach that combines the merits of both Reinforcement Learning (RL) and deductive techniques in logical reasoning for ecient co-synthesis of CCSL specifications. Specifically, our method leverages RL to enumerate all the feasible solutions to fill the holes of incomplete specifications and deductive techniques to judge the quality of each trial. Our proposed deductive mechanisms are useful for not only pruning enumeration space, but also guiding the enumeration process to reach an optimal solution quickly. Comprehensive experimental results on both well-known benchmarks and complex industrial examples demonstrate the performance and scalability of our method. Compared with the state-of-theart, our approach can drastically reduce the synthesis time by several orders of magnitude while the accuracy of synthesis can be guaranteed.

Enumeration and Deduction Driven Co-Synthesis of CCSL Specifications Using Reinforcement Learning

In this paper we present a new scheduling model for resilient real-time mixed trust systems. This model extends the previous Real-Time Mixed-Trust Computing framework RT-MTC to support degradation modes. Management of these modes has been identified in industrial documents as a key requirement for deploying trusted autonomous vehicles for safe autonomy. RT-MTC uses verified components (known as enforcers) to guarantee that the output of a system is safe by replacing it with a verified safe one if this output is deemed unsafe or is not produced on time. In this paper we extend RT-MTC and develop a scheduling model that uses the digraph scheduling model as a baseline but extends it in four critical ways: (1) it creates extensions for the mixed-preemptive scheduling required by RT-MTC, (2) it enables priority bands in order to separate trusted and untrusted components, (3) it uses these bands in order to calculate intermediate deadlines used by the RT-MTC framework for the scheduling of the trusted components, and (4) it defines system mode semantics to obtain two desirable properties of the new schedulability analysis: low pessimism and low time-complexity. This paper evaluates the new schedulability algorithm and shows that it is efficient in that it only needs to analyze one transition at a time. The new model supports the construction of a resilient autonomous system with provable guarantees protected by verified enforcers within the RT-MTC framework and, more importantly, preserves these guarantees even across failure-triggered mode changes.

Resilient Mixed-Trust Scheduling

Federated scheduling is a promising approach to schedule parallel real-time tasks, where each task exclusively executes on a set of dedicated processors. However, federated scheduling suffers significant resource wasting since a task typically only uses part of the processing capacity allocated to it, while the unused part cannot be shared with other tasks. To solve this problem, we present a virtually-federated scheduling approach, which both enjoys the good analyzability of federated scheduling and allows tasks to efficiently share processors with others. The main idea is to construct virtual processors on physical processors, and let a task exclusively execute on a set of virtual processors. As a physical processor is shared by virtual processors, tasks effectively share processors with each other. On the other hand, as each task exclusively executes on its own virtual processor set, the good analyzability of federated scheduling can be carried into to our virtually-federated scheduling approach. We conduct comprehensive performance evaluation to compare our proposed approach with existing methods of different types. Experiment results show that our approach consistently outperforms existing methods to a considerable extent under a wide range of parameter settings.

Virtually-Federated Scheduling of Parallel Real-Time Tasks

OpenMP is a promising framework for developing parallel real-time software on multi-cores. Recently, many graphbased task models representing realistic features of OpenMP task systems have been proposed and analyzed. However, all previous studies did not model the loop structures, which is common in OpenMP task systems. In this paper, we formulate the workload of OpenMP task systems with loop structures as the cyclic graph model and study how to compute safe upper bounds for the worstcase response time (WCRT). The loop structures combined with the creation of tasks and conditional branches result in a large state space. Simply unrolling the loop and/or enumerating all the possible execution flows would be computationally intractable. As the major technical contribution, we develop a linear-time dynamic programming algorithm to compute the WCRT bound without unrolling loops or explicitly enumerating the execution flows. Experiments with both synthetic task graphs and realistic OpenMP programs are conducted to evaluate the performance of our method.

Calculating Worst-Case Response Time Bounds for OpenMP Programs with Loop Structures

Real-time deep learning inference serving systems often require prohibitive resources and diverse user requirements. The existing design of inference serving systems mainly focusing on computation resource efficiency, largely ignoring the trade-off between computation and bandwidth resources in need. Sub-optimal resource utilization usually leads to huge serving cost waste. In this paper, we tackle the dual challenge of computation bandwidth trade-off and cost-effectiveness by proposing A2, an efficient joint Adaptive model, and Adaptive data deep learning serving solution across the geo-datacenters. Inspired by the insight that a trade-off between computational cost and bandwidth cost in achieving the same accuracy, we design a real-time inference serving framework, which selectively places different “versions” of the deep learning models at different geolocations, and schedules different data sample versions to be sent to those model versions for inference. The goal is to minimize the total serving cost while meeting latency and accuracy demand for the serving requests. We formulate a joint placement and serving problem and propose an efficient approximation algorithm to solve it with a theoretical performance guarantee. We deploy A2 on Amazon EC2 for experiments, which shows that A2 achieves 30%-50% serving cost reduction under the same required latency and accuracy as compared to baselines.

Premium content

A Real-Time virtio-based Framework for Predictable Inter-VM Communication

Downloads

Next from IEEE RTSS 2021

A ROS 2 Response-Time Analysis Exploiting Starvation Freedom and Execution-Time Variance

Similar lecture

TimeWall: Enabling Time Partitioning for Real-Time Multicore+Accelerator Platforms

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES