Germany

This paper discusses evaluation criteria and scheduling strategies for the analysis of overloaded real-time systems. This work builds upon techniques from queueing theory and proposes a new approach for real-time systems.

IEEE RTSS 2021

Evaluating Task Dropping Strategies for Overloaded Real-Time Systems

queueing analysis

task analysis

task dropping

overloaded system

real-time system

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

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.

Joint Model and Data Adaptation for Cloud Inference Serving

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.

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

Instant delivery has developed rapidly in recent years and significantly changed the lifestyle of people due to its timeliness and convenience. In instant delivery, the order dispatch process is concurrent. Couriers take new orders continuously and deliver multiple orders in a delivery trip (i.e., a batch). The delivery time of orders in a batch is often overlapped and interlinked with each other. The pickup and delivery sequence of the existing orders in a batch changes dynamically due to time constraints and real-time overdue possibility (i.e., the rate of deliveries that are not finished in promised time). Most of existing order dispatch mechanisms are designed for independent order dispatch or concurrent delivery without strict time constraints, hence are incapable of handling real-time concurrent dispatch with strict time constraints in on-demand instant delivery. To address the challenge, we propose a Time-Constrained Actor- Critic Reinforcement learning based concurrent dispatch system called TCAC-Dispatch to enhance the long-term overall revenue and reduce the overdue rate. Specifically, we design a deep matching network (DMN) with a variable action space, which integrates the state embedding (including route behaviors encod- ing) and actions embedding features into a long-term matching value. Then the Actor-Critic model tackles the concurrent order dispatch problem considering strict time constraints and stochas- tic demand-supply in instant delivery. An estimated time-based action pruning module is designed to ensure time constraints guarantee and accelerate the training as well as dispatching processes. We evaluate the TCAC-Dispatch with one-month data involved with 36.48 million orders and 42,000 couriers collected from one of the largest instant delivery companies in China, i.e., Eleme. Empirical experiments are conducted on a data-driven emulator deployed on the development environment of Eleme and results show that our method achieves 22% of the increase in total revenue and reduces the overdue rate by 21.6%.

Concurrent Order Dispatch for Instant Delivery with Time-Constrained Actor-Critic Reinforcement Learning

Mobile devices have been increasingly deployed in large-scale cyber-physical systems (CPS) to traverse the field and retrieve data measurements from designated physical entities with stringent performance requirements. This work studies the availability-constrained real-time data retrieval problem in CPS with a speed adjustable mobile device (AFDR-SA). The goal is to maintain the temporal validity of the real-time data to be retrieved in the system while meeting the data availability constraints imposed by the communication range between the mobile device and the physical entities. A dynamic programming (DP)-based optimal algorithm is proposed for a special but commonly presented scenario where the retrieval times of individual data items are of the same length. Based on this optimal algorithm, an effective heuristic method is further developed for the general case where data items can have arbitrary retrieval times. The effectiveness of the proposed methods are validated through extensive experiments. Our results demonstrate the optimality of the DP-based algorithm, and show that the heuristic method outperforms the state-of-the-art schemes and performs close to the optimal solution obtained by the exhaustive search with much less computational overhead.

Keep Fresh: Real-time Data Retrieval with Speed Adaptation in Mobile Cyber-Physical Systems

Increased dependence on networked, software-based control has escalated the vulnerabilities of Cyber-Physical Systems (CPSs). Detection and monitoring components developed leveraging dynamical systems theory are often employed as lightweight security measures for protecting such safety-critical CPSs against false data injection attacks. However, existing approaches do not correlate attack scenarios with parameters of detection systems. In this work, we propose real-time attack detection and mitigation strategies for safety-critical CPSs. A Reinforcement Learning (RL) based framework is presented which adaptively sets the parameters of such detectors based on experience learned from attack scenarios. The detection system is provided with a suitable training environment to learn how to maximize the detection rate while minimizing false alarms. Along with the objective of attack detection, our framework also attempts to preserve system performance by judiciously choosing control actions based on the operating region. Our proposed method i) mathematically establishes a detection strategy for fast and accurate FDI attack detection, ii) correlates the key parameters of the detection system by learning from attack scenarios, and iii) incorporates a real-time attack mitigation strategy that uses formally synthesized fast controllers, thus creating an end-to-end defense against FDI attacks for safety-critical CPSs. We evaluate our proposed method using well-known safety-critical CPS examples.

Catch Me If You Learn: Real-Time Attack Detection and Mitigation in Learning Enabled CPS

Real-time end-to-end task scheduling in networked control systems (NCSs) requires the joint consideration of both network and computing resources to guarantee the desired quality of service (QoS). This paper introduces a new model for composite resource scheduling (CRS) in real-time networked control systems, which considers a strict execution order of sensing, computing, and actuating segments based on the control loop of the target NCS. We prove that the general CRS problem is NP-hard and study two special cases of the CRS problem. The first case restricts the computing and actuating segments to have unit-size execution time while the second case assumes that both sensing and actuating segments have unit-size execution time. We propose an optimal algorithm to solve the first case by checking the intervals with 100% network resource utilization and modify the deadlines of the tasks within those intervals to prune the search. For the second case, we propose another optimal algorithm based on a novel backtracking strategy to check the time intervals with the network resource utilization larger than 100% and modify the timing parameters of tasks based on these intervals. For the general case, we design a greedy strategy to modify the timing parameters of both network segments and computing segments within the time intervals that have network and computing resource utilization larger than 100%, respectively. The correctness and effectiveness of the proposed algorithms are verified through extensive experiments.

Composite Resource Scheduling for Networked Control Systems

Artificial-intelligence algorithms are enabling ever more sophisticated autonomous features in safety-critical applica- tion domains. These algorithms can be quite complex—consisting of many tasks interconnected in processing graphs—and often must execute on complex heterogeneous hardware—typically multicore machines augmented with one or more hardware accelerators. To further complicate matters, these processing graphs often must be supported in contexts where a large system is broken into smaller components. With this confluence of factors, existing response-time analysis for processing graphs is not applicable. In this paper, such analysis is extended to address these complexities in systems where components are isolated via time partitioning. Additionally, graph restructuring methods are presented that enable response-time bounds to be reduced.

AI Meets Real-Time: Addressing Real-World Complexities in Graph Response-Time Analysis

Across a range of safety-critical domains, an evolution is underway to endow embedded systems with “thinking” capabilities by using artificial-intelligence (AI) techniques. This evolution is being fueled by the availability of high-performance embedded hardware, typically multicore machines augmented with accelerators. Unfortunately, existing software certification processes rely on time partitioning to isolate system components, and this sense of isolation can be broken by accelerator usage. To address this issue, this paper presents TimeWall, a time-partitioning framework for multicore+accelerator platforms. When applied alongside existing methods for alleviating spatial interference, TimeWall can help enable component-wise certification on multicore+accelerator platforms. The challenges in realizing a TimeWall implementation are discussed in detail in this paper. Additionally, the temporal isolation TimeWall affords is examined experimentally, including via a case study of a computer-vision perception application, on a real platform.

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

General-purpose graphics processing units (GPUs) made available on embedded platforms have gained much interest in real-time cyber-physical systems. Despite the fact that GPUs generally outperform CPUs on many compute-intensive tasks in a multitasking environment, high power consumption remains a challenging problem. In this paper, we first analyze the power and energy consumption of GPU kernels scheduled with spatial multitasking, which is found to be advantageous for schedulability in recent studies, and prove that its use, however, degrades energy efficiency even in the latest commercially available embedded GPUs like NVIDIA Jetson Xavier AGX. Then, based on our observations, we propose sBEET, a real-time energy-efficient GPU scheduling framework that makes scheduling decisions at runtime to optimize the energy consumption while utilizing spatial multitasking to improve real-time performance. We evaluate the performance of the proposed sBEET framework using well-known GPU benchmarks and randomly-generated timing parameters on real hardware. The results indicate that sBEET reduces deadline misses up to 13% when the system is overloaded, and also achieves 15% to 21% lower energy consumption when the tasksets are schedulable compared to the existing works.

Premium content

Evaluating Task Dropping Strategies for Overloaded Real-Time Systems

Downloads

Next from IEEE RTSS 2021

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

Similar lecture

AI Meets Real-Time: Addressing Real-World Complexities in Graph Response-Time Analysis

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES