Volume
LIPIcs, Volume 231
34th Euromicro Conference on Real-Time Systems (ECRTS 2022)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Euromicro Conference on Real-Time Systems (ECRTS)
Event
ECRTS 2022, July 5-8, 2022, Modena, ItalyEditor
Publication Details
- published at: 2022-06-28
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-239-6
- DBLP: db/conf/ecrts/ecrts2022
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 231, ECRTS 2022, Complete Volume
Abstract
LIPIcs, Volume 231, ECRTS 2022, Complete Volume
Cite as
34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 1-470, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@Proceedings{maggio:LIPIcs.ECRTS.2022,
title = {{LIPIcs, Volume 231, ECRTS 2022, Complete Volume}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {1--470},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022},
URN = {urn:nbn:de:0030-drops-163161},
doi = {10.4230/LIPIcs.ECRTS.2022},
annote = {Keywords: LIPIcs, Volume 231, ECRTS 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{maggio:LIPIcs.ECRTS.2022.0,
author = {Maggio, Martina},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {0:i--0:x},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.0},
URN = {urn:nbn:de:0030-drops-163176},
doi = {10.4230/LIPIcs.ECRTS.2022.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Industrial Challenge 2022: A High-Performance Real-Time Case Study on Arm
Abstract
High-performance real-time systems are becoming increasingly common in several application domains, including automotive, robotics, and embedded. To meet the growing performance requirements of the emerging applications, these systems often adopt a heterogeneous System-on-Chip hardware architecture comprising multiple high-performance CPUs and one or more domain-specific accelerators. At the same time, the applications running on these systems are subject to stringent real-time and safety requirements. Due to the non-deterministic execution model of the compute elements involved and the co-location of the workloads, which leads to contention of the shared hardware resources, designing and orchestrating such applications is particularly challenging. In fact, the demand for novel methodologies, tools, and best practices to assist application designers working on high-performance real-time systems has never been stronger.
To stimulate innovation in this area, this document outlines an industrial case study from the automotive domain targeting an Arm-based hardware platform. The selected application is an augmented reality head-up display, which can be considered a representative example of a high-performance real-time use case. This case study will serve as the basis for a (multi-year) challenge involving real-time and embedded systems researchers across academia and industry that will be kicked off at the 34superscript{th} Euromicro Conference on Real-Time Systems (ECRTS) 2022.
Cite as
Matteo Andreozzi, Giacomo Gabrielli, Balaji Venu, and Giacomo Travaglini. Industrial Challenge 2022: A High-Performance Real-Time Case Study on Arm. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{andreozzi_et_al:LIPIcs.ECRTS.2022.1,
author = {Andreozzi, Matteo and Gabrielli, Giacomo and Venu, Balaji and Travaglini, Giacomo},
title = {{Industrial Challenge 2022: A High-Performance Real-Time Case Study on Arm}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {1:1--1:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.1},
URN = {urn:nbn:de:0030-drops-163186},
doi = {10.4230/LIPIcs.ECRTS.2022.1},
annote = {Keywords: real-time, worst-case execution time}
}
Document
RTScale: Sensitivity-Aware Adaptive Image Scaling for Real-Time Object Detection
Abstract
Real-time object detection is crucial in autonomous driving. To avoid catastrophic accidents, an autonomous car should detect objects with multiple cameras and make decisions within a certain time limit. Object detection systems can meet the real-time constraint by dynamically downsampling input images to proper scales according to their time budget. However, simply applying the same scale to all the images from multiple cameras can cause unnecessary accuracy loss because downsampling can incur a significant accuracy loss for some images.
To reduce the accuracy loss while meeting the real-time constraint, this work proposes RTScale, a new adaptive real-time image scaling scheme that applies different scales to different images reflecting their sensitivities to the scaling and time budget. RTScale infers the sensitivities of multiple images from multiple cameras and determines an appropriate image scale for each image considering the real-time constraint. This work evaluates object detection accuracy and latency with RTScale for two driving datasets. The evaluation results show that RTScale can meet real-time constraints with minimal accuracy loss.
Cite as
Seonyeong Heo, Shinnung Jeong, and Hanjun Kim. RTScale: Sensitivity-Aware Adaptive Image Scaling for Real-Time Object Detection. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{heo_et_al:LIPIcs.ECRTS.2022.2,
author = {Heo, Seonyeong and Jeong, Shinnung and Kim, Hanjun},
title = {{RTScale: Sensitivity-Aware Adaptive Image Scaling for Real-Time Object Detection}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {2:1--2:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.2},
URN = {urn:nbn:de:0030-drops-163199},
doi = {10.4230/LIPIcs.ECRTS.2022.2},
annote = {Keywords: Real-time object detection, Dynamic neural network execution, Adaptive image scaling, Autonomous driving, Self-driving cars}
}
Document
ACETONE: Predictable Programming Framework for ML Applications in Safety-Critical Systems
Abstract
Machine learning applications have been gaining considerable attention in the field of safety-critical systems. Nonetheless, there is up to now no accepted development process that reaches classical safety confidence levels. This is the reason why we have developed a generic programming framework called ACETONE that is compliant with safety objectives (including traceability and WCET computation) for machine learning. More practically, the framework generates C code from a detailed description of off-line trained feed-forward deep neural networks that preserves the semantics of the original trained model and for which the WCET can be assessed with OTAWA. We have compared our results with Keras2c and uTVM with static runtime on a realistic set of benchmarks.
Cite as
Iryna De Albuquerque Silva, Thomas Carle, Adrien Gauffriau, and Claire Pagetti. ACETONE: Predictable Programming Framework for ML Applications in Safety-Critical Systems. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dealbuquerquesilva_et_al:LIPIcs.ECRTS.2022.3,
author = {De Albuquerque Silva, Iryna and Carle, Thomas and Gauffriau, Adrien and Pagetti, Claire},
title = {{ACETONE: Predictable Programming Framework for ML Applications in Safety-Critical Systems}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {3:1--3:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.3},
URN = {urn:nbn:de:0030-drops-163202},
doi = {10.4230/LIPIcs.ECRTS.2022.3},
annote = {Keywords: Real-time safety-critical systems, Worst Case Execution Time analysis, Artificial Neural Networks implementation}
}
Document
Using Quantile Regression in Neural Networks for Contention Prediction in Multicore Processors
Abstract
The development of multicore-based embedded real-time systems is a complex process that encompasses several phases. During the software design and development phases (DDP), and prior to the validation phase, key decisions are taken that cover several aspects of the system under development, from hardware selection and configuration, to the identification and mapping of software functions to the processing nodes. The timing dimension steers a large fraction of those decisions as the correctness of the final system ultimately depends on the implemented functions being able to execute within the allotted time budgets. Early execution time figures already in the DDP are thus needed to prevent flawed design decisions resulting in timing misbehavior being intercepted at the timing analysis step in the advanced development phases, when rolling back to different design decisions is extremely onerous. Multicore timing interference compounds this situation as it has been shown to largely impact execution time of tasks and, therefore, must be factored in when deriving early timing bounds. To effectively prevent misconfigurations while preserving resource efficiency, early timing estimates, typically derived from previous projects or early versions of the software functions, should conservatively and tightly overestimate the timing requirements of the final system configuration including multicore contention. In this work, we show that multi-linear regression (MLR) models and neural network (NN) models can be used to predict the impact of multicore contention on tasks' execution time and hence, derive contention-aware early time budgets, as soon as a release (binary) of the application is available. However, those techniques widely used in the mainstream domain minimize the average/mean case and the predicted impact of contention frequently underestimates the impact that can potentially arise at run time. In order to cover this gap, we propose the use of quantile regression neural networks (QRNN), which are specifically designed to predict the desired high quantile. QRNN reduces the number of underestimations compared to MLR and NN models while containing the overestimation by preserving the high quality prediction. For a set of workloads composed by representative kernels running on a NXP T2080 processor, QRNN reduces the number of underestimations to 8.8% compared to 46.8% and 31.3% for MLR and NN models respectively, while keeping the average over estimation in 1%. QRNN exposes a parameter, the target quantile, that allows controlling the behavior of the predictions so it adapts to user’s needs.
Cite as
Axel Brando, Isabel Serra, Enrico Mezzetti, Jaume Abella, and Francisco J. Cazorla. Using Quantile Regression in Neural Networks for Contention Prediction in Multicore Processors. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 4:1-4:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{brando_et_al:LIPIcs.ECRTS.2022.4,
author = {Brando, Axel and Serra, Isabel and Mezzetti, Enrico and Abella, Jaume and Cazorla, Francisco J.},
title = {{Using Quantile Regression in Neural Networks for Contention Prediction in Multicore Processors}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {4:1--4:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.4},
URN = {urn:nbn:de:0030-drops-163213},
doi = {10.4230/LIPIcs.ECRTS.2022.4},
annote = {Keywords: Neural Networks, Quantile Prediction, Multicore Contention}
}
Document
A Formal Link Between Response Time Analysis and Network Calculus
Abstract
Classical Response Time Analysis (RTA) and Network Calculus (NC) are two major formalisms used for the verification of real-time properties. We offer mathematical links between these two different theories. Based on these links, we then prove the equivalence of various key notions in both frameworks. This enables specialists of both formalisms to get increase confidence on their models, or even, like the authors, to discover errors in theorems by investigating apparent discrepancies between some notions expected to be equivalent. The presented mathematical results are all mechanically checked with the interactive theorem prover Coq, building on existing formalizations of RTA and NC. Establishing such a link between NC and RTA paves the way for improved real-time analyses obtained by combining both theories to enjoy their respective strengths (e.g., multicore analyses for RTA or clock drifts for NC).
Cite as
Pierre Roux, Sophie Quinton, and Marc Boyer. A Formal Link Between Response Time Analysis and Network Calculus. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{roux_et_al:LIPIcs.ECRTS.2022.5,
author = {Roux, Pierre and Quinton, Sophie and Boyer, Marc},
title = {{A Formal Link Between Response Time Analysis and Network Calculus}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {5:1--5:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.5},
URN = {urn:nbn:de:0030-drops-163224},
doi = {10.4230/LIPIcs.ECRTS.2022.5},
annote = {Keywords: Response Time Analysis, Network Calculus, dense time, discrete time, response time, formal proof, Coq}
}
Document
Unikernel-Based Real-Time Virtualization Under Deferrable Servers: Analysis and Realization
Abstract
For cyber-physical systems, real-time virtualization optimizes the hardware utilization by consolidating multiple systems into the same platform, while satisfying the timing constraints of their real-time tasks. This paper considers virtualization based on unikernels, i.e., single address space kernels usually constructed by using library operating systems. Each unikernel is a guest operating system in the virtualization and hosts a single real-time task.
We consider deferrable servers in the virtualization platform to schedule the unikernel-based guest operating systems and analyze the worst-case response time of a sporadic real-time task under such a virtualization architecture. Throughout synthesized tasksets, we empirically show that our analysis outperforms the restated analysis derived from the state-of-the-art, which is based on Real-Time Calculus. Furthermore, we provide insights on implementation-specific issues and offer evidence that the proposed scheduling architecture can be effectively implemented on top of the Xen hypervisor while incurring acceptable overhead.
Cite as
Kuan-Hsun Chen, Mario Günzel, Boguslaw Jablkowski, Markus Buschhoff, and Jian-Jia Chen. Unikernel-Based Real-Time Virtualization Under Deferrable Servers: Analysis and Realization. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:LIPIcs.ECRTS.2022.6,
author = {Chen, Kuan-Hsun and G\"{u}nzel, Mario and Jablkowski, Boguslaw and Buschhoff, Markus and Chen, Jian-Jia},
title = {{Unikernel-Based Real-Time Virtualization Under Deferrable Servers: Analysis and Realization}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {6:1--6:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.6},
URN = {urn:nbn:de:0030-drops-163239},
doi = {10.4230/LIPIcs.ECRTS.2022.6},
annote = {Keywords: Unikernel, Virtualization, Reservation Servers, Deferrable Servers, Cyber-Physical Systems, Real-Time Systems}
}
Document
A Mathematical Comparison Between Response-Time Analysis and Real-Time Calculus for Fixed-Priority Preemptive Scheduling
Abstract
Fixed-priority preemptive scheduling is a popular scheduling scheme for real-time systems. This is accompanied by a vast amount of research on how to analyse and check whether these systems satisfy their real-time requirements. Two methods that emerged from this research are the response-time analysis and the real-time calculus. These two methods have been compared empirically on the basis of several abstract systems showing that for some systems one method gives better results than the other and for other systems both methods appear to give the same results. However, empirical analyses inherently contain uncertainty. To get a definitive answer we compare both methods mathematically and we show that both methods give the same results for systems that use fixed-priority preemptive scheduling and independent tasks.
Cite as
Victor Pollex and Frank Slomka. A Mathematical Comparison Between Response-Time Analysis and Real-Time Calculus for Fixed-Priority Preemptive Scheduling. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{pollex_et_al:LIPIcs.ECRTS.2022.7,
author = {Pollex, Victor and Slomka, Frank},
title = {{A Mathematical Comparison Between Response-Time Analysis and Real-Time Calculus for Fixed-Priority Preemptive Scheduling}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {7:1--7:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.7},
URN = {urn:nbn:de:0030-drops-163246},
doi = {10.4230/LIPIcs.ECRTS.2022.7},
annote = {Keywords: real-time systems, fixed-priority scheduling, response-time analysis, real-time calculus}
}
Document
General Framework for Routing, Scheduling and Formal Timing Analysis in Deterministic Time-Aware Networks
Abstract
In deterministic time-aware networks, such as TTEthernet (TTE) and Time Sensitive Networking (TSN), time-triggered (TT) communication are often routed and scheduled without taking into account other critical traffic such as Rate-Constrained (RC) traffic. Consequently, the impact of a static transmission schedule for TT traffic can prevent RC traffic from fulfilling their timing constraints.
In this paper, we present a general framework for routing, scheduling and formal timing analysis (FTA) in deterministic time-aware networks (e.g. TSN, TTE). The general framework drives an iterative execution of different modules (i.e. routing, scheduling and FTA) searching for a solution that fulfills an arbitrary number of defined constraints (e.g. maximum end-to-end RC and TT latency) and optimization goals (e.g. minimize reception jitter). The result is an iteratively improved solution including the routing configuration for TT and RC flows, the static TT schedule, a formal analysis for the RC traffic, as well as any additional outputs satisfying user constraints (e.g. maximum RC jitter). We then do a performance evaluation of the general framework, with a proposed implementation of the necessary modules for TTEthernet networks with mixed time-triggered and rate-constrained traffic. The evaluation of our studied realistic use case shows that, using the general framework, the end-to-end latency for RC traffic can be reduced up to 28.3%, and the number of flows not fulfilling their deadlines divided by up to 3 compared to existing methods.
Cite as
Anaïs Finzi and Ramon Serna Oliver. General Framework for Routing, Scheduling and Formal Timing Analysis in Deterministic Time-Aware Networks. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{finzi_et_al:LIPIcs.ECRTS.2022.8,
author = {Finzi, Ana\"{i}s and Serna Oliver, Ramon},
title = {{General Framework for Routing, Scheduling and Formal Timing Analysis in Deterministic Time-Aware Networks}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {8:1--8:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.8},
URN = {urn:nbn:de:0030-drops-163254},
doi = {10.4230/LIPIcs.ECRTS.2022.8},
annote = {Keywords: TSN, TTEthernet, AFDX, AVB, Modeling, Routing, Scheduling, Formal timing analysis, Worst-case analysis, Performance evaluation}
}
Document
Correctness and Efficiency Criteria for the Multi-Phase Task Model
Abstract
This paper investigates how the multi-phase representation of real-time tasks impacts their implementation and the precision of the interference analysis in a multi-core context. In classical scheduling and interference analyses, tasks are represented as a single phase with a duration equal to their Worst-Case Execution Time (WCET) in isolation, annotated with their worst-case number of accesses. We propose a general formal definition of a task model in which tasks are represented as a sequence of such phases: the multi-phase model. We then provide a set of general correction criteria for the implementation of tasks represented in the multi-phase model, which is agnostic of the analysis method applied on the tasks. We also use the multi-phase model on an avionics case-study and study its impact on the interference analysis. Finally, we define a set of efficiency criteria using a statistical study of the most efficient multi-phase shapes.
Cite as
Rémi Meunier, Thomas Carle, and Thierry Monteil. Correctness and Efficiency Criteria for the Multi-Phase Task Model. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{meunier_et_al:LIPIcs.ECRTS.2022.9,
author = {Meunier, R\'{e}mi and Carle, Thomas and Monteil, Thierry},
title = {{Correctness and Efficiency Criteria for the Multi-Phase Task Model}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {9:1--9:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.9},
URN = {urn:nbn:de:0030-drops-163267},
doi = {10.4230/LIPIcs.ECRTS.2022.9},
annote = {Keywords: Task model, Interference, Multicore architectures}
}
Document
Overrun-Resilient Multiprocessor Real-Time Locking
Abstract
Existing real-time locking protocols require accurate worst-case execution time (WCET) estimates for both tasks and critical sections (CSs) in order to function correctly. On multicore platforms, however, the only seemingly viable strategy for obtaining such estimates is via measurements, which cannot produce a true WCET with certainty. The absence of correct WCETs can be partially ameliorated by enforcing execution budgets at both the task and CS levels and by using a locking protocol that is resilient to budget overruns, i.e., that ensures that the schedulability of non-overrunning tasks is not compromised by tasks that do overrun their budgets. Unfortunately, no fully overrun-resilient locking protocol has been proposed to date for multiprocessor systems. To remedy this situation, this paper presents two such protocols, the OR-FMLP and the OR-OMLP , which introduce overrun-resiliency mechanisms to two existing multiprocessor protocols, the spin-based FMLP and suspension-based global OMLP, respectively. In devising such mechanisms, undo code can be problematic. For the important locking use case of protecting shared data structures, it is shown that such code can be avoided entirely by using abortable critical sections, a concept proposed herein that leverages obstruction-free synchronization techniques. Experiments are presented that demonstrate both the effectiveness of the mechanisms introduced in this paper and their cost.
Cite as
Zelin Tong, Shareef Ahmed, and James H. Anderson. Overrun-Resilient Multiprocessor Real-Time Locking. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{tong_et_al:LIPIcs.ECRTS.2022.10,
author = {Tong, Zelin and Ahmed, Shareef and Anderson, James H.},
title = {{Overrun-Resilient Multiprocessor Real-Time Locking}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {10:1--10:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.10},
URN = {urn:nbn:de:0030-drops-163272},
doi = {10.4230/LIPIcs.ECRTS.2022.10},
annote = {Keywords: Real-Time Systems, Real-Time Synchronization, Budget Enforcement}
}
Document
Scheduling Offset-Free Systems Under FIFO Priority Protocol
Abstract
On UAVs, telemetry messages are often sent following a FIFO schedule, and some messages, depending on the FIFO queue state may suffer long delays, and can even be lost if the FIFO queue is full. Considering the high complexity of the problem of assigning offsets to periodic tasks, we propose a new heuristic, called GCD+, that we compare to the methods of the state of the art, showing that GCD+ significantly outperforms them on synthetic tasks sets. Then we use a real UAV use case, based on Paparazzi autopilot, to show that GCD+ behaves well. The proposed algorithm is meant to be the new Paparazzi’s automatic offset assignment method for messages.
Cite as
Matheus Ladeira, Emmanuel Grolleau, Fabien Bonneval, Gautier Hattenberger, Yassine Ouhammou, and Yuri Hérouard. Scheduling Offset-Free Systems Under FIFO Priority Protocol. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ladeira_et_al:LIPIcs.ECRTS.2022.11,
author = {Ladeira, Matheus and Grolleau, Emmanuel and Bonneval, Fabien and Hattenberger, Gautier and Ouhammou, Yassine and H\'{e}rouard, Yuri},
title = {{Scheduling Offset-Free Systems Under FIFO Priority Protocol}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {11:1--11:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.11},
URN = {urn:nbn:de:0030-drops-163281},
doi = {10.4230/LIPIcs.ECRTS.2022.11},
annote = {Keywords: Scheduling, non-preemptible, heuristics, FIFO, autopilot}
}
Document
Response-Time Analysis for Non-Preemptive Periodic Moldable Gang Tasks
Abstract
Gang scheduling has long been adopted by the high-performance computing community as a way to reduce the synchronization overhead between related threads. It allows for several threads to execute in lock steps without suffering from long busy-wait periods or be penalized by large context-switch overheads. When combined with non-preemptive execution, gang scheduling significantly reduces the execution time of threads that work on the same data by decreasing the number of memory transactions required to load or store the data. In this work, we focus on two main types of gang tasks: rigid and moldable. A moldable gang task has a presumed known minimum and maximum number of cores on which it can be executed at runtime, while a rigid gang task always executes on the same number of cores. This work presents the first response-time analysis for non-preemptive moldable gang tasks. Our analysis is based on the notion of schedule abstraction; a new approach for response-time analysis with the promise of high accuracy. Our experiments on periodic rigid gang tasks show that our analysis is 4.9 times more successful in identifying schedulable tasks than the existing utilization-based test for rigid gang tasks.
Cite as
Geoffrey Nelissen, Joan Marcè i Igual, and Mitra Nasri. Response-Time Analysis for Non-Preemptive Periodic Moldable Gang Tasks. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{nelissen_et_al:LIPIcs.ECRTS.2022.12,
author = {Nelissen, Geoffrey and Marc\`{e} i Igual, Joan and Nasri, Mitra},
title = {{Response-Time Analysis for Non-Preemptive Periodic Moldable Gang Tasks}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {12:1--12:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.12},
URN = {urn:nbn:de:0030-drops-163293},
doi = {10.4230/LIPIcs.ECRTS.2022.12},
annote = {Keywords: schedulability analysis, response time analysis, moldable gang tasks, rigid gang tasks, schedule abstraction graph, multiprocessor, non-preemptive}
}
Document
Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling
Abstract
The self-suspending task model proved to be particularly effective in capturing the timing behavior of real-time systems characterized by complex execution patterns, such as computation offloading to hardware accelerators, inter-core synchronization by means of multiprocessor locking protocols, and highly parallel computation. Most of the existing results for the timing analysis of self-suspending tasks do not support the widely adopted Earliest Deadline First (EDF) scheduling algorithm, being instead primarily focused on fixed-priority scheduling. This paper presents a response-time analysis for constrained-deadline self-suspending tasks scheduled under EDF on a uniprocessor system. The proposed analysis is based on a model transformation from self-suspending sporadic tasks to sporadic tasks with jitter, which can then be analyzed using a state-of-the-art analysis method for EDF scheduling. Experimental results are presented to compare the performance of the proposed technique in terms of schedulability ratio with that of the pessimistic suspension-oblivious approach and with a less general technique for task sets with implicit deadlines.
Cite as
Federico Aromolo, Alessandro Biondi, and Geoffrey Nelissen. Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{aromolo_et_al:LIPIcs.ECRTS.2022.13,
author = {Aromolo, Federico and Biondi, Alessandro and Nelissen, Geoffrey},
title = {{Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {13:1--13:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.13},
URN = {urn:nbn:de:0030-drops-163306},
doi = {10.4230/LIPIcs.ECRTS.2022.13},
annote = {Keywords: Real-Time Systems, Schedulability Analysis, Self-Suspending Tasks, EDF Scheduling}
}
Document
An Approach to Formally Specifying the Behaviour of Mixed-Criticality Systems
Abstract
This paper proposes a formal framework for describing the relationship between a criticality-aware scheduler and a set of application tasks that are assigned different criticality levels. The exposition employs a series of examples starting with scheduling simple jobs and then moving on to mixed-criticality robust and resilient tasks. The proposed formalism extends the rely-guarantee approach, which facilitates formal reasoning about the functional behaviour of concurrent systems, to address real-time properties.
Cite as
A. Burns and Cliff B. Jones. An Approach to Formally Specifying the Behaviour of Mixed-Criticality Systems. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{burns_et_al:LIPIcs.ECRTS.2022.14,
author = {Burns, A. and Jones, Cliff B.},
title = {{An Approach to Formally Specifying the Behaviour of Mixed-Criticality Systems}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {14:1--14:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.14},
URN = {urn:nbn:de:0030-drops-163315},
doi = {10.4230/LIPIcs.ECRTS.2022.14},
annote = {Keywords: real-time, scheduling, mixed criticality, rely/guaranteed conditions}
}
Document
Achieving Isolation in Mixed-Criticality Industrial Edge Systems with Real-Time Containers
Abstract
Real-time containers are a promising solution to reduce latencies in time-sensitive cloud systems. Recent efforts are emerging to extend their usage in industrial edge systems with mixed-criticality constraints. In these contexts, isolation becomes a major concern: a disturbance (such as timing faults or unexpected overloads) affecting a container must not impact the behavior of other containers deployed on the same hardware. In this paper, we propose a novel architectural solution to achieve isolation in real-time containers, based on real-time co-kernels, hierarchical scheduling, and time-division networking. The architecture has been implemented on Linux patched with the Xenomai co-kernel, extended with a new hierarchical scheduling policy, named SCHED_DS, and integrating the RTNet stack. Experimental results are promising in terms of overhead and latency compared to other Linux-based solutions. More importantly, the isolation of containers is guaranteed even in presence of severe co-located disturbances, such as faulty tasks (elapsing more time than declared) or high CPU, network, or I/O stress on the same machine.
Cite as
Marco Barletta, Marcello Cinque, Luigi De Simone, and Raffaele Della Corte. Achieving Isolation in Mixed-Criticality Industrial Edge Systems with Real-Time Containers. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{barletta_et_al:LIPIcs.ECRTS.2022.15,
author = {Barletta, Marco and Cinque, Marcello and De Simone, Luigi and Della Corte, Raffaele},
title = {{Achieving Isolation in Mixed-Criticality Industrial Edge Systems with Real-Time Containers}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {15:1--15:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.15},
URN = {urn:nbn:de:0030-drops-163328},
doi = {10.4230/LIPIcs.ECRTS.2022.15},
annote = {Keywords: Real-time, Mixed-criticality, Containers, Edge computing}
}
Document
Parallelism-Aware High-Performance Cache Coherence with Tight Latency Bounds
Abstract
In Commercial-Off-The-Shelf (COTS) systems-on-chip, processing elements communicate data through a shared memory hierarchy, and a coherent high-performance interconnect, where the de facto standard to handle shared data is through a coherence protocol. Driven by the extraordinary demands from modern real-time embedded system applications to generate, process, and communicate massive amounts of data, recent efforts aim to ensure timing predictability while integrating cache coherence in multi-core real-time systems. However, we observe that most of these efforts compromise system average performance upon offering predictability guarantees. Motivated by this observation, this work proposes an arbiter aimed at providing a predictable, coherent shared cache hierarchy solution, yet with a negligible performance degradation compared to COTS solutions. We achieve this goal by adopting a high-performance-driven architecture including a split-transaction bus and bankized shared cache. In addition, all accesses are arbitrated through a global ordering mechanism. Our proposed arbiter operates alongside conventional coherence protocols without requiring any protocol modifications. Furthermore, we leverage the Duetto reference model by pairing the proposed arbiter and a high-performance arbiter. We evaluate our solution based on both synthetic and SPLASH-3 benchmarks, showing that we can significantly outperform the state-of-the-art in predictable cache coherence, while offering a COTS-level performance.
Cite as
Reza Mirosanlou, Mohamed Hassan, and Rodolfo Pellizzoni. Parallelism-Aware High-Performance Cache Coherence with Tight Latency Bounds. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 16:1-16:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{mirosanlou_et_al:LIPIcs.ECRTS.2022.16,
author = {Mirosanlou, Reza and Hassan, Mohamed and Pellizzoni, Rodolfo},
title = {{Parallelism-Aware High-Performance Cache Coherence with Tight Latency Bounds}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {16:1--16:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.16},
URN = {urn:nbn:de:0030-drops-163330},
doi = {10.4230/LIPIcs.ECRTS.2022.16},
annote = {Keywords: Predictability, Cache, COTS, Arbitration, Real-time system}
}
Document
Predictably and Efficiently Integrating COTS Cache Coherence in Real-Time Systems
Abstract
The adoption of multi-core platforms in embedded real-time systems mandates predictable system components. Such components must guarantee the satisfaction of the timing constraints of various applications running on the system. One of the components that can break the system predictability is cache coherence, which ensures the correctness of shared data. This paper proposes a solution towards the enablement of predictable cache coherent real-time systems. The solution uses existing COTS coherence protocols and proposes a methodology to integrate them with legacy real-time arbiters without imposing any required modification to either of them. Doing so, the paper also works as an exploratory study of the integration of various coherence protocols with various predictable arbitration schemes leading to a total of 12 different architecture configurations. Evaluation against four state-of-the-art predictable coherence solutions as well as COTS-based solutions show that the proposed approach achieves the tightest existing latency bounds among predictable solutions with minimal performance degradation over the COTS ones.
Cite as
Mohamed Hossam and Mohamed Hassan. Predictably and Efficiently Integrating COTS Cache Coherence in Real-Time Systems. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{hossam_et_al:LIPIcs.ECRTS.2022.17,
author = {Hossam, Mohamed and Hassan, Mohamed},
title = {{Predictably and Efficiently Integrating COTS Cache Coherence in Real-Time Systems}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {17:1--17:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.17},
URN = {urn:nbn:de:0030-drops-163345},
doi = {10.4230/LIPIcs.ECRTS.2022.17},
annote = {Keywords: Coherence, Shared Data, Caches, Multi-Core, Real-Time, Memory}
}
Document
RT-DFI: Optimizing Data-Flow Integrity for Real-Time Systems
Abstract
The emergence of Real-Time Systems with increased connections to their environment has led to a greater demand in security for these systems. Memory corruption attacks, which modify the memory to trigger unexpected executions, are a significant threat against applications written in low-level languages. Data-Flow Integrity (DFI) is a protection that verifies that only a trusted source has written any loaded data. The overhead of such a security mechanism remains a major issue that limits its adoption. This article presents RT-DFI, a new approach that optimizes Data-Flow Integrity to reduce its overhead on the Worst-Case Execution Time. We model the number and order of the checks and use an Integer Linear Programming solver to optimize the protection on the Worst-Case Execution Path. Our approach protects the program against many memory-corruption attacks, including Return-Oriented Programming and Data-Only attacks. Moreover, our experimental results show that our optimization reduces the overhead by 7% on average compared to a state-of-the-art implementation.
Cite as
Nicolas Bellec, Guillaume Hiet, Simon Rokicki, Frederic Tronel, and Isabelle Puaut. RT-DFI: Optimizing Data-Flow Integrity for Real-Time Systems. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 18:1-18:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bellec_et_al:LIPIcs.ECRTS.2022.18,
author = {Bellec, Nicolas and Hiet, Guillaume and Rokicki, Simon and Tronel, Frederic and Puaut, Isabelle},
title = {{RT-DFI: Optimizing Data-Flow Integrity for Real-Time Systems}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {18:1--18:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.18},
URN = {urn:nbn:de:0030-drops-163351},
doi = {10.4230/LIPIcs.ECRTS.2022.18},
annote = {Keywords: Real-time system, Software security, Data-flow integrity, Worst-case execution time}
}
Document
Foundational Response-Time Analysis as Explainable Evidence of Timeliness
Abstract
The paper introduces foundational response-time analysis (RTA) as a means to produce strong and independently checkable evidence of temporal correctness. In a foundational RTA, each response-time bound calculated comes with an auto-generated certificate of correctness - a short and human-inspectable sequence of machine-checked proofs that formally show the claimed bound to hold. In other words, a foundational RTA yields explainable results that can be independently verified (e.g., by a certification authority) in a rigorous manner (with an automated proof checker). Consequently, the analysis tool itself does not need to be verified nor trusted. As a proof of concept, the paper presents POET, the first foundational RTA tool. POET generates certificates based on Prosa, the to-date largest verified framework for schedulability analysis, which is based on Coq. The trusted computing base is hence reduced to the Coq proof checker and its dependencies. POET currently supports two scheduling policies (earliest-deadline-first, fixed-priority), two preemption models (fully preemptive, fully non-preemptive), arbitrary deadlines, periodic and sporadic tasks, and tasks characterized by arbitrary arrival curves. The paper describes the challenges inherent in the development of a foundational RTA tool, discusses key design choices, and reports on its scalability.
Cite as
Marco Maida, Sergey Bozhko, and Björn B. Brandenburg. Foundational Response-Time Analysis as Explainable Evidence of Timeliness. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 19:1-19:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{maida_et_al:LIPIcs.ECRTS.2022.19,
author = {Maida, Marco and Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
title = {{Foundational Response-Time Analysis as Explainable Evidence of Timeliness}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {19:1--19:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.19},
URN = {urn:nbn:de:0030-drops-163363},
doi = {10.4230/LIPIcs.ECRTS.2022.19},
annote = {Keywords: hard real-time systems, response-time analysis, uniprocessor, Coq, Prosa, fixed priority, EDF, preemptive, non-preemptive, verification}
}
Document
Using Markov’s Inequality with Power-Of-k Function for Probabilistic WCET Estimation
Abstract
Deriving WCET estimates for software programs with probabilistic means (a.k.a. pWCET estimation) has received significant attention during last years as a way to deal with the increased complexity of the processors used in real-time systems. Many works build on Extreme Value Theory (EVT) that is fed with a sample of the collected data (execution times). In its application, EVT carries two sources of uncertainty: the first one that is intrinsic to the EVT model and relates to determining the subset of the sample that belongs to the (upper) tail, and hence, is actually used by EVT for prediction; and the second one that is induced by the sampling process and hence is inherent to all sample-based methods. In this work, we show that Markov’s inequality can be used to obtain provable trustworthy probabilistic bounds to the tail of a distribution without incurring any model-intrinsic uncertainty. Yet, it produces pessimistic estimates that we shave substantially by proposing the use of a power-of-k function instead of the default identity function used by Markov’s inequality. Lastly, we propose a method to deal with sampling uncertainty for Markov’s inequality that consistently improves EVT estimates on synthetic and real data obtained from a railway application.
Cite as
Sergi Vilardell, Isabel Serra, Enrico Mezzetti, Jaume Abella, Francisco J. Cazorla, and Joan del Castillo. Using Markov’s Inequality with Power-Of-k Function for Probabilistic WCET Estimation. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 20:1-20:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{vilardell_et_al:LIPIcs.ECRTS.2022.20,
author = {Vilardell, Sergi and Serra, Isabel and Mezzetti, Enrico and Abella, Jaume and Cazorla, Francisco J. and del Castillo, Joan},
title = {{Using Markov’s Inequality with Power-Of-k Function for Probabilistic WCET Estimation}},
booktitle = {34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
pages = {20:1--20:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-239-6},
ISSN = {1868-8969},
year = {2022},
volume = {231},
editor = {Maggio, Martina},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.20},
URN = {urn:nbn:de:0030-drops-163377},
doi = {10.4230/LIPIcs.ECRTS.2022.20},
annote = {Keywords: Markov’s inequality, probabilistic time estimates, probabilistic WCET, Extreme Value Theory}
}