Germany

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.

IEEE RTSS 2021

Partitioned Scheduling of Recurrent Real-Time Tasks

partitioned simultaneous congruence

unrelated (heterogeneous) multiprocessors

sporadic and periodic tasks

task analysis

complexity theory

upper bound

computational complexity

processor scheduling

real-time systems

partitioned scheduling

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

Today’s deeply embedded systems, with real-time interactions to the environment, are largely battery-operated, and peripheral modules like LTE, WiFi, and GPS are among the most energy-hungry components of them. These components are often under the direct control of an embedded software. Some pieces of the software program are called energy hotspots if they can be transformed towards better system energy consumption while leaving it logically- and temporally-correct. This paper focuses on three such energy hotspots from the peripheral module perspective. The root causes of the hotspots in the software program are misplaced driver calls: Early acquiring or late releasing of the module causes it to waste energy in the active state, having unnecessary distance between the use operations causes extra tail energy overhead, and unaccounted releasing and re-acquiring of the module causes more energy consumption in comparison to leaving the module unreleased. We provide static analysis methods for the detection and elimination of such energy hotspots automatically with regard to some relations between temporal requirements of the real-time embedded software, the time and energy specifications of the module, and the extreme (worst-case/best-case) execution times of specific pieces of the software program. Our simulation results show about 4.7 to 20 percent of energy reductions after elimination of the energy hotspots of the test programs using our proposed method.

Automatic Energy-Hotspot Detection and Elimination in Real-Time Deeply Embedded Systems,

In mixed-criticality systems (MCSs), less-critical tasks are often terminated to ensure the correct execution of high critical tasks. This strategy could however lead to safety hazards, and largely reduce system functionality due to the absence of the discarded tasks. To overcome this problem, we introduce a high resilience and approximated computing framework for MCS, i.e., HIART-MCS. HIART-MCS introduces a novel processor which supports approximation at the hardware level. Associated with this, we also introduce a new intermediate system mode which allows less-critical tasks to be executed with reduced precision instead of being directly dropped out. Corresponding to the HIART-MCS, we further present a new theoretical model and schedulability analysis providing a timing guarantee for the system, followed by optimisations of the mode switch strategy. As demonstrated in both the theoretical and practical evaluations, HIART-MCS effectively improves the survivability of less-critical tasks with limited sacrifice of the critical tasks and negligible extra overhead. It is notable that HIART-MCS is the first practical framework for imprecise MCSs.

HIART-MCS: High Resilience and Approximated Computing Architecture for Imprecise Mixed-Criticality Systems

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 TeamPlay Coordination Language for Mission-critical Cyber-physical Systems


Scheduling Adaptive Dataflow Applications in Safety-critical Cyber-physical Systems

Designing Adaptive Avionics Embedded Systems

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

Partitioned Scheduling of Recurrent Real-Time Tasks

Downloads

Next from IEEE RTSS 2021

Automatic Energy-Hotspot Detection and Elimination in Real-Time Deeply Embedded Systems,

Similar lecture

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