Germany

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.

IEEE RTSS 2021

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

multicore processing

scheduling algorithms

program processors

probabilistic logic

computational modeling

parallel processing

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

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.

Toward Real-Time Guaranteed Scheduling for Autonomous Driving Systems

Considering the instance of autonomous driving system mentioned in RTSS 2021 Industry Challenge, a mixed integer linear programming (MILP) model is built to formulate this specific instance. Based on the specific instance, system and scheduling models are proposed correspondingly.

A Linear Programming Solution to Real-time Scheduling in Autonomous Driving System

In this paper, we propose a general solution to the problem of scheduling real-time applications on heterogeneous hardware platforms. To fully utilize the computing capacity of heterogeneous processing units, we model the real-time applica- tion as a heterogeneous Directed Acyclic Graph (DAG) which specifies the types of processors (CPU, GPU, etc.) where each task should run. In this well-known DAG context, we propose a novel extension aimed at safety-critical systems that operate in unpredictable environments: the coupling of conditional DAG nodes with stochasticity. Specifically, conditional DAG nodes en- able the modeling of systems that execute computational pipelines based on environmental context, while stochasticity of DAG edges captures the uncertain nature of a system’s environment or the reliability of its hardware. Furthermore, considering the pessimism of deterministic worst-case execution time (WCET) in scheduling processes, we model execution times of tasks (DAG nodes) as probability distributions which yields a novel stochastic conditional DAG model. Coupled with a novel S-bottleneck heuris- tic and safety-performance (SP) metric, our proposed framework allows for efficient online scheduling in complex computational pipelines, with more flexible representation of timing constraints, and ultimately, safety-performance trade offs.

S-Bottleneck Scheduling with Safety-Performance Trade-offs in Stochastic Conditional DAG Models

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

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

Downloads

Next from IEEE RTSS 2021

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

Similar lecture

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

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES