Germany

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

IEEE RTSS 2021

Monte Carlo Response-Time Analysis

aerospace electronics

time factors

probabilistic scheduling

probabilistic logic

runtime

monte carlo simulation

convolution

monte carlo methods

real time systems

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

This work focuses on the time-predictable execution of Deep Neural Networks (DNNs) accelerated on FPGA System-on-Chips (SoCs). The modern DPU accelerator by Xilinx is considered. An extensive profiling campaign targeting the Zynq Ultrascale+ platform has been performed to study the execution behavior of the DPU when accelerating a set of state-of-the-art DNNs for Advanced Driver Assistance Systems (ADAS). Based on the profiling, an execution model is proposed and then used to derive a response-time analysis. A custom FPGA module named DICTAT is also proposed to improve the predictability of the acceleration of DNNs and tighten the analytical bounds. A rich set of experimental results based on both analytical bounds and measurements from the target platform is finally presented to assess the effectiveness and the performance of the proposed approach on ADAS applications.

Time-Predictable Acceleration of Deep Neural Networks on FPGA-based SoC

Deep neural networks (DNNs) have shown remark- able success in various machine-learning (ML) tasks useful for many safety-critical, real-time embedded systems. The foremost design goal for enabling DNN execution on real-time embedded systems is to provide worst-case timing guarantees with limited computing resources. Yet, the state-of-the-art ML frameworks hardly leverage heterogeneous computing resources (i.e., CPU, GPU) to improve the schedulability of real-time DNN tasks due to several factors, which include a coarse-grained resource allocation model (one-resource-per-task), the asymmetric nature of DNN execution on CPU and GPU, and lack of schedulability- aware CPU/GPU allocation scheme. This paper presents, to the best of our knowledge, the first study of addressing the above three major barriers and examining their cooperative effect on schedulability improvement. In this paper, we propose LaLaRAND, a real-time layer-level DNN scheduling framework, that enables flexible CPU/GPU scheduling of individual DNN layers by tightly coupling CPU-friendly quantization with fine-grained CPU/GPU allocation schemes (one-resource-per-layer) while mitigating ac- curacy loss without compromising timing guarantees. We have implemented and evaluated LaLaRAND on top of the state-of-the- art ML framework to demonstrate its effectiveness in making more DNN task sets schedulable by 56% and 80% over an existing approach and a baseline (vanilla PyTorch), respectively, with only up to -0.4% of performance (inference accuracy) difference.

LaLaRAND: Flexible Layer-by-Layer CPU/GPU Scheduling for Real-Time DNN Task

Thermal awareness is increasingly important for real-time systems deployed in harsh environments. As high chip temperature can cause frequency throttling or shutdown of processor cores at unexpected times, many real-time scheduling techniques have been developed to ensure continuous, fail-safe operation of safety-critical tasks with stringent timing constraints. However, their practical use remains largely limited due to the fact that it is extremely difficult to obtain a precise thermal model of commercial processors without using special measurement instruments or access to proprietary information, such as the power traces of micro-architectural units and detailed floorplans. In this paper, we propose a data-driven structured thermal modeling scheme that is directly applicable to commercial off-theshelf multi-core processors used in real-time embedded systems. By using a small number of thermal profiles obtained from onchip temperature sensors, our scheme can accurately predict the processor operating temperature under dynamic real-time workloads at various CPU frequencies and ambient conditions. The thermal model derived from our scheme is fast to converge and robust against different sources of errors. Our scheme is non-intrusive, meaning that it does not require changes to the software code or the hardware packaging of the target system. Furthermore, our scheme can estimate the relative power consumption of the processor for a given workload and clock frequency level. Experimental results from a multi-core ARM platform indicate that our scheme estimates the operating temperature with a maximum error of 2.5% while the latest prior work results in 23% error. This highly accurate modeling enables us to obtain the maximum achievable processor utilization that does not cause a thermal safety violation.

Data-Driven Structured Thermal Modeling for COTS Multi-Core Processors

The modeling and analysis of real-time applications focus on the worst-case scenario because of their strict timing requirements. However, many real-time embedded systems in- clude critical applications requiring not only timing constraints but also other system limitations, such as energy consumption. In this paper, we study the energy-aware real-time scheduling of Directed Acyclic Graph (DAG) tasks. We integrate the Dynamic Power Management (DPM) policy to reduce the Worst-Case Energy Consumption (WCEC), which is an essential requirement for energy-constrained systems. Besides, we extend our analysis with tasks’ probabilistic information to improve the Average- Case Energy Consumption (ACEC), which is, instead, a common non-functional requirement of embedded systems. To verify the benefits of our approach in terms of reduced energy consumption, we finally conduct an extensive simulation, followed by an experimental study on an Odroid-H2 board. Compared to the state-of-the-art solution, our approach is able to reduce the power consumption up to 32.1%.

A Multi-Level DPM Approach for Real-Time DAG Tasks in Heterogeneous Processors

Real-time systems increasingly use multicore processors in order to satisfy thermal, power, and computational requirements. To exploit the architectural parallelism offered by the multicore processors, parallel task models, scheduling algorithms and response-time analyses with respect to real-time constraints have to be provided. In this paper, we propose a reservation-based scheduling algorithm for sporadic constrained-deadline parallel conditional DAG tasks with probabilistic execution behaviour for applications that can tolerate bounded number of deadline misses and bounded tardiness. We devise design rules and analyses to guarantee bounded tardiness for a specified bounded probability for k-consecutive deadline misses without enforcing late jobs to be immediately aborted.

Response-Time Analysis and Optimization for Probabilistic Conditional Parallel DAG Tasks

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

We regard the industry challenge as a multi- objective real-time scheduling problem. Different from tradi- tional methods, we model it as a nonlinear program (NLP) and use gradient-based methods for efficient solutions. Different requirements can be freely added as constraints, which gives the proposed method effective for a large range of problems. Furthermore, the proposed NLP scheduling method can utilize available scheduling algorithm as initialization method, and improve their performance even further. Preliminary evaluation shows advantages against simple heuristic methods in compli- cated problems.

A General Scheduling Framework for Multi-objective Real-time Systems

As a feasible solution for the RTSS 2021 industry challenge, we propose System-Level Logical Execution Time (SL- LET) in combination with a modified middleware layer.

Premium content

Monte Carlo Response-Time Analysis

Downloads

Next from IEEE RTSS 2021

Time-Predictable Acceleration of Deep Neural Networks on FPGA-based SoC

Similar lecture

Efficiently Approximating the Worst-Case Deadline Failure Probability under EDF

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES