Germany

Real-time applications with high computational demand, e.g., autonomous driving, are emerging and their complex nature conforms to a DAG(directed acyclic graph) structure. We propose a conditionally optimal parallelization for real-time DAG tasks for global EDF, ensuring complete execution of all tasks within the deadline. To achieve this, we formalize a monotonic increasing property of both tolerance and interference to the parallelization option. Using such properties, we develop a unidirectional search algorithm that can assign parallelization options in polynomial time, which we formally prove the optimality. We observe significant improvement of schedulability through simulation experiment, and then in the following implementation experiment, we demonstrate that the algorithm is practically applicable for real-world use-cases.

IEEE RTSS 2021

Conditionally Optimal Parallelization of Real-Time DAG Tasks for Global EDF

optimal parallelization

parallelization freedom

task analysis

interference

autonomous vehicles

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

We present MINOTAuR, a timing predictable open source RISC-V core based on the Ariane core. We first modify Ariane in order to make it timing predictable following the approach used to design the SIC processor. We prove that the instruction parallelism in the Ariane core does not prevent from enforcing timing predictability. We further relax restrictions by enabling a limited amount of speculative execution and we are still able to formally prove that the core is timing predictable. Experimental results show that the performance is reduced by only 10% on average compared to the original Ariane core.

Speculative Execution and Timing Predictability in an Open Source RISC-V Core

The partitioned scheduling of periodic and sporadic task systems upon multiprocessor platforms (both identical and heterogeneous) is considered. The computational complexity of a large number of such partitioned schedulability problems is examined. New lower and upper bounds on complexity are presented for several problems. Some problems are pigeonholed into their precise complexity classes in this way. A list of problems for which exact classification remains open is compiled.

Partitioned Scheduling of Recurrent Real-Time Tasks

Though recent work has established the soft real-time (SRT)-optimality of Earliest-Deadline-First (EDF) variants on multiprocessor models with limited heterogeneity (e.g., uniform speeds or affinity masks), such models are insufficient to describe modern multiprocessors, which have grown increasingly heterogeneous. This fact highlights the need to extend theoretical results to more asymmetric models, such as the unrelated multiprocessor model. This paper presents an EDF variant tailored for this model and proves that it is at least nearly SRT-optimal. Simulation results for random task systems are also presented that suggest that the proposed EDF variant may actually be SRT-optimal.

Extending EDF for Soft Real-Time Scheduling on Unrelated Multiprocessors

Shared communication media are widely used in many applications including safety critical applications such as control systems on flights or autonomous vehicles. Noise and transient errors can cause transmission failures. We consider the problem of designing fault tolerant static schedules for transmitting messages in these media. In particular, we assume that the schedule of transmission over all messages must be computed in advance and must guarantee that all messages will be delivered as long as the number of medium errors falls below a provided upper bound, regardless of when the medium errors occur. It is crucial that the messages be delivered in a timely manner, and hence we are interested in minimizing the length of the schedule that achieves the desired level of fault tolerance. In this paper, we provide an efficient algorithm for producing a schedule for $n$ messages with total length $n+O(f^2\log^2n)$ that can tolerate $f$ medium errors. We also prove that fault-tolerant schedules with length $n+O(f\log f\log n)$ exist. Since $n$ steps are required to transmit $n$ messages, the overhead of fault tolerance is characterized by the additive terms of $O(f^2\log^2n)$ and $O(f\log f\log n)$, respectively. Both of these terms are sublinear in $n$ and represent asymptotic improvements to the previously best known schedule, which has overhead $fn/2$.

Sub-Linear Overhead in Static Schedules for Fault-Tolerant Transmission

Global scheduling of real time tasks with precedence constraints has received significant attention recently. Specifically, on multiprocessor systems, the directed acyclic graph (DAG) model well-represents parallelizable workloads with precedence constraints. Hence, many studies have recently been published analyzing DAG structures using decomposition and window-based analysis methods. We identified a set of schedulable DAG taskets that are hard-to-analyze using state-of-the-art window-based schedulability tests. Additionally, we observe that the window-based test solely depends on one structural feature of the DAG taskset, which raises concerns about its pessimism in many settings. In this paper, to address these concerns, for hard real-time sporadic implicit-deadline DAG tasksets, we perform LAG-based schedulability analysis, which offers a more holistic view of the taskset than the window-based analysis. We present a companion utilization-based schedulability test to the state-of-the-art, which considers additional structural features of DAGs. Our results show that by considering such features, our LAG-based test empirically dominates the state-of-the-art test on over 80% of the evaluated DAG tasksets. Moreover, combining our LAG-based test in conjunction with the window-based tests can achieve high schedulability in many cases.

LAG-based Analysis Techniques for Scheduling Multiprocessor Hard Real-Time Sporadic DAGs

Probabilistic timing guarantees enable a tradeoff between system safety and hardware costs in embedded real-time systems. A key metric for assessing whether timing requirements can be satisfied with sufficiently high probability is the worst- case deadline failure probability (WCDFP). This paper studies the WCDFP under earliest-deadline first (EDF) scheduling for tasks with several probabilistic execution modes (e.g., a low-needs “typical” mode and a resource-intensive “exceptional” mode). Under EDF, no known approach can bound the WCDFP for practically sized workloads since the time complexity of prior approaches is exponential in the number of jobs. This paper examines the structure of the EDF WCDFP problem and establishes a safe, efficiently computable over- approximation by restricting the analysis to a set of specific intervals and providing a criterion to stop the derivation early without risking under-approximation. The analysis first assumes independent jobs and is then extended to handle dependencies (i.e., acyclic task chains). An evaluation shows that (i) even if 99.9999% of the jobs must meet their deadlines, a significantly higher utilization is possible than in the deterministic case, (ii) the analysis is scalable to 30 tasks with more than 10 60 jobs in the hyperperiod, and (iii) assuming independence in the presence of dependent tasks can severely under-estimate the WCDFP.

Efficiently Approximating the Worst-Case Deadline Failure Probability under EDF

Embedded systems have become extensive, complex, and automated; thus, increasingly, computing platforms for such systems are being transformed into multi-/many-core platforms. Typically, self-driving systems, involve various applications that run simultaneously, and such systems require low power consumption and large-scale computation. A many-core processor with instructions, multiple data architecture can satisfy these requirements. Shortening the time required to execute all tasks (i.e., makespan) is an important objective in task scheduling for parallel real-time systems, such as self-driving system. Machine learning algorithms have been introduced to solve this kind of problem. This paper proposes a reinforcement learning-based scheduling algorithm for parallel real-time systems represented by a directed acyclic graph (DAG), and Kalray MPPA3-80 is used as a target many-core processor.

Reinforcement Learning-based DAG Scheduling Algorithm in Clustered Many-Core Platform

This paper deals with scheduling anomalies in realtime systems. Scheduling anomalies jeopardize schedulability analysis made prior to execution. In this paper, we propose a model to specify conditions leading to scheduling anomalies. A scheduling anomaly is modeled as a set of constraints on the architecture. We use this model to detect scheduling anomalies by ofﬂine and online analysis. To validate our approach, we implemented the approach as an extension to Cheddar, a schedulability tool. We apply our approach to seven scheduling anomalies and we show that most of these anomalies can be successfully detected.

Models and tools to detect Real-Time Scheduling Anomalies

This is a brief presentation of the paper Bugaev A.S., Tatashev A.G., Yashina M.V., Lavrov O.S., Nosov E.A. Reconstruction of traffic flow dynamics based on deterministic-stochastic model and data obtained from intelligent transport systems. T-Comm, vol. 13, no. 10, pp. 35--44. (in Russian). In this paper, an algorithm has been developed to construct to adjust a mathematical traffic model to traffic modeling. The developed algorithm is used for reconstruction of the flow density and velocity on a segment of Leningradsky prospect in Moscow on the base of the 2011/19 year measurements.

Premium content

Conditionally Optimal Parallelization of Real-Time DAG Tasks for Global EDF

Downloads

Next from IEEE RTSS 2021

Speculative Execution and Timing Predictability in an Open Source RISC-V Core

Similar lecture

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

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES