Germany

We propose a SMT method to derive a real-time guaranteed schedule for the autonomous driving system de- scribed in the industry challenge. All timing constraints proposed as the industry challenge are considered in our SMT model.

IEEE RTSS 2021

Toward Real-Time Guaranteed Scheduling for Autonomous Driving Systems

sponsored talk

 **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. 

Even though earliest-deadline-first (EDF) is optimal in terms of uniprocessor schedulability, it is co-NP-hard to precisely verify uniprocessor schedulability for constraineddeadline task sets. The most efficient way to solve this problem in polynomial time is via a partially linear approximation of the demand bound function. Such approximation leads to a simple uniprocessor schedulability testing with speedup factor ρ. Such a result further leads to Deadline-Monotonic Partitioned-EDF on multi-processors with speedup factor of 1 + ρ − 1/m (where m is the number of processors). The current state of the art results indicate that ρ is within the range [1.5, 14/9]. Especially, it has been a conjecture that ρ = 1.5. This paper improves the range of ρ to (1.5026, 1.5380). The improved lower bound disproves the conjecture of lower bound 1.5. A novel technique is to construct an auxiliary function that is larger than the approximate demand bound function but keeps the supremum ρ unchanged. It solves the dilemma that beating the lower bound 1.5 requires extremely large task sets, while the large size makes it difficult to check the schedulability. This technique not only enables us to disprove 1.5 by a task set of only eight tasks, but also sheds light on future work in transferring/downsizing task sets and deriving utilization bound based tests for various workload abstraction models, such as DAG tasks.

Tighter Bounds of Speedup Factor of Partitioned EDF for Constrained-Deadline Sporadic Tasks

Software transactional memory (STM) is a synchronization paradigm originally proposed for throughput-oriented computing to facilitate producing performant concurrent code that is free of synchronization bugs. With STM, programmers merely annotate code sections requiring synchronization; the underlying STM framework automatically resolves how synchronization is done. Today, the programming issues that motivated STM are becoming a concern in embedded computing, where ever more sophisticated systems are being produced that require highly parallel implementations. In this area, an evolution is underway to produce sophisticated systems such as autonomous vehicles that require highly parallel implementations. These implementations are often produced by engineers and control experts who may not be well versed in concurrency-related issues. In this context, a real-time STM framework would be useful in ensuring that the synchronization aspects of a system pass real-time certification. However, all prior STM approaches fundamentally rely on retries to resolve conflicts, and such retries can yield high worst-case synchronization costs compared to lock-based approaches. Unfortunately, prior work on real-time STM is not helpful in this regard because it has been limited to approaches that retry conflicting transactions; such approaches require retry bounds, which can be large and pessimistic on multiprocessors. This paper presents a new STM class called Retry-Free Real-Time STM (R^2STM), which is designed for worst-case real-time performance. The benefit of a retry-free approach for use in a real-time system is demonstrated by a schedulability study, in which it improved overall schedulability across all considered task systems by an average of 95.3% over a retry-based approach. This paper also presents TORTIS, the first R^2STM implementation for real-time systems.

TORTIS: Retry-Free Software Transactional Memory for Real-Time Systems

In real-time scheduling theory, self-suspension describes the behavior that a job can suspend itself from the ready state and thus be exempted from the scheduling for the suspension duration. This behavior makes it non-trivial to resort to established concepts such as the busy-interval analysis to self-suspending task sets which is required to analyze the worst-case response time of tasks with backlog, e.g., arbitrary-deadline task sets. In this paper, we present a novel suspension-aware busy-interval analysis for dynamic self-suspension tasks where the inter-arrival time of subsequent jobs can be bounded by an arrival curve. Based on the general analysis, we provide worst-case response time analyses and hence sufficient schedulability tests for fixed-priority preemptive uniprocessor scheduling algorithms for arrival-curve constrained and sporadic self-suspension task systems with arbitrary deadlines. Moreover, we provide evaluations based on synthetically generated task sets that show that our method indeed exploits the optimism that is introduced when enlarging the relative deadline of tasks. We demonstrate that our approach improves the state of the art by considering arrival curves that are obtained from tasks with release jitter.

Suspension-Aware Fixed-Priority Schedulability Test with Arbitrary Deadlines And Arrival Curves

We consider the problem of scheduling a set of preemptible independent periodic implicit-deadline hard real- time tasks on heterogeneous processors. We divide this problem into two sub-problems: (a) assigning portions of each proces- sor (offline) to each task without jeopardizing schedulability; and (b) generating a schedule satisfying the assigned portions using an online semi-partitioned scheduler, called Heterogeneous Quasi-Partitioned Scheduling (hQPS). The scheduler handles task servers at run-time for ensuring that the processor shares assigned to tasks are timely available to them. Assessments indicate that the proposed solution (i) has good scalability (up to 64 tasks, 64 processors), (ii) is effective in generating schedules with few preemptions and few migrations, and (iii) is effective in managing resources; for task sets where an extra processor speed is required, our solution needs at most 10% extra compared to an optimal scheduler.

Heterogeneous Quasi-Partitioned Scheduling

In this paper, we propose to use Schedule Abstraction Graphs (SAGs) to determine exact worst-case latency of packets at an egress port of an Ethernet TSN switch with Time-aware Shapers (TASs). We briefly sketch how to apply the existing SAG framework in a TSN context and extend the framework with FIFO-queues and TASs.

Analysis of TSN Time-aware Shapers using Schedule Abstraction Graphs

This work will demonstrate a new flavor of the RA-TDMA set of protocols, namely RA-TDMAs+, which uses IEEE-802.11 (WiFi) COTS hardware in ad-hoc mode to set up a dynamic mesh network of mobile nodes with high-bandwidth. The protocol uses topology tracking to configure the TDMA frame and robust relative synchronization to define the TDMA slots without resorting to a global clock and in the presence of interfering traffic. The demo will set up a small-scale testbed using COTS hardware, thus evidencing the feasibility of the approach, and it will show “live plots” of the temporal (synchronization) and topological views of the network.

Demonstrating RA-TDMAs+ for robust communication in WiFi mesh networks

Industrial Challenge: Opening, Introduction, and Overview of Solutions

In this paper we address the timing verification for processing graphs used to implement autonomous driving systems by the company Perceptin. We demonstrate how to extend our previous results on end-to-end timing analysis in terms of maximum reaction time and maximum data age for cause-effect chains in automotive systems for the posed challenge.

End-To-End Processing Chain Analysis

The 2021 RTSS Industry challenge considers timing constraints in autonomous driving systems. One real-time requirement is that the differences of timestamps among all source data of an output must be upper-bounded by a pre-defined value, to make sure that data from different sources are correctly fused, e.g, object detection by using different sensing data. In this paper, we formally describe the challenge system as well as the requirements. In particular, we present timing analysis to bound the maximum differences of timestamps among all sources for an output. We show that an output may possibly be caused by two different data from the same source, when fork-join structure exists. This result suggests that data fusion after different long pipelined processing procedure must be avoided to meet required timing constraints.

Analysis of Time difference among Sensing Data in Autonomous Driving Systems

Given the problem proposed in RTSS 2021 Industry Challenge, we formally define a system model where dependent tasks are organized in a direct acyclic graph structure and communicate with an unblocking manner. For such a system, we present solutions to estimate three time latencies: maximum reaction time, maximum data age, and maximum difference among the timestamps of ”source” sensor data. One major contribution made in this paper is that the clock shifts among different processing units have been taken into account during the estimations without a mandatory schedule simulation process. By doing this, fairly tight upper bounds can be calculated for all three latencies.

Toward Real-Time Guaranteed Scheduling for Autonomous Driving Systems

Downloads

Next from IEEE RTSS 2021

Tighter Bounds of Speedup Factor of Partitioned EDF for Constrained-Deadline Sporadic Tasks

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES