Volume
LIPIcs, Volume 165
32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Euromicro Conference on Real-Time Systems (ECRTS)
Event
ECRTS 2020, July 7-10, 2020, Virtual ConferenceEditor
Publication Details
- published at: 2020-06-30
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-152-8
- DBLP: db/conf/ecrts/ecrts2020
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 165, ECRTS 2020, Complete Volume
Abstract
LIPIcs, Volume 165, ECRTS 2020, Complete Volume
Cite as
32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 1-578, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@Proceedings{volp:LIPIcs.ECRTS.2020,
title = {{LIPIcs, Volume 165, ECRTS 2020, Complete Volume}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {1--578},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020},
URN = {urn:nbn:de:0030-drops-123626},
doi = {10.4230/LIPIcs.ECRTS.2020},
annote = {Keywords: LIPIcs, Volume 165, ECRTS 2020, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{volp:LIPIcs.ECRTS.2020.0,
author = {V\"{o}lp, Marcus},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {0:i--0:xiv},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.0},
URN = {urn:nbn:de:0030-drops-123631},
doi = {10.4230/LIPIcs.ECRTS.2020.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Fixed-Priority Memory-Centric Scheduler for COTS-Based Multiprocessors
Abstract
Memory-centric scheduling attempts to guarantee temporal predictability on commercial-off-the-shelf (COTS) multiprocessor systems to exploit their high performance for real-time applications. Several solutions proposed in the real-time literature have hardware requirements that are not easily satisfied by modern COTS platforms, like hardware support for strict memory partitioning or the presence of scratchpads. However, even without said hardware support, it is possible to design an efficient memory-centric scheduler.
In this article, we design, implement, and analyze a memory-centric scheduler for deterministic memory management on COTS multiprocessor platforms without any hardware support. Our approach uses fixed-priority scheduling and proposes a global "memory preemption" scheme to boost real-time schedulability. The proposed scheduling protocol is implemented in the Jailhouse hypervisor and Erika real-time kernel. Measurements of the scheduler overhead demonstrate the applicability of the proposed approach, and schedulability experiments show a 20% gain in terms of schedulability when compared to contention-based and static fair-share approaches.
Cite as
Gero Schwäricke, Tomasz Kloda, Giovani Gracioli, Marko Bertogna, and Marco Caccamo. Fixed-Priority Memory-Centric Scheduler for COTS-Based Multiprocessors. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{schwaricke_et_al:LIPIcs.ECRTS.2020.1,
author = {Schw\"{a}ricke, Gero and Kloda, Tomasz and Gracioli, Giovani and Bertogna, Marko and Caccamo, Marco},
title = {{Fixed-Priority Memory-Centric Scheduler for COTS-Based Multiprocessors}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {1:1--1:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.1},
URN = {urn:nbn:de:0030-drops-123648},
doi = {10.4230/LIPIcs.ECRTS.2020.1},
annote = {Keywords: Schedulability Analysis, Scheduler Implementation, memory-centric Scheduling, Virtualization, Multiprocessor}
}
Document
CPU Energy-Aware Parallel Real-Time Scheduling
Abstract
Both energy-efficiency and real-time performance are critical requirements in many embedded systems applications such as self-driving car, robotic system, disaster response, and security/safety control. These systems entail a myriad of real-time tasks, where each task itself is a parallel task that can utilize multiple computing units at the same time. Driven by the increasing demand for parallel tasks, multi-core embedded processors are inevitably evolving to many-core. Existing work on real-time parallel tasks mostly focused on real-time scheduling without addressing energy consumption. In this paper, we address hard real-time scheduling of parallel tasks while minimizing their CPU energy consumption on multicore embedded systems. Each task is represented as a directed acyclic graph (DAG) with nodes indicating different threads of execution and edges indicating their dependencies. Our technique is to determine the execution speeds of the nodes of the DAGs to minimize the overall energy consumption while meeting all task deadlines. It incorporates a frequency optimization engine and the dynamic voltage and frequency scaling (DVFS) scheme into the classical real-time scheduling policies (both federated and global) and makes them energy-aware. The contributions of this paper thus include the first energy-aware online federated scheduling and also the first energy-aware global scheduling of DAGs. Evaluation using synthetic workload through simulation shows that our energy-aware real-time scheduling policies can achieve up to 68% energy-saving compared to classical (energy-unaware) policies. We have also performed a proof of concept system evaluation using physical hardware demonstrating the energy efficiency through our proposed approach.
Cite as
Abusayeed Saifullah, Sezana Fahmida, Venkata P. Modekurthy, Nathan Fisher, and Zhishan Guo. CPU Energy-Aware Parallel Real-Time Scheduling. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 2:1-2:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{saifullah_et_al:LIPIcs.ECRTS.2020.2,
author = {Saifullah, Abusayeed and Fahmida, Sezana and Modekurthy, Venkata P. and Fisher, Nathan and Guo, Zhishan},
title = {{CPU Energy-Aware Parallel Real-Time Scheduling}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {2:1--2:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.2},
URN = {urn:nbn:de:0030-drops-123655},
doi = {10.4230/LIPIcs.ECRTS.2020.2},
annote = {Keywords: Real-time scheduling, multicore, energy-efficiency, embedded systems}
}
Document
PAStime: Progress-Aware Scheduling for Time-Critical Computing
Abstract
Over-estimation of worst-case execution times (WCETs) of real-time tasks leads to poor resource utilization. In a mixed-criticality system (MCS), the over-provisioning of CPU time to accommodate the WCETs of highly critical tasks may lead to degraded service for less critical tasks. In this paper we present PAStime, a novel approach to monitor and adapt the runtime progress of highly time-critical applications, to allow for improved service to lower criticality tasks. In PAStime, CPU time is allocated to time-critical tasks according to the delays they experience as they progress through their control flow graphs. This ensures that as much time as possible is made available to improve the Quality-of-Service of less critical tasks, while high-criticality tasks are compensated after their delays.
This paper describes the integration of PAStime with Adaptive Mixed-criticality (AMC) scheduling. The LO-mode budget of a high-criticality task is adjusted according to the delay observed at execution checkpoints. This is the first implementation of AMC in the scheduling framework of LITMUS^RT, which is extended with our PAStime runtime policy and tested with real-time Linux applications such as object classification and detection. We observe in our experimental evaluation that AMC-PAStime significantly improves the utilization of the low-criticality tasks while guaranteeing service to high-criticality tasks.
Cite as
Soham Sinha, Richard West, and Ahmad Golchin. PAStime: Progress-Aware Scheduling for Time-Critical Computing. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{sinha_et_al:LIPIcs.ECRTS.2020.3,
author = {Sinha, Soham and West, Richard and Golchin, Ahmad},
title = {{PAStime: Progress-Aware Scheduling for Time-Critical Computing}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {3:1--3:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.3},
URN = {urn:nbn:de:0030-drops-123668},
doi = {10.4230/LIPIcs.ECRTS.2020.3},
annote = {Keywords: progress-aware scheduling, code instrumentation, timing annotation}
}
Document
Dynamic Interference-Sensitive Run-time Adaptation of Time-Triggered Schedules
Abstract
Over-approximated Worst-Case Execution Time (WCET) estimations for multi-cores lead to safe, but over-provisioned, systems and underutilized cores. To reduce WCET pessimism, interference-sensitive WCET (isWCET) estimations are used. Although they provide tighter WCET bounds, they are valid only for a specific schedule solution. Existing approaches have to maintain this isWCET schedule solution at run-time, via time-triggered execution, in order to be safe. Hence, any earlier execution of tasks, enabled by adapting the isWCET schedule solution, is not possible. In this paper, we present a dynamic approach that safely adapts isWCET schedules during execution, by relaxing or completely removing isWCET schedule dependencies, depending on the progress of each core. In this way, an earlier task execution is enabled, creating time slack that can be used by safety-critical and mixed-criticality systems to provide higher Quality-of-Services or execute other best-effort applications. The Response-Time Analysis (RTA) of the proposed approach is presented, showing that although the approach is dynamic, it is fully predictable with bounded WCET. To support our contribution, we evaluate the behavior and the scalability of the proposed approach for different application types and execution configurations on the 8-core Texas Instruments TMS320C6678 platform, obtaining significant performance improvements compared to static approaches.
Cite as
Stefanos Skalistis and Angeliki Kritikakou. Dynamic Interference-Sensitive Run-time Adaptation of Time-Triggered Schedules. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{skalistis_et_al:LIPIcs.ECRTS.2020.4,
author = {Skalistis, Stefanos and Kritikakou, Angeliki},
title = {{Dynamic Interference-Sensitive Run-time Adaptation of Time-Triggered Schedules}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {4:1--4:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.4},
URN = {urn:nbn:de:0030-drops-123673},
doi = {10.4230/LIPIcs.ECRTS.2020.4},
annote = {Keywords: Worst-Case Execution Time, Interference-sensitive, Run-time Adaptation, Time-Triggered, Response Time Analysis, Multi-cores}
}
Document
Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning
Abstract
Schedulability analyses for preemptive real-time systems need to take into account cache-related preemption delays (CRPD) caused by preemptions between the tasks. The estimation of the CRPD values must be sound, i.e. it must not be lower than the worst-case CRPD that may occur at runtime, but also should minimise the pessimism of estimation. The existing methods over-approximate the computed CRPD upper bounds by accounting for multiple preemption combinations which cannot occur simultaneously during runtime. This over-approximation may further lead to the over-approximation of the worst-case response times of the tasks, and therefore a false-negative estimation of the system’s schedulability. In this paper, we propose a more precise cache-aware response time analysis for sporadic real-time systems under fully-preemptive fixed priority scheduling. The evaluation shows a significant improvement over the existing state of the art approaches.
Cite as
Filip Marković, Jan Carlson, Sebastian Altmeyer, and Radu Dobrin. Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{markovic_et_al:LIPIcs.ECRTS.2020.5,
author = {Markovi\'{c}, Filip and Carlson, Jan and Altmeyer, Sebastian and Dobrin, Radu},
title = {{Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {5:1--5:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.5},
URN = {urn:nbn:de:0030-drops-123682},
doi = {10.4230/LIPIcs.ECRTS.2020.5},
annote = {Keywords: Real-time systems, Fixed-Priority Preemptive Scheduling, Preemption delay}
}
Document
Nested, but Separate: Isolating Unrelated Critical Sections in Real-Time Nested Locking
Abstract
Prior work has produced multiprocessor real-time locking protocols that ensure asymptotically optimal bounds on priority inversion, that support fine-grained nesting of critical sections, or that are independence-preserving under clustered scheduling. However, while several protocols manage to come with two out of these three desirable features, no protocol to date accomplishes all three. Motivated by this gap in capabilities, this paper introduces the Group Independence-Preserving Protocol (GIPP), the first protocol to support fine-grained nested locking, guarantee a notion of independence preservation for fine-grained nested locking, and ensure asymptotically optimal priority-inversion bounds. As a stepping stone, this paper further presents the Clustered k-Exclusion Independence-Preserving Protocol (CKIP), the first asymptotically optimal independence-preserving k-exclusion lock for clustered scheduling. The GIPP and the CKIP rely on allocation inheritance (a.k.a. migratory priority inheritance) as a key mechanism to accomplish independence preservation.
Cite as
James Robb and Björn B. Brandenburg. Nested, but Separate: Isolating Unrelated Critical Sections in Real-Time Nested Locking. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{robb_et_al:LIPIcs.ECRTS.2020.6,
author = {Robb, James and Brandenburg, Bj\"{o}rn B.},
title = {{Nested, but Separate: Isolating Unrelated Critical Sections in Real-Time Nested Locking}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {6:1--6:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.6},
URN = {urn:nbn:de:0030-drops-123691},
doi = {10.4230/LIPIcs.ECRTS.2020.6},
annote = {Keywords: multiprocessor real-time locking, nested locking, independence preservation, suspension-oblivious analysis, priority inversion, asymptotically optimal blocking, RNLP, OMIP}
}
Document
The Safe and Effective Use of Learning-Enabled Components in Safety-Critical Systems
Abstract
Autonomous systems increasingly use components that incorporate machine learning and other AI-based techniques in order to achieve improved performance. The problem of assuring correctness in safety-critical systems that use such components is considered. A model is proposed in which components are characterized according to both their worst-case and their typical behaviors; it is argued that while safety must be assured under all circumstances, it is reasonable to be concerned with providing a high degree of performance for typical behaviors only. The problem of assuring safety while providing such improved performance is formulated as an optimization problem in which performance under typical circumstances is the objective function to be optimized while safety is a hard constraint that must be satisfied. Algorithmic techniques are applied to derive an optimal solution to this optimization problem. This optimal solution is compared with an alternative approach that optimizes for performance under worst-case conditions, as well as some common-sense heuristics, via simulation experiments on synthetically-generated workloads.
Cite as
Kunal Agrawal, Sanjoy Baruah, and Alan Burns. The Safe and Effective Use of Learning-Enabled Components in Safety-Critical Systems. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2020.7,
author = {Agrawal, Kunal and Baruah, Sanjoy and Burns, Alan},
title = {{The Safe and Effective Use of Learning-Enabled Components in Safety-Critical Systems}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {7:1--7:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.7},
URN = {urn:nbn:de:0030-drops-123704},
doi = {10.4230/LIPIcs.ECRTS.2020.7},
annote = {Keywords: Learning-enabled components (LECs), Safety-critical systems, Typical analysis, Performance optimization, Run-time monitoring}
}
Document
Attack Detection Through Monitoring of Timing Deviations in Embedded Real-Time Systems
Abstract
Real-time embedded systems (RTES) are required to interact more and more with their environment, thereby increasing their attack surface. Recent security breaches on car brakes and other critical components have already proven the feasibility of attacks on RTES. Such attacks may change the control-flow of the programs, which may lead to violations of the system’s timing constraints.
In this paper, we present a technique to detect attacks in RTES based on timing information. Our technique, designed for single-core processors, is based on a monitor implemented in hardware to preserve the predictability of instrumented programs. The monitor uses timing information (Worst-Case Execution Time - WCET) of code regions to detect attacks. The proposed technique guarantees that attacks that delay the run-time of any region beyond its WCET are detected. Since the number of regions in programs impacts the memory resources consumed by the hardware monitor, our method includes a region selection algorithm that limits the amount of memory consumed by the monitor. An implementation of the hardware monitor and its simulation demonstrates the practicality of our approach. In particular, an experimental study evaluates the attack detection latency.
Cite as
Nicolas Bellec, Simon Rokicki, and Isabelle Puaut. Attack Detection Through Monitoring of Timing Deviations in Embedded Real-Time Systems. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bellec_et_al:LIPIcs.ECRTS.2020.8,
author = {Bellec, Nicolas and Rokicki, Simon and Puaut, Isabelle},
title = {{Attack Detection Through Monitoring of Timing Deviations in Embedded Real-Time Systems}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {8:1--8:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.8},
URN = {urn:nbn:de:0030-drops-123719},
doi = {10.4230/LIPIcs.ECRTS.2020.8},
annote = {Keywords: Real-time systems, security, attack detection, control flow hijacking, WCET estimation, hardware monitoring}
}
Document
Demystifying the Real-Time Linux Scheduling Latency
Abstract
Linux has become a viable operating system for many real-time workloads. However, the black-box approach adopted by cyclictest, the tool used to evaluate the main real-time metric of the kernel, the scheduling latency, along with the absence of a theoretically-sound description of the in-kernel behavior, sheds some doubts about Linux meriting the real-time adjective. Aiming at clarifying the PREEMPT_RT Linux scheduling latency, this paper leverages the Thread Synchronization Model of Linux to derive a set of properties and rules defining the Linux kernel behavior from a scheduling perspective. These rules are then leveraged to derive a sound bound to the scheduling latency, considering all the sources of delays occurring in all possible sequences of synchronization events in the kernel. This paper also presents a tracing method, efficient in time and memory overheads, to observe the kernel events needed to define the variables used in the analysis. This results in an easy-to-use tool for deriving reliable scheduling latency bounds that can be used in practice. Finally, an experimental analysis compares the cyclictest and the proposed tool, showing that the proposed method can find sound bounds faster with acceptable overheads.
Cite as
Daniel Bristot de Oliveira, Daniel Casini, Rômulo Silva de Oliveira, and Tommaso Cucinotta. Demystifying the Real-Time Linux Scheduling Latency. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{deoliveira_et_al:LIPIcs.ECRTS.2020.9,
author = {de Oliveira, Daniel Bristot and Casini, Daniel and de Oliveira, R\^{o}mulo Silva and Cucinotta, Tommaso},
title = {{Demystifying the Real-Time Linux Scheduling Latency}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {9:1--9:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.9},
URN = {urn:nbn:de:0030-drops-123721},
doi = {10.4230/LIPIcs.ECRTS.2020.9},
annote = {Keywords: Real-time operating systems, Linux kernel, PREEMPT\underlineRT, Scheduling latency}
}
Document
AMD GPUs as an Alternative to NVIDIA for Supporting Real-Time Workloads
Abstract
Graphics processing units (GPUs) manufactured by NVIDIA continue to dominate many fields of research, including real-time GPU-management. NVIDIA’s status as a key enabling technology for deep learning and image processing makes this unsurprising, especially when combined with the company’s push into embedded, safety-critical domains like autonomous driving. NVIDIA’s primary competitor, AMD, has received comparatively little attention, due in part to few embedded offerings and a lack of support from popular deep-learning toolkits. Recently, however, AMD’s ROCm (Radeon Open Compute) software platform was made available to address at least the second of these two issues, but is ROCm worth the attention of safety-critical software developers? In order to answer this question, this paper explores the features and pitfalls of AMD GPUs, focusing on contrasting details with NVIDIA’s GPU hardware and software. We argue that an open software stack such as ROCm may be able to provide much-needed flexibility and reproducibility in the context of real-time GPU research, where new algorithmic or analysis techniques should typically remain agnostic to the underlying GPU architecture. In support of this claim, we summarize how closed-source platforms have obstructed prior research using NVIDIA GPUs, and then demonstrate that AMD may be a viable alternative by modifying components of the ROCm software stack to implement spatial partitioning. Finally, we present a case study using the PyTorch deep-learning framework that demonstrates the impact such modifications can have on complex real-world software.
Cite as
Nathan Otterness and James H. Anderson. AMD GPUs as an Alternative to NVIDIA for Supporting Real-Time Workloads. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{otterness_et_al:LIPIcs.ECRTS.2020.10,
author = {Otterness, Nathan and Anderson, James H.},
title = {{AMD GPUs as an Alternative to NVIDIA for Supporting Real-Time Workloads}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {10:1--10:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.10},
URN = {urn:nbn:de:0030-drops-123732},
doi = {10.4230/LIPIcs.ECRTS.2020.10},
annote = {Keywords: real-time systems, graphics processing units, parallel computing}
}
Document
Turning Futexes Inside-Out: Efficient and Deterministic User Space Synchronization Primitives for Real-Time Systems with IPCP
Abstract
In Linux and other operating systems, futexes (fast user space mutexes) are the underlying synchronization primitives to implement POSIX synchronization mechanisms, such as blocking mutexes, condition variables, and semaphores. Futexes allow one to implement mutexes with excellent performance by avoiding system calls in the fast path. However, futexes are fundamentally limited to synchronization mechanisms that are expressible as atomic operations on 32-bit variables. At operating system kernel level, futex implementations require complex mechanisms to look up internal wait queues making them susceptible to determinism issues. In this paper, we present an alternative design for futexes by completely moving the complexity of wait queue management from the operating system kernel into user space, i. e. we turn futexes "inside out". The enabling mechanisms for "inside-out futexes" are an efficient implementation of the immediate priority ceiling protocol (IPCP) to achieve non-preemptive critical sections in user space, spinlocks for mutual exclusion, and interwoven services to suspend or wake up threads. The design allows us to implement common thread synchronization mechanisms in user space and to move determinism concerns out of the kernel while keeping the performance properties of futexes. The presented approach is suitable for multi-processor real-time systems with partitioned fixed-priority (P-FP) scheduling on each processor. We evaluate the approach with an implementation for mutexes and condition variables in a real-time operating system (RTOS). Experimental results on 32-bit ARM platforms show that the approach is feasible, and overheads are driven by low-level synchronization primitives.
Cite as
Alexander Zuepke. Turning Futexes Inside-Out: Efficient and Deterministic User Space Synchronization Primitives for Real-Time Systems with IPCP. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{zuepke:LIPIcs.ECRTS.2020.11,
author = {Zuepke, Alexander},
title = {{Turning Futexes Inside-Out: Efficient and Deterministic User Space Synchronization Primitives for Real-Time Systems with IPCP}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {11:1--11:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.11},
URN = {urn:nbn:de:0030-drops-123746},
doi = {10.4230/LIPIcs.ECRTS.2020.11},
annote = {Keywords: Futex, Immediate Priority Ceiling Protocol, Critical Section, Monitor}
}
Document
Modeling and Analysis of Bus Contention for Hardware Accelerators in FPGA SoCs
Abstract
FPGA System-on-Chips (SoCs) are heterogeneous platforms that combine general-purpose processors with a field-programmable gate array (FPGA) fabric. The FPGA fabric is composed of a programmable logic in which hardware accelerators can be deployed to accelerate the execution of specific functionality. The main source of unpredictability when bounding the execution times of hardware accelerators pertains the access to the shared memories via the on-chip bus. This work is focused on bounding the worst-case bus contention experienced by the hardware accelerators deployed in the FPGA fabric. To this end, this work considers the AMBA AXI bus, which is the de-facto standard communication interface used in most the commercial off-the-shelf (COTS) FPGA SoCs, and presents an analysis technique to bound the response times of hardware accelerators implemented on such platforms. A fine-grained modeling of the AXI bus and AXI interconnects is first provided. Then, contention delays are studied under hierarchical bus infrastructures with arbitrary depths. Experimental results are finally presented to validate the proposed model with execution traces on two modern FPGA-based SoC produced by Xilinx (Zynq-7000 and Zynq-Ultrascale+ families) and to assess the performance of the proposed analysis.
Cite as
Francesco Restuccia, Marco Pagani, Alessandro Biondi, Mauro Marinoni, and Giorgio Buttazzo. Modeling and Analysis of Bus Contention for Hardware Accelerators in FPGA SoCs. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 12:1-12:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{restuccia_et_al:LIPIcs.ECRTS.2020.12,
author = {Restuccia, Francesco and Pagani, Marco and Biondi, Alessandro and Marinoni, Mauro and Buttazzo, Giorgio},
title = {{Modeling and Analysis of Bus Contention for Hardware Accelerators in FPGA SoCs}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {12:1--12:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.12},
URN = {urn:nbn:de:0030-drops-123753},
doi = {10.4230/LIPIcs.ECRTS.2020.12},
annote = {Keywords: Heterogeneous computing, Predictable hardware acceleration, FPGA SoCs, Multi-Master architectures}
}
Document
On How to Identify Cache Coherence: Case of the NXP QorIQ T4240
Abstract
Architectures used in safety critical systems have to pass certain certification standards, which require sufficient proof that they will behave as expected. Multi-core processors make this challenging by featuring complex interactions between the tasks they run. A lot of these interactions are made without explicit instructions from the program designers. Furthermore, they can have strong negative impacts on performance (and potentially affect correctness). One important such source of interactions is cache coherence, which speeds up operations in most cases, but can also lead to unexpected variations in execution time if not fully understood. Architecture documentations often lack details on the implementation of cache coherence. We thus propose a strategy to ascertain that the platform does indeed implement the cache coherence protocol its user believes it to. We also apply this strategy to the NXP QorIQ T4240, resulting in the identification of a protocol (MESIF) other than the one this architecture’s documentation led us to believe it was using (MESI).
Cite as
Nathanaël Sensfelder, Julien Brunel, and Claire Pagetti. On How to Identify Cache Coherence: Case of the NXP QorIQ T4240. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{sensfelder_et_al:LIPIcs.ECRTS.2020.13,
author = {Sensfelder, Nathana\"{e}l and Brunel, Julien and Pagetti, Claire},
title = {{On How to Identify Cache Coherence: Case of the NXP QorIQ T4240}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {13:1--13:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.13},
URN = {urn:nbn:de:0030-drops-123764},
doi = {10.4230/LIPIcs.ECRTS.2020.13},
annote = {Keywords: Real-time systems, multi-core processor, cache coherence}
}
Document
Simultaneous Multithreading and Hard Real Time: Can It Be Safe?
Abstract
The applicability of Simultaneous Multithreading (SMT) to real-time systems has been hampered by the difficulty of obtaining reliable execution costs in an SMT-enabled system. This problem is addressed by introducing a scheduling framework, called CERT-MT, that combines scheduling-aware timing analysis with a cyclic-executive scheduler in a way that minimizes SMT-related timing variations. The proposed scheduling-aware timing analysis is based on maximum observed execution times and accounts for the uncertainty inherent in measurement-based timing analysis. The timing analysis is found to work for tasks with and without SMT, though some adjustments are required in the former case. A large-scale schedulability study is presented that shows CERT-MT can schedule systems with total utilizations approaching 1.4 times the core count, without sacrificing safety.
Cite as
Sims Hill Osborne and James H. Anderson. Simultaneous Multithreading and Hard Real Time: Can It Be Safe?. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{osborne_et_al:LIPIcs.ECRTS.2020.14,
author = {Osborne, Sims Hill and Anderson, James H.},
title = {{Simultaneous Multithreading and Hard Real Time: Can It Be Safe?}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {14:1--14:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.14},
URN = {urn:nbn:de:0030-drops-123778},
doi = {10.4230/LIPIcs.ECRTS.2020.14},
annote = {Keywords: real-time systems, simultaneous multithreading, hard real-time, scheduling algorithms, probability, statistics, timing analysis}
}
Document
Tracing Hardware Monitors in the GR712RC Multicore Platform: Challenges and Lessons Learnt from a Space Case Study
Abstract
The demand for increased computing performance is driving industry in critical-embedded systems (CES) domains, e.g. space, towards the use of multicores processors. Multicores, however, pose several challenges that must be addressed before their safe adoption in critical embedded domains. One of the prominent challenges is software timing analysis, a fundamental step in the verification and validation process. Monitoring and profiling solutions, traditionally used for debugging and optimization, are increasingly exploited for software timing in multicores. In particular, hardware event monitors related to requests to shared hardware resources are building block to assess and restraining multicore interference. Modern timing analysis techniques build on event monitors to track and control the contention tasks can generate each other in a multicore platform. In this paper we look into the hardware profiling problem from an industrial perspective and address both methodological and practical problems when monitoring a multicore application. We assess pros and cons of several profiling and tracing solutions, showing that several aspects need to be taken into account while considering the appropriate mechanism to collect and extract the profiling information from a multicore COTS platform. We address the profiling problem on a representative COTS platform for the aerospace domain to find that the availability of directly-accessible hardware counters is not a given, and it may be necessary to the develop specific tools that capture the needs of both the user’s and the timing analysis technique requirements. We report challenges in developing an event monitor tracing tool that works for bare-metal and RTEMS configurations and show the accuracy of the developed tool-set in profiling a real aerospace application. We also show how the profiling tools can be exploited, together with handcrafted benchmarks, to characterize the application behavior in terms of multicore timing interference.
Cite as
Xavier Palomo, Mikel Fernandez, Sylvain Girbal, Enrico Mezzetti, Jaume Abella, Francisco J. Cazorla, and Laurent Rioux. Tracing Hardware Monitors in the GR712RC Multicore Platform: Challenges and Lessons Learnt from a Space Case Study. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 15:1-15:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{palomo_et_al:LIPIcs.ECRTS.2020.15,
author = {Palomo, Xavier and Fernandez, Mikel and Girbal, Sylvain and Mezzetti, Enrico and Abella, Jaume and Cazorla, Francisco J. and Rioux, Laurent},
title = {{Tracing Hardware Monitors in the GR712RC Multicore Platform: Challenges and Lessons Learnt from a Space Case Study}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {15:1--15:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.15},
URN = {urn:nbn:de:0030-drops-123787},
doi = {10.4230/LIPIcs.ECRTS.2020.15},
annote = {Keywords: Multicore Contention, Timing interference, Hardware Event Counters, PMC}
}
Document
Discriminative Coherence: Balancing Performance and Latency Bounds in Data-Sharing Multi-Core Real-Time Systems
Abstract
Tasks in modern multi-core real-time systems share data and communicate among each other. Nonetheless, the majority of published research in real-time systems either assumes that tasks do not share data or prohibits data sharing by design. Only recently, some works investigated solutions to address this limitation and enable data sharing; however, we find these works to suffer from severe limitations. In particular, approaches that bypass private caches to avoid coherence interference altogether suffer from significant average-case performance degradation. On the other hand, proposed predictable cache coherence protocols increase the worst-case memory latency (WCL) quadratically due to coherence interference. In this paper, by carefully analyzing the scenarios that lead to high coherence interference, we make the following observation. A protocol that distinguishes between non-modifying (read) and modifying (write) memory accesses is key towards reducing the effects of coherence interference on WCL. Accordingly, we propose DISCO, a discriminative coherence solution that capitalizes on this observation to balance average-case performance and WCL. This is achieved by disallowing modified data in private caches, and hence, the significant coherence delays resulting from them are avoided. In addition, DISCO achieves high average performance by allowing tasks to simultaneously read shared data in the private caches. Moreover, if the system supports the distinction between private and shared data, DISCO further improves average performance by allowing for the caching of private data in cores' private caches regardless of whether it is modified or not. Our evaluation shows that DISCO achieves 7.2× lower latency bounds compared to the state-of-the-art predictable coherence protocol. DISCO also achieves up to 11.4× (5.3× on average) better performance than private cache bypassing for the SPLASH-3 benchmarks.
Cite as
Mohamed Hassan. Discriminative Coherence: Balancing Performance and Latency Bounds in Data-Sharing Multi-Core Real-Time Systems. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{hassan:LIPIcs.ECRTS.2020.16,
author = {Hassan, Mohamed},
title = {{Discriminative Coherence: Balancing Performance and Latency Bounds in Data-Sharing Multi-Core Real-Time Systems}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {16:1--16:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.16},
URN = {urn:nbn:de:0030-drops-123795},
doi = {10.4230/LIPIcs.ECRTS.2020.16},
annote = {Keywords: Coherence, Shared Data, Caches, Multi-Core, Real-Time, Memory}
}
Document
Impact of AS6802 Synchronization Protocol on Time-Triggered and Rate-Constrained Traffic
Abstract
TTEthernet is an Ethernet-based synchronized network technology compliant with the AFDX standard. It supports safety-critical applications by defining different traffic classes: Time-Triggered (TT), Rate-Constrained (RC), and Best-Effort traffic. The synchronization is managed through the AS6802 protocol, which defines so-called Protocol Control Frames (PCFs) to synchronize the local clock of each device. In this paper, we analyze the synchronization protocol to assess the impact of the PCFs on TT and RC traffic. We propose a method to decrease the impact of PCFs on TT and a new Network Calculus model to compute RC delay bounds with the influence of both PCF and TT traffic. We finish with a performance evaluation to i) assess the impact of PCFs, ii) show the benefits of our method in terms of reducing the impact of PCFs on TT traffic and iii) prove the necessity of taking the PCF traffic into account to compute correct RC worst-case delays and provide a safe system.
Cite as
Anaïs Finzi and Luxi Zhao. Impact of AS6802 Synchronization Protocol on Time-Triggered and Rate-Constrained Traffic. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{finzi_et_al:LIPIcs.ECRTS.2020.17,
author = {Finzi, Ana\"{i}s and Zhao, Luxi},
title = {{Impact of AS6802 Synchronization Protocol on Time-Triggered and Rate-Constrained Traffic}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {17:1--17:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.17},
URN = {urn:nbn:de:0030-drops-123808},
doi = {10.4230/LIPIcs.ECRTS.2020.17},
annote = {Keywords: AS6802, TTE, Modeling, Performance analysis}
}
Document
Offloading Safety- and Mission-Critical Tasks via Unreliable Connections
Abstract
For many cyber-physical systems, e.g., IoT systems and autonomous vehicles, offloading workload to auxiliary processing units has become crucial. However, since this approach highly depends on network connectivity and responsiveness, typically only non-critical tasks are offloaded, which have less strict timing requirements than critical tasks. In this work, we provide two protocols allowing to offload critical and non-critical tasks likewise, while providing different service levels for non-critical tasks in the event of an unsuccessful offloading operation, depending on the respective system requirements. We analyze the worst-case timing behavior of the local cyber-physical system and, based on these analyses, we provide a sufficient schedulability test for each of the proposed protocols. In the course of comprehensive experiments, we show that our protocols have reasonable acceptance ratios under the provided schedulability tests. Moreover, we demonstrate that the system behavior under our proposed protocols is strongly dependent on probability of unsuccessful offloading operations, the percentage of critical tasks in the system, and the amount of offloaded workload.
Cite as
Lea Schönberger, Georg von der Brüggen, Kuan-Hsun Chen, Benjamin Sliwa, Hazem Youssef, Aswin Karthik Ramachandran Venkatapathy, Christian Wietfeld, Michael ten Hompel, and Jian-Jia Chen. Offloading Safety- and Mission-Critical Tasks via Unreliable Connections. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{schonberger_et_al:LIPIcs.ECRTS.2020.18,
author = {Sch\"{o}nberger, Lea and von der Br\"{u}ggen, Georg and Chen, Kuan-Hsun and Sliwa, Benjamin and Youssef, Hazem and Ramachandran Venkatapathy, Aswin Karthik and Wietfeld, Christian and ten Hompel, Michael and Chen, Jian-Jia},
title = {{Offloading Safety- and Mission-Critical Tasks via Unreliable Connections}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {18:1--18:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.18},
URN = {urn:nbn:de:0030-drops-123811},
doi = {10.4230/LIPIcs.ECRTS.2020.18},
annote = {Keywords: internet of things, cyber-physical systems, real-time, mixed-criticality, self-suspension, computation offloading, scheduling, communication}
}
Document
The Time-Triggered Wireless Architecture
Abstract
Wirelessly interconnected sensors, actuators, and controllers promise greater flexibility, lower installation and maintenance costs, and higher robustness in harsh conditions than wired solutions. However, to facilitate the adoption of wireless communication in cyber-physical systems (CPS), the functional and non-functional properties must be similar to those known from wired architectures. We thus present Time-Triggered Wireless (TTW), a wireless architecture for multi-mode CPS that offers reliable communication with guarantees on end-to-end delays among distributed applications executing on low-cost, low-power embedded devices. We achieve this by exploiting the high reliability and deterministic behavior of a synchronous transmission based communication stack we design, and by coupling the timings of distributed task executions and message exchanges across the wireless network by solving a novel co-scheduling problem. While some of the concepts in TTW have existed for some time and TTW has already been successfully applied for feedback control and coordination of multiple mechanical systems with closed-loop stability guarantees, this paper presents the key algorithmic, scheduling, and networking mechanisms behind TTW, along with their experimental evaluation, which have not been known so far. TTW is open source and ready to use: https://ttw.ethz.ch.
Cite as
Romain Jacob, Licong Zhang, Marco Zimmerling, Jan Beutel, Samarjit Chakraborty, and Lothar Thiele. The Time-Triggered Wireless Architecture. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 19:1-19:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{jacob_et_al:LIPIcs.ECRTS.2020.19,
author = {Jacob, Romain and Zhang, Licong and Zimmerling, Marco and Beutel, Jan and Chakraborty, Samarjit and Thiele, Lothar},
title = {{The Time-Triggered Wireless Architecture}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {19:1--19:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.19},
URN = {urn:nbn:de:0030-drops-123826},
doi = {10.4230/LIPIcs.ECRTS.2020.19},
annote = {Keywords: Time-triggered architecture, wireless bus, synchronous transmissions}
}
Document
Evaluation of the Age Latency of a Real-Time Communicating System Using the LET Paradigm
Abstract
Automotive and avionics embedded systems are usually composed of several tasks that are subject to complex timing constraints. In this context, the LET paradigm was introduced to improve the determinism of a system of tasks that communicate data through shared variables. The age latency corresponds to the maximum time for the propagation of data in these systems. Its precise evaluation is an important and challenging question for the design of these systems.
We consider in this paper a set of multi-periodic tasks that communicate data following the LET paradigm. Our main contribution is the development of mathematical and algorithmic tools to model precisely the dependency between tasks executions to experiment with an original methodology for computing the age latency of the system. These tools allow to handle the whole graph instead of particular chains and to extract automatically the critical parts of the graph. Experiments on randomly generated graphs indicate that systems with up to 90 periodic tasks and a hyperperiod bounded by 100 can be handled within a reasonable amount of time.
Cite as
Alix Munier Kordon and Ning Tang. Evaluation of the Age Latency of a Real-Time Communicating System Using the LET Paradigm. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kordon_et_al:LIPIcs.ECRTS.2020.20,
author = {Kordon, Alix Munier and Tang, Ning},
title = {{Evaluation of the Age Latency of a Real-Time Communicating System Using the LET Paradigm}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {20:1--20:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.20},
URN = {urn:nbn:de:0030-drops-123833},
doi = {10.4230/LIPIcs.ECRTS.2020.20},
annote = {Keywords: Real-Time Systems, Logical Execution Time, Age Latency}
}
Document
Control-System Stability Under Consecutive Deadline Misses Constraints
Abstract
This paper deals with the real-time implementation of feedback controllers. In particular, it provides an analysis of the stability property of closed-loop systems that include a controller that can sporadically miss deadlines. In this context, the weakly hard m-K computational model has been widely adopted and researchers used it to design and verify controllers that are robust to deadline misses. Rather than using the m-K model, we focus on another weakly-hard model, the number of consecutive deadline misses, showing a neat mathematical connection between real-time systems and control theory. We formalise this connection using the joint spectral radius and we discuss how to prove stability guarantees on the combination of a controller (that is unaware of deadline misses) and its system-level implementation. We apply the proposed verification procedure to a synthetic example and to an industrial case study.
Cite as
Martina Maggio, Arne Hamann, Eckart Mayer-John, and Dirk Ziegenbein. Control-System Stability Under Consecutive Deadline Misses Constraints. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{maggio_et_al:LIPIcs.ECRTS.2020.21,
author = {Maggio, Martina and Hamann, Arne and Mayer-John, Eckart and Ziegenbein, Dirk},
title = {{Control-System Stability Under Consecutive Deadline Misses Constraints}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {21:1--21:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.21},
URN = {urn:nbn:de:0030-drops-123845},
doi = {10.4230/LIPIcs.ECRTS.2020.21},
annote = {Keywords: Real-Time Control, Deadline Misses, Weakly Hard Models}
}
Document
Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle
Abstract
This paper introduces the first general and rigorous formalization of the classic busy-window principle for uniprocessors. The essence of the principle is identified as a minimal set of generic, high-level hypotheses that allow for a unified and general abstract response-time analysis, which is independent of specific scheduling policies, workload models, and preemption policy details. From this abstract core, the paper shows how to obtain concrete analysis instantiations for specific uniprocessor schedulers via a sequence of refinement steps, and provides formally verified response-time bounds for eight common schedulers and workloads, including the widely used fixed-priority (FP) and earliest-deadline first (EDF) scheduling policies in the context of fully, limited-, and non-preemptive sporadic tasks. All definitions and proofs in this paper have been mechanized and verified with the Coq proof assistant, and in fact form the common core and foundation for verified response-time analyses in the Prosa open-source framework for formally proven schedulability analyses.
Cite as
Sergey Bozhko and Björn B. Brandenburg. Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 22:1-22:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bozhko_et_al:LIPIcs.ECRTS.2020.22,
author = {Bozhko, Sergey and Brandenburg, Bj\"{o}rn B.},
title = {{Abstract Response-Time Analysis: A Formal Foundation for the Busy-Window Principle}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {22:1--22:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.22},
URN = {urn:nbn:de:0030-drops-123850},
doi = {10.4230/LIPIcs.ECRTS.2020.22},
annote = {Keywords: hard real-time systems, response-time analysis, uniprocessor, busy window, fixed priority, EDF, verification, Coq, Prosa, preemptive, non-preemptive, limited-preemptive}
}
Document
Analysis of Memory-Contention in Heterogeneous COTS MPSoCs
Abstract
Multiple-Processors Systems-on-Chip (MPSoCs) provide an appealing platform to execute Mixed Criticality Systems (MCS) with both time-sensitive critical tasks and performance-oriented non-critical tasks. Their heterogeneity with a variety of processing elements can address the conflicting requirements of those tasks. Nonetheless, the complex (and hence hard-to-analyze) architecture of Commercial-Off-The-Shelf (COTS) MPSoCs presents a challenge encumbering their adoption for MCS. In this paper, we propose a framework to analyze the memory contention in COTS MPSoCs and provide safe and tight bounds to the delays suffered by any critical task due to this contention. Unlike existing analyses, our solution is based on two main novel approaches. 1) It conducts a hybrid analysis that blends both request-level and task-level analyses into the same framework. 2) It leverages available knowledge about the types of memory requests of the task under analysis as well as contending tasks; specifically, we consider information that is already obtainable by applying existing static analysis tools to each task in isolation. Thanks to these novel techniques, our comparisons with the state-of-the art approaches show that the proposed analysis provides the tightest bounds across all evaluated access scenarios.
Cite as
Mohamed Hassan and Rodolfo Pellizzoni. Analysis of Memory-Contention in Heterogeneous COTS MPSoCs. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{hassan_et_al:LIPIcs.ECRTS.2020.23,
author = {Hassan, Mohamed and Pellizzoni, Rodolfo},
title = {{Analysis of Memory-Contention in Heterogeneous COTS MPSoCs}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {23:1--23:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.23},
URN = {urn:nbn:de:0030-drops-123861},
doi = {10.4230/LIPIcs.ECRTS.2020.23},
annote = {Keywords: DRAM, Memory, COTS, Multi-core, Real-Time, Embedded Systems, Analysis}
}
Document
smARTflight: An Environmentally-Aware Adaptive Real-Time Flight Management System
Abstract
Multi-rotor drones require real-time sensor data processing and control to maintain flight stability, which is made more challenging by external disturbances such as wind. In this paper we introduce smARTflight: an environmentally-aware adaptive real-time flight management system. smARTflight adapts the execution frequencies of flight control tasks according to timing and safety-critical constraints, in response to transient fluctuations of a drone’s attitude. In contrast to current state-of-the-art methods, smARTflight’s criticality-aware scheduler reduces the latency to return to a steady-state target attitude. The system also improves the overall control accuracy and lowers the frequency of adjustments to motor speeds to conserve power. A comparative case-study with a well-known autopilot shows that smARTflight reduces unnecessary control loop executions under stable conditions, while reducing response time latency by as much as 60% in a given axis of rotation when subjected to a 15° step attitude disturbance.
Cite as
Anam Farrukh and Richard West. smARTflight: An Environmentally-Aware Adaptive Real-Time Flight Management System. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 24:1-24:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{farrukh_et_al:LIPIcs.ECRTS.2020.24,
author = {Farrukh, Anam and West, Richard},
title = {{smARTflight: An Environmentally-Aware Adaptive Real-Time Flight Management System}},
booktitle = {32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
pages = {24:1--24:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-152-8},
ISSN = {1868-8969},
year = {2020},
volume = {165},
editor = {V\"{o}lp, Marcus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.24},
URN = {urn:nbn:de:0030-drops-123874},
doi = {10.4230/LIPIcs.ECRTS.2020.24},
annote = {Keywords: adaptive real-time systems, safety criticality, flight controller, multi-rotor drones, environmental awareness}
}