Volume
LIPIcs, Volume 106
30th Euromicro Conference on Real-Time Systems (ECRTS 2018)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Euromicro Conference on Real-Time Systems (ECRTS)
Event
ECRTS 2018, July 3-6, 2018, Barcelona, SpainEditor
Publication Details
- published at: 2018-06-22
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-075-0
- DBLP: db/conf/ecrts/ecrts2018
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 106, ECRTS'18, Complete Volume
Abstract
LIPIcs, Volume 106, ECRTS'18, Complete Volume
Cite as
30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@Proceedings{altmeyer:LIPIcs.ECRTS.2018,
title = {{LIPIcs, Volume 106, ECRTS'18, Complete Volume}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018},
URN = {urn:nbn:de:0030-drops-92441},
doi = {10.4230/LIPIcs.ECRTS.2018},
annote = {Keywords: Computer systems organization, Real-time systems, Computer systems organization, Embedded and cyber-physical systems, Software and its engineering}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{altmeyer:LIPIcs.ECRTS.2018.0,
author = {Altmeyer, Sebastian},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {0:i--0:xiv},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.0},
URN = {urn:nbn:de:0030-drops-89763},
doi = {10.4230/LIPIcs.ECRTS.2018.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Deterministic Memory Abstraction and Supporting Multicore System Architecture
Abstract
Poor time predictability of multicore processors has been a long-standing challenge in the real-time systems community. In this paper, we make a case that a fundamental problem that prevents efficient and predictable real-time computing on multicore is the lack of a proper memory abstraction to express memory criticality, which cuts across various layers of the system: the application, OS, and hardware. We, therefore, propose a new holistic resource management approach driven by a new memory abstraction, which we call Deterministic Memory. The key characteristic of deterministic memory is that the platform-the OS and hardware-guarantees small and tightly bounded worst-case memory access timing. In contrast, we call the conventional memory abstraction as best-effort memory in which only highly pessimistic worst-case bounds can be achieved. We propose to utilize both abstractions to achieve high time predictability but without significantly sacrificing performance. We present deterministic memory-aware OS and architecture designs, including OS-level page allocator, hardware-level cache, and DRAM controller designs. We implement the proposed OS and architecture extensions on Linux and gem5 simulator. Our evaluation results, using a set of synthetic and real-world benchmarks, demonstrate the feasibility and effectiveness of our approach.
Cite as
Farzad Farshchi, Prathap Kumar Valsan, Renato Mancuso, and Heechul Yun. Deterministic Memory Abstraction and Supporting Multicore System Architecture. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 1:1-1:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{farshchi_et_al:LIPIcs.ECRTS.2018.1,
author = {Farshchi, Farzad and Valsan, Prathap Kumar and Mancuso, Renato and Yun, Heechul},
title = {{Deterministic Memory Abstraction and Supporting Multicore System Architecture}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {1:1--1:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.1},
URN = {urn:nbn:de:0030-drops-90010},
doi = {10.4230/LIPIcs.ECRTS.2018.1},
annote = {Keywords: multicore processors, real-time, shared cache, DRAM controller, Linux}
}
Document
Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers
Abstract
In multicore architectures, there is potential for contention between cores when accessing shared resources, such as system memory. Such contention scenarios are challenging to accurately analyse, from a worst-case timing perspective. One way of making memory contention in multicores more amenable to timing analysis is the use of memory regulation mechanisms. It restricts the number of accesses performed by any given core over time by using periodically replenished per-core budgets. Typically, this assumes that all cores access memory via a single shared memory controller. However, ever-increasing bandwidth requirements have brought about architectures with multiple memory controllers. These control accesses to different memory regions and are potentially shared among all cores. While this presents an opportunity to satisfy bandwidth requirements, existing analysis designed for a single memory controller are no longer safe.
This work formulates a worst-case memory stall analysis for a memory-regulated multicore with two memory controllers. This stall analysis can be integrated into the schedulability analysis of systems under fixed-priority partitioned scheduling. Five heuristics for assigning tasks and memory budgets to cores in a stall-cognisant manner are also proposed. We experimentally quantify the cost in terms of extra stall for letting all cores benefit from the memory space offered by both controllers, and also evaluate the five heuristics for different system characteristics.
Cite as
Muhammad Ali Awan, Pedro F. Souto, Konstantinos Bletsas, Benny Akesson, and Eduardo Tovar. Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{awan_et_al:LIPIcs.ECRTS.2018.2,
author = {Awan, Muhammad Ali and Souto, Pedro F. and Bletsas, Konstantinos and Akesson, Benny and Tovar, Eduardo},
title = {{Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {2:1--2:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.2},
URN = {urn:nbn:de:0030-drops-90025},
doi = {10.4230/LIPIcs.ECRTS.2018.2},
annote = {Keywords: multiple memory controllers, memory regulation, multicore}
}
Document
HWP: Hardware Support to Reconcile Cache Energy, Complexity, Performance and WCET Estimates in Multicore Real-Time Systems
Abstract
High-performance processors have deployed multilevel cache (MLC) systems for decades. In the embedded real-time market, the use of MLC is also on the rise, with processors for future systems in space, railway, avionics and automotive already featuring two or more cache levels. One of the most critical elements for MLC is the write policy that not only affects several key metrics such as performance, WCET estimates, energy/power, and reliability, but also the design of complexity-prone cache coherence protocol and cache reliability solutions. In this paper we make an extensive analysis of existing write policies, namely write-through (WT) and write-back (WB). In the context of the real-time domain, we show that no write policy is superior for all metrics: WT simplifies the design of the coherence and reliability solutions at the cost of performance, WCET, and energy; while WB improves performance and energy results, but complicates cache design. To take the best of each policy, we propose Hybrid Write Policy (HWP) a low-complexity hardware mechanism that reconciles the benefits of WT in terms of simplifying the cache design (e.g. coherence solution) and the benefits of WB in improved average performance and WCET estimates as the pressure on the interconnection network increases. Guaranteed performance results show that HWP scales with core count similar to WB. Likewise, HWP reduces cache energy usage of WT, to levels similar to those of WB. These benefits are obtained while retaining the reduced coherence complexity of WT, in contrast to high coherence costs under WB.
Cite as
Pedro Benedicte, Carles Hernandez, Jaume Abella, and Francisco J. Cazorla. HWP: Hardware Support to Reconcile Cache Energy, Complexity, Performance and WCET Estimates in Multicore Real-Time Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{benedicte_et_al:LIPIcs.ECRTS.2018.3,
author = {Benedicte, Pedro and Hernandez, Carles and Abella, Jaume and Cazorla, Francisco J.},
title = {{HWP: Hardware Support to Reconcile Cache Energy, Complexity, Performance and WCET Estimates in Multicore Real-Time Systems}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {3:1--3:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.3},
URN = {urn:nbn:de:0030-drops-90005},
doi = {10.4230/LIPIcs.ECRTS.2018.3},
annote = {Keywords: multilevel caches, real-time systems, multicores, WCET}
}
Document
Compiler-based Extraction of Event Arrival Functions for Real-Time Systems Analysis
Abstract
Event arrival functions are commonly required in real-time systems analysis. Yet, event arrival functions are often either modeled based on specifications or generated by using potentially unsafe captured traces. To overcome this shortcoming, we present a compiler-based approach to safely extract event arrival functions. The extraction takes place at the code-level considering a complete coverage of all possible paths in the program and resulting in a cycle accurate event arrival curve. In order to reduce the runtime overhead of the proposed algorithm, we extend our approach with an adjustable level of granularity always providing a safe approximation of the tightest possible event arrival curve. In an evaluation, we demonstrate that the required extraction time can be heavily reduced while maintaining a high precision.
Cite as
Dominic Oehlert, Selma Saidi, and Heiko Falk. Compiler-based Extraction of Event Arrival Functions for Real-Time Systems Analysis. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{oehlert_et_al:LIPIcs.ECRTS.2018.4,
author = {Oehlert, Dominic and Saidi, Selma and Falk, Heiko},
title = {{Compiler-based Extraction of Event Arrival Functions for Real-Time Systems Analysis}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {4:1--4:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.4},
URN = {urn:nbn:de:0030-drops-89985},
doi = {10.4230/LIPIcs.ECRTS.2018.4},
annote = {Keywords: compiler, real-time, event arrival functions, extraction}
}
Document
A Measurement-Based Model for Parallel Real-Time Tasks
Abstract
Under the federated paradigm of multiprocessor scheduling, a set of processors is reserved for the exclusive use of each real-time task. If tasks are characterized very conservatively (as is typical in safety-critical systems), it is likely that most invocations of the task will have computational demand far below the worst-case characterization, and could have been scheduled correctly upon far fewer processors than were assigned to it assuming the worst-case characterization of its run-time behavior. Provided we could safely determine during run-time when all the processors are going to be needed, for the rest of the time the unneeded processors could be idled in low-energy "sleep" mode, or used for executing non-real time work in the background. In this paper we propose a model for representing parallelizable real-time tasks in a manner that permits us to do so. Our model does not require us to have fine-grained knowledge of the internal structure of the code represented by the task; rather, it characterizes each task by a few parameters that are obtained by repeatedly executing the code under different conditions and measuring the run-times.
Cite as
Kunal Agrawal and Sanjoy Baruah. A Measurement-Based Model for Parallel Real-Time Tasks. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2018.5,
author = {Agrawal, Kunal and Baruah, Sanjoy},
title = {{A Measurement-Based Model for Parallel Real-Time Tasks}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {5:1--5:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.5},
URN = {urn:nbn:de:0030-drops-89999},
doi = {10.4230/LIPIcs.ECRTS.2018.5},
annote = {Keywords: multiprocessor federated scheduling, parallel tasks, work and span, mixed criticality}
}
Document
Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems
Abstract
This paper explores the probability of deadline misses for a set of constrained-deadline sporadic soft real-time tasks on uniprocessor platforms. We explore two directions to evaluate the probability whether a job of the task under analysis can finish its execution at (or before) a testing time point t. One approach is based on analytical upper bounds that can be efficiently computed in polynomial time at the price of precision loss for each testing point, derived from the well-known Hoeffding's inequality and the well-known Bernstein's inequality. Another approach convolutes the probability efficiently over multinomial distributions, exploiting a series of state space reduction techniques, i.e., pruning without any loss of precision, and approximations via unifying equivalent classes with a bounded loss of precision. We demonstrate the effectiveness of our approaches in a series of evaluations. Distinct from the convolution-based methods in the literature, which suffer from the high computation demand and are applicable only to task sets with a few tasks, our approaches can scale reasonably without losing much precision in terms of the derived probability of deadline misses.
Cite as
Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik. Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{vonderbruggen_et_al:LIPIcs.ECRTS.2018.6,
author = {von der Br\"{u}ggen, Georg and Piatkowski, Nico and Chen, Kuan-Hsun and Chen, Jian-Jia and Morik, Katharina},
title = {{Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {6:1--6:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.6},
URN = {urn:nbn:de:0030-drops-89978},
doi = {10.4230/LIPIcs.ECRTS.2018.6},
annote = {Keywords: deadline miss probability, multinomial-based approach, analytical bound}
}
Document
Transferring Real-Time Systems Research into Industrial Practice: Four Impact Case Studies
Abstract
This paper describes four impact case studies where real-time systems research has been successfully transferred into industrial practice. In three cases, the technology created was translated into a viable commercial product via a start-up company. This technology transfer led to the creation and sustaining of a large number of high technology jobs over a 20 year period. The final case study involved the direct transfer of research results into an engineering company. Taken together, all four case studies have led to significant advances in automotive electronics and avionics, providing substantial returns on investment for the companies using the technology.
Cite as
Robert I. Davis, Iain Bate, Guillem Bernat, Ian Broster, Alan Burns, Antoine Colin, Stuart Hutchesson, and Nigel Tracey. Transferring Real-Time Systems Research into Industrial Practice: Four Impact Case Studies. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{davis_et_al:LIPIcs.ECRTS.2018.7,
author = {Davis, Robert I. and Bate, Iain and Bernat, Guillem and Broster, Ian and Burns, Alan and Colin, Antoine and Hutchesson, Stuart and Tracey, Nigel},
title = {{Transferring Real-Time Systems Research into Industrial Practice: Four Impact Case Studies}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {7:1--7:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.7},
URN = {urn:nbn:de:0030-drops-89955},
doi = {10.4230/LIPIcs.ECRTS.2018.7},
annote = {Keywords: real-time systems, industrial impact, automotive, avionics}
}
Document
Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems
Abstract
The sporadic task model is often used to analyze recurrent execution of tasks in real-time systems. A sporadic task defines an infinite sequence of task instances, also called jobs, that arrive under the minimum inter-arrival time constraint. To ensure the system safety, timeliness has to be guaranteed in addition to functional correctness, i.e., all jobs of all tasks have to be finished before the job deadlines. We focus on analyzing arbitrary-deadline task sets on a homogeneous (identical) multiprocessor system under any given global fixed-priority scheduling approach and provide a series of schedulability tests with different tradeoffs between their time complexity and their accuracy. Under the arbitrary-deadline setting, the relative deadline of a task can be longer than the minimum inter-arrival time of the jobs of the task. We show that global deadline-monotonic (DM) scheduling has a speedup bound of 3-1/M against any optimal scheduling algorithms, where M is the number of identical processors, and prove that this bound is asymptotically tight.
Cite as
Jian-Jia Chen, Georg von der Brüggen, and Niklas Ueter. Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 8:1-8:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:LIPIcs.ECRTS.2018.8,
author = {Chen, Jian-Jia and von der Br\"{u}ggen, Georg and Ueter, Niklas},
title = {{Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {8:1--8:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.8},
URN = {urn:nbn:de:0030-drops-89965},
doi = {10.4230/LIPIcs.ECRTS.2018.8},
annote = {Keywords: global fixed-priority scheduling, schedulability analyses, speedup bounds}
}
Document
A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling
Abstract
An effective way to increase the timing predictability of multicore platforms is to use non-preemptive scheduling. It reduces preemption and job migration overheads, avoids intra-core cache interference, and improves the accuracy of worst-case execution time (WCET) estimates. However, existing schedulability tests for global non-preemptive multiprocessor scheduling are pessimistic, especially when applied to periodic workloads. This paper reduces this pessimism by introducing a new type of sufficient schedulability analysis that is based on an exploration of the space of possible schedules using concise abstractions and state-pruning techniques. Specifically, we analyze the schedulability of non-preemptive job sets (with bounded release jitter and execution time variation) scheduled by a global job-level fixed-priority (JLFP) scheduling algorithm upon an identical multicore platform. The analysis yields a lower bound on the best-case response-time (BCRT) and an upper bound on the worst-case response time (WCRT) of the jobs. In an empirical evaluation with randomly generated workloads, we show that the method scales to 30 tasks, a hundred thousand jobs (per hyperperiod), and up to 9 cores.
Cite as
Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg. A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{nasri_et_al:LIPIcs.ECRTS.2018.9,
author = {Nasri, Mitra and Nelissen, Geoffrey and Brandenburg, Bj\"{o}rn B.},
title = {{A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {9:1--9:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.9},
URN = {urn:nbn:de:0030-drops-89941},
doi = {10.4230/LIPIcs.ECRTS.2018.9},
annote = {Keywords: global multiprocessor scheduling, schedulability analysis, non-preemptive tasks, worst-case response time, best-case response time}
}
Document
Beyond the Weakly Hard Model: Measuring the Performance Cost of Deadline Misses
Abstract
Most works in schedulability analysis theory are based on the assumption that constraints on the performance of the application can be expressed by a very limited set of timing constraints (often simply hard deadlines) on a task model. This model is insufficient to represent a large number of systems in which deadlines can be missed, or in which late task responses affect the performance, but not the correctness of the application. For systems with a possible temporary overload, models like the m-K deadline have been proposed in the past. However, the m-K model has several limitations since it does not consider the state of the system and is largely unaware of the way in which the performance is affected by deadline misses (except for critical failures). In this paper, we present a state-based representation of the evolution of a system with respect to each deadline hit or miss event. Our representation is much more general (while hopefully concise enough) to represent the evolution in time of the performance of time-sensitive systems with possible time overloads. We provide the theoretical foundations for our model and also show an application to a simple system to give examples of the state representations and their use.
Cite as
Paolo Pazzaglia, Luigi Pannocchi, Alessandro Biondi, and Marco Di Natale. Beyond the Weakly Hard Model: Measuring the Performance Cost of Deadline Misses. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{pazzaglia_et_al:LIPIcs.ECRTS.2018.10,
author = {Pazzaglia, Paolo and Pannocchi, Luigi and Biondi, Alessandro and Di Natale, Marco},
title = {{Beyond the Weakly Hard Model: Measuring the Performance Cost of Deadline Misses}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {10:1--10:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.10},
URN = {urn:nbn:de:0030-drops-89930},
doi = {10.4230/LIPIcs.ECRTS.2018.10},
annote = {Keywords: control, real-time, cyber physical systems, weakly hard, deadline miss, performance}
}
Document
Intractability Issues in Mixed-Criticality Scheduling
Abstract
In seeking to develop mixed-criticality scheduling algorithms, one encounters challenges arising from two sources. First, mixed-criticality scheduling is an inherently an on-line problem in that scheduling decisions must be made without access to all the information that is needed to make such decisions optimally - such information is only revealed over time. Second, many fundamental mixed-criticality schedulability analysis problems are computationally intractable - NP-hard in the strong sense - but we desire to solve these problems using algorithms with polynomial or pseudo-polynomial running time. While these two aspects of intractability are traditionally studied separately in the theoretical computer science literature, they have been considered in an integrated fashion in mixed-criticality scheduling theory. In this work we seek to separate out the effects of being inherently on-line, and being computationally intractable, on the overall intractability of mixed-criticality scheduling problems. Speedup factor is widely used as quantitative metric of the effectiveness of mixed-criticality scheduling algorithms; there has recently been a bit of a debate regarding the appropriateness of doing so. We provide here some additional perspective on this matter: we seek to better understand its appropriateness as well as its limitations in this regard by examining separately how the on-line nature of some mixed-criticality problems, and their computational complexity, contribute to the speedup factors of two widely-studied mixed-criticality scheduling algorithms.
Cite as
Kunal Agrawal and Sanjoy Baruah. Intractability Issues in Mixed-Criticality Scheduling. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2018.11,
author = {Agrawal, Kunal and Baruah, Sanjoy},
title = {{Intractability Issues in Mixed-Criticality Scheduling}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {11:1--11:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.11},
URN = {urn:nbn:de:0030-drops-89925},
doi = {10.4230/LIPIcs.ECRTS.2018.11},
annote = {Keywords: mixed-criticality scheduling, speedup factor, competitive ratio, approximation ratio, NP-completeness results, sporadic tasks}
}
Document
Improving the Schedulability and Quality of Service for Federated Scheduling of Parallel Mixed-Criticality Tasks on Multiprocessors
Abstract
This paper presents federated scheduling algorithm, called MCFQ, for a set of parallel mixed-criticality tasks on multiprocessors. The main feature of MCFQ algorithm is that different alternatives to assign each high-utilization, high-critical task to the processors are computed. Given the different alternatives, we carefully select one alternative for each such task so that all the other tasks can be successfully assigned on the remaining processors. Such flexibility in choosing the right alternative has two benefits. First, it has higher likelihood to satisfy the total resource requirement of all the tasks while ensuring schedulability. Second, computational slack becomes available by intelligently selecting the alternative such that the total resource requirement of all the tasks is minimized. Such slack then can be used to improve the QoS of the system (i.e., never discard some low-critical tasks). Our experimental results using randomly-generated parallel mixed-critical tasksets show that MCFQ can schedule much higher number of tasksets and can improve the QoS of the system significantly in comparison to the state of the art.
Cite as
Risat Mahmud Pathan. Improving the Schedulability and Quality of Service for Federated Scheduling of Parallel Mixed-Criticality Tasks on Multiprocessors. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{pathan:LIPIcs.ECRTS.2018.12,
author = {Pathan, Risat Mahmud},
title = {{Improving the Schedulability and Quality of Service for Federated Scheduling of Parallel Mixed-Criticality Tasks on Multiprocessors}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {12:1--12:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.12},
URN = {urn:nbn:de:0030-drops-89915},
doi = {10.4230/LIPIcs.ECRTS.2018.12},
annote = {Keywords: mixed-criticality systems, real-time systems, multiprocessor scheduling, federated scheduling}
}
Document
Virtual Timing Isolation for Mixed-Criticality Systems
Abstract
Commercial of the shelf multicore processors suffer from timing interferences between cores which complicates applying them in hard real-time systems like avionic applications. This paper proposes a virtual timing isolation of one main application running on one core from all other cores. The proposed technique is based on hardware external to the multicore processor and completely transparent to the main application i.e., no modifications of the software including the operating system are necessary. The basic idea is to apply a single-core execution based Worst Case Execution Time analysis and to accept a predefined slowdown during multicore execution. If the slowdown exceeds the acceptable bounds, interferences will be reduced by controlling the behavior of low-critical cores to keep the main application's progress inside the given bounds. Apart from the main goal of isolating the timing of the critical application a subgoal is also to efficiently use the other cores. For that purpose, three different mechanisms for controlling the non-critical cores are compared regarding efficient usage of the complete processor.
Measuring the progress of the main application is performed by tracking the application's Fingerprint. This technology quantifies online any slowdown of execution compared to a given baseline (single-core execution). Several countermeasures to compensate unacceptable slowdowns are proposed and evaluated in this paper, together with an accuracy evaluation of the Fingerprinting. Our evaluations using the TACLeBench benchmark suite show that we can meet a given acceptable timing bound of 4 percent slowdown with a resulting real slowdown of only 3.27 percent in case of a pulse width modulated control and of 4.44 percent in the case of a frequency scaling control.
Cite as
Johannes Freitag, Sascha Uhrig, and Theo Ungerer. Virtual Timing Isolation for Mixed-Criticality Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{freitag_et_al:LIPIcs.ECRTS.2018.13,
author = {Freitag, Johannes and Uhrig, Sascha and Ungerer, Theo},
title = {{Virtual Timing Isolation for Mixed-Criticality Systems}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {13:1--13:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.13},
URN = {urn:nbn:de:0030-drops-89904},
doi = {10.4230/LIPIcs.ECRTS.2018.13},
annote = {Keywords: multicore, hard real-time systems, timing isolation, safety-critical systems, mixed-criticality design and assurance}
}
Document
AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems
Abstract
A system is said to be resilient if slight deviations from expected behavior during run-time does not lead to catastrophic degradation of performance: minor deviations should result in no more than minor performance degradation. In mixed-criticality systems, such degradation should additionally be criticality-cognizant. The applicability of control theory is explored for the design of resilient run-time scheduling algorithms for mixed-criticality systems. Recent results in control theory have shown how appropriately designed controllers can provide guaranteed service to hard-real-time servers; this prior work is extended to allow for such guarantees to be made concurrently to multiple criticality-cognizant servers. The applicability of this approach is explored via several experimental simulations in a dual-criticality setting. These experiments demonstrate that our control-based run-time schedulers can be synthesized in such a manner that bounded deviations from expected behavior result in the high-criticality server suffering no performance degradation and the lower-criticality one, bounded performance degradation.
Cite as
Alessandro Vittorio Papadopoulos, Enrico Bini, Sanjoy Baruah, and Alan Burns. AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{papadopoulos_et_al:LIPIcs.ECRTS.2018.14,
author = {Papadopoulos, Alessandro Vittorio and Bini, Enrico and Baruah, Sanjoy and Burns, Alan},
title = {{AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {14:1--14:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.14},
URN = {urn:nbn:de:0030-drops-89899},
doi = {10.4230/LIPIcs.ECRTS.2018.14},
annote = {Keywords: mixed criticality, control theory, run-time resilience, bounded overloads}
}
Document
Verifying Weakly-Hard Real-Time Properties of Traffic Streams in Switched Networks
Abstract
In this paper, we introduce the first verification method which is able to provide weakly-hard real-time guarantees for tasks and task chains in systems with multiple resources under partitioned scheduling with fixed priorities. Existing weakly-hard real-time verification techniques are restricted today to systems with a single resource. A weakly-hard real-time guarantee specifies an upper bound on the maximum number m of deadline misses of a task in a sequence of k consecutive executions. Such a guarantee is useful if a task can experience a bounded number of deadline misses without impacting the system mission. We present our verification method in the context of switched networks with traffic streams between nodes, and demonstrate its practical applicability in an automotive case study.
Cite as
Leonie Ahrendts, Sophie Quinton, Thomas Boroske, and Rolf Ernst. Verifying Weakly-Hard Real-Time Properties of Traffic Streams in Switched Networks. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{ahrendts_et_al:LIPIcs.ECRTS.2018.15,
author = {Ahrendts, Leonie and Quinton, Sophie and Boroske, Thomas and Ernst, Rolf},
title = {{Verifying Weakly-Hard Real-Time Properties of Traffic Streams in Switched Networks}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {15:1--15:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.15},
URN = {urn:nbn:de:0030-drops-89879},
doi = {10.4230/LIPIcs.ECRTS.2018.15},
annote = {Keywords: embedded and cyber-physical systems, weakly-hard real-time systems and networks, timing analysis}
}
Document
Quantifying the Resiliency of Fail-Operational Real-Time Networked Control Systems
Abstract
In time-sensitive, safety-critical systems that must be fail-operational, active replication is commonly used to mitigate transient faults that arise due to electromagnetic interference (EMI). However, designing an effective and well-performing active replication scheme is challenging since replication conflicts with the size, weight, power, and cost constraints of embedded applications. To enable a systematic and rigorous exploration of the resulting tradeoffs, we present an analysis to quantify the resiliency of fail-operational networked control systems against EMI-induced memory corruption, host crashes, and retransmission delays. Since control systems are typically robust to a few failed iterations, e.g., one missed actuation does not crash an inverted pendulum, traditional solutions based on hard real-time assumptions are often too pessimistic. Our analysis reduces this pessimism by modeling a control system's inherent robustness as an (m,k)-firm specification. A case study with an active suspension workload indicates that the analytical bounds closely predict the failure rate estimates obtained through simulation, thereby enabling a meaningful design-space exploration, and also demonstrates the utility of the analysis in identifying non-trivial and non-obvious reliability tradeoffs.
Cite as
Arpan Gujarati, Mitra Nasri, and Björn B. Brandenburg. Quantifying the Resiliency of Fail-Operational Real-Time Networked Control Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{gujarati_et_al:LIPIcs.ECRTS.2018.16,
author = {Gujarati, Arpan and Nasri, Mitra and Brandenburg, Bj\"{o}rn B.},
title = {{Quantifying the Resiliency of Fail-Operational Real-Time Networked Control Systems}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {16:1--16:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.16},
URN = {urn:nbn:de:0030-drops-89884},
doi = {10.4230/LIPIcs.ECRTS.2018.16},
annote = {Keywords: probabilistic analysis, reliability analysis, networked control systems}
}
Document
Camera Networks Dimensioning and Scheduling with Quasi Worst-Case Transmission Time
Abstract
This paper describes a method to compute frame size estimates to be used in quasi Worst-Case Transmission Times (qWCTT) for cameras that transmit frames over IP-based communication networks. The precise determination of qWCTT allows us to model the network access scheduling problem as a multiframe problem and to re-use theoretical results for network scheduling. The paper presents a set of experiments, conducted in an industrial testbed, that validate the qWCTT estimation. We believe that a more precise estimation will lead to savings for network infrastructure and to better network utilization.
Cite as
Viktor Edpalm, Alexandre Martins, Karl-Erik Årzén, and Martina Maggio. Camera Networks Dimensioning and Scheduling with Quasi Worst-Case Transmission Time. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{edpalm_et_al:LIPIcs.ECRTS.2018.17,
author = {Edpalm, Viktor and Martins, Alexandre and \r{A}rz\'{e}n, Karl-Erik and Maggio, Martina},
title = {{Camera Networks Dimensioning and Scheduling with Quasi Worst-Case Transmission Time}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {17:1--17:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.17},
URN = {urn:nbn:de:0030-drops-89869},
doi = {10.4230/LIPIcs.ECRTS.2018.17},
annote = {Keywords: worst-case transmission time, H.264, bandwidth estimation, video compression, network access scheduling, multiframe model, camera network}
}
Document
Early Design Phase Cross-Platform Throughput Prediction for Industrial Stream-Processing Applications
Abstract
Industrial embedded platforms are often used to execute stream-processing applications, from which the results are used by actuators. On average, these stream-processing applications should at least meet the required throughput of their actuators, which poses a real-time requirement on the system. To avoid extra costs and delays, it is desired to estimate during the early design phase if a combination of an embedded platform and a stream-processing application can achieve the required throughput. The throughput of a stream-processing application executed on different embedded platforms can be predicted by modeling them using static or measurement based analysis. However, during the early design phase it can be desirable to have a model that allows a large set of embedded platforms to be considered, where embedded platforms with predictive instructions are supported.
This paper presents a gray-box approach applicable during the early design phase to perform cross-platform throughput predictions for industrial stream-processing applications and their embedded platforms. A three step regression-based approach is presented, which uses an expression based on Amdahl's law for the discrete scaling of workload over cores and a large database with CPU performance scores to perform cross-platform throughput predictions. Validation, with a limited set of platforms, showed the usability of the approach. The pragmatic approach is based on a prototype industrial digital image processing application for a printer from Océ, which is also used to present the approach.
Cite as
Tjerk Bijlsma, Alexander Lint, and Jacques Verriet. Early Design Phase Cross-Platform Throughput Prediction for Industrial Stream-Processing Applications. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bijlsma_et_al:LIPIcs.ECRTS.2018.18,
author = {Bijlsma, Tjerk and Lint, Alexander and Verriet, Jacques},
title = {{Early Design Phase Cross-Platform Throughput Prediction for Industrial Stream-Processing Applications}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {18:1--18:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.18},
URN = {urn:nbn:de:0030-drops-89853},
doi = {10.4230/LIPIcs.ECRTS.2018.18},
annote = {Keywords: throughput prediction, stream-processing application, early design phase, regression model, cross-platform}
}
Document
Protecting Real-Time GPU Kernels on Integrated CPU-GPU SoC Platforms
Abstract
Integrated CPU-GPU architecture provides excellent acceleration capabilities for data parallel applications on embedded platforms while meeting the size, weight and power (SWaP) requirements. However, sharing of main memory between CPU applications and GPU kernels can severely affect the execution of GPU kernels and diminish the performance gain provided by GPU. For example, in the NVIDIA Jetson TX2 platform, an integrated CPU-GPU architecture, we observed that, in the worst case, the GPU kernels can suffer as much as 3X slowdown in the presence of co-running memory intensive CPU applications. In this paper, we propose a software mechanism, which we call BWLOCK++, to protect the performance of GPU kernels from co-scheduled memory intensive CPU applications.
Cite as
Waqar Ali and Heechul Yun. Protecting Real-Time GPU Kernels on Integrated CPU-GPU SoC Platforms. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{ali_et_al:LIPIcs.ECRTS.2018.19,
author = {Ali, Waqar and Yun, Heechul},
title = {{Protecting Real-Time GPU Kernels on Integrated CPU-GPU SoC Platforms}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {19:1--19:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.19},
URN = {urn:nbn:de:0030-drops-89833},
doi = {10.4230/LIPIcs.ECRTS.2018.19},
annote = {Keywords: GPU, memory bandwidth, resource contention, CPU throttling, fair scheduler}
}
Document
Avoiding Pitfalls when Using NVIDIA GPUs for Real-Time Tasks in Autonomous Systems
Abstract
NVIDIA's CUDA API has enabled GPUs to be used as computing accelerators across a wide range of applications. This has resulted in performance gains in many application domains, but the underlying GPU hardware and software are subject to many non-obvious pitfalls. This is particularly problematic for safety-critical systems, where worst-case behaviors must be taken into account. While such behaviors were not a key concern for earlier CUDA users, the usage of GPUs in autonomous vehicles has taken CUDA programs out of the sole domain of computer-vision and machine-learning experts and into safety-critical processing pipelines. Certification is necessary in this new domain, which is problematic because GPU software may have been developed without any regard for worst-case behaviors. Pitfalls when using CUDA in real-time autonomous systems can result from the lack of specifics in official documentation, and developers of GPU software not being aware of the implications of their design choices with regards to real-time requirements. This paper focuses on the particular challenges facing the real-time community when utilizing CUDA-enabled GPUs for autonomous applications, and best practices for applying real-time safety-critical principles.
Cite as
Ming Yang, Nathan Otterness, Tanya Amert, Joshua Bakita, James H. Anderson, and F. Donelson Smith. Avoiding Pitfalls when Using NVIDIA GPUs for Real-Time Tasks in Autonomous Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{yang_et_al:LIPIcs.ECRTS.2018.20,
author = {Yang, Ming and Otterness, Nathan and Amert, Tanya and Bakita, Joshua and Anderson, James H. and Smith, F. Donelson},
title = {{Avoiding Pitfalls when Using NVIDIA GPUs for Real-Time Tasks in Autonomous Systems}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {20:1--20:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.20},
URN = {urn:nbn:de:0030-drops-89845},
doi = {10.4230/LIPIcs.ECRTS.2018.20},
annote = {Keywords: real-time systems, graphics processing units, scheduling algorithms, parallel computing, embedded software}
}
Document
Instruction Caches in Static WCET Analysis of Artificially Diversified Software
Abstract
Artificial Software Diversity is a well-established method to increase security of computer systems by thwarting code-reuse attacks, which is particularly beneficial in safety-critical real-time systems. However, static worst-case execution time (WCET) analysis on complex hardware involving caches only delivers sound results for single versions of the program, as it relies on absolute addresses for all instructions. To overcome this problem, we present an abstract interpretation based instruction cache analysis that provides a safe yet precise upper bound for the execution of all variants of a program. We achieve this by integrating uncertainties in the absolute and relative positioning of code fragments when updating the abstract cache state during the analysis. We demonstrate the effectiveness of our approach in an in-depth evaluation and provide an overview of the impact of different diversity techniques on the WCET estimations.
Cite as
Joachim Fellmuth, Thomas Göthel, and Sabine Glesner. Instruction Caches in Static WCET Analysis of Artificially Diversified Software. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{fellmuth_et_al:LIPIcs.ECRTS.2018.21,
author = {Fellmuth, Joachim and G\"{o}thel, Thomas and Glesner, Sabine},
title = {{Instruction Caches in Static WCET Analysis of Artificially Diversified Software}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {21:1--21:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.21},
URN = {urn:nbn:de:0030-drops-89822},
doi = {10.4230/LIPIcs.ECRTS.2018.21},
annote = {Keywords: WCET, static analysis, abstract interpretation, artificial diversity, cache analysis}
}
Document
Vulnerability Analysis and Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Systems
Abstract
Much effort has been put into improving the predictability of real-time systems, especially in safety-critical environments, which provides designers with a rich set of methods and tools to attest safety in situations with no or a limited number of accidental faults. However, with increasing connectivity of real-time systems and a wide availability of increasingly sophisticated exploits, security and, in particular, the consequences of predictability on security become concerns of equal importance. Time-triggered scheduling with offline constructed tables provides determinism and simplifies timing inference, however, at the same time, time-triggered scheduling creates vulnerabilities by allowing attackers to target their attacks to specific, deterministically scheduled and possibly safety-critical tasks. In this paper, we analyze the severity of these vulnerabilities by assuming successful compromise of a subset of the tasks running in a real-time system and by investigating the attack potential that attackers gain from them. Moreover, we discuss two ways to mitigate direct attacks: slot-level online randomization of schedules, and offline schedule-diversification. We evaluate these mitigation strategies with a real-world case study to show their practicability for mitigating not only accidentally malicious behavior, but also malicious behavior triggered by attackers on purpose.
Cite as
Kristin Krüger, Marcus Völp, and Gerhard Fohler. Vulnerability Analysis and Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{kruger_et_al:LIPIcs.ECRTS.2018.22,
author = {Kr\"{u}ger, Kristin and V\"{o}lp, Marcus and Fohler, Gerhard},
title = {{Vulnerability Analysis and Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Systems}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {22:1--22:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.22},
URN = {urn:nbn:de:0030-drops-89811},
doi = {10.4230/LIPIcs.ECRTS.2018.22},
annote = {Keywords: real-time systems, time-triggered systems, security, vulnerability}
}
Document
Recovery Time Considerations in Real-Time Systems Employing Software Fault Tolerance
Abstract
Safety-critical real-time systems like modern automobiles with advanced driving-assist features must employ redundancy for crucial software tasks to tolerate permanent crash faults. This redundancy can be achieved by using techniques like active replication or the primary-backup approach. In such systems, the recovery time which is the amount of time it takes for a redundant task to take over execution on the failure of a primary task becomes a very important design parameter. The recovery time for a given task depends on various factors like task allocation, primary and redundant task priorities, system load and the scheduling policy. Each task can also have a different recovery time requirement (RTR). For example, in automobiles with automated driving features, safety-critical tasks like perception and steering control have strict RTRs, whereas such requirements are more relaxed in the case of tasks like heating control and mission planning. In this paper, we analyze the recovery time for software tasks in a real-time system employing Rate-Monotonic Scheduling (RMS). We derive bounds on the recovery times for different redundant task options and propose techniques to determine the redundant-task type for a task to satisfy its RTR. We also address the fault-tolerant task allocation problem, with the additional constraint of satisfying the RTR of each task in the system. Given that the problem of assigning tasks to processors is a well-known NP-hard bin-packing problem we propose computationally-efficient heuristics to find a feasible allocation of tasks and their redundant copies. We also apply the simulated annealing method to the fault-tolerant task allocation problem with RTR constraints and compare against our heuristics.
Cite as
Anand Bhat, Soheil Samii, and Ragunathan (Raj) Rajkumar. Recovery Time Considerations in Real-Time Systems Employing Software Fault Tolerance. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bhat_et_al:LIPIcs.ECRTS.2018.23,
author = {Bhat, Anand and Samii, Soheil and Rajkumar, Ragunathan (Raj)},
title = {{Recovery Time Considerations in Real-Time Systems Employing Software Fault Tolerance}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {23:1--23:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.23},
URN = {urn:nbn:de:0030-drops-89808},
doi = {10.4230/LIPIcs.ECRTS.2018.23},
annote = {Keywords: fault tolerance, real-time embedded systems, recovery time, real-time schedulability}
}
Document
Whole-System Worst-Case Energy-Consumption Analysis for Energy-Constrained Real-Time Systems
Abstract
Although internal devices (e.g., memory, timers) and external devices (e.g., transceivers, sensors) significantly contribute to the energy consumption of an embedded real-time system, their impact on the worst-case response energy consumption (WCRE) of tasks is usually not adequately taken into account. Most WCRE analysis techniques, for example, only focus on the processor and therefore do not consider the energy consumption of other hardware units. Apart from that, the typical approach for dealing with devices is to assume that all of them are always activated, which leads to high WCRE overestimations in the general case where a system switches off the devices that are currently not needed in order to minimize energy consumption.
In this paper, we present SysWCEC, an approach that addresses these problems by enabling static WCRE analysis for entire real-time systems, including internal as well as external devices. For this purpose, SysWCEC introduces a novel abstraction, the power-state-transition graph, which contains information about the worst-case energy consumption of all possible execution paths. To construct the graph, SysWCEC decomposes the analyzed real-time system into blocks during which the set of active devices in the system does not change and is consequently able to precisely handle devices being dynamically activated or deactivated.
Cite as
Peter Wägemann, Christian Dietrich, Tobias Distler, Peter Ulbrich, and Wolfgang Schröder-Preikschat. Whole-System Worst-Case Energy-Consumption Analysis for Energy-Constrained Real-Time Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 24:1-24:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{wagemann_et_al:LIPIcs.ECRTS.2018.24,
author = {W\"{a}gemann, Peter and Dietrich, Christian and Distler, Tobias and Ulbrich, Peter and Schr\"{o}der-Preikschat, Wolfgang},
title = {{Whole-System Worst-Case Energy-Consumption Analysis for Energy-Constrained Real-Time Systems}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {24:1--24:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.24},
URN = {urn:nbn:de:0030-drops-89795},
doi = {10.4230/LIPIcs.ECRTS.2018.24},
annote = {Keywords: energy-constrained real-time systems, worst-case energy consumption (WCEC), worst-case response energy consumption (WCRE), static whole-system analysis}
}
Document
Using Lock Servers to Scale Real-Time Locking Protocols: Chasing Ever-Increasing Core Counts
Abstract
During the past decade, parallelism-related issues have been at the forefront of real-time systems research due to the advent of multicore technologies. In the coming years, such issues will loom ever larger due to increasing core counts. Having more cores means a greater potential exists for platform capacity loss when the available parallelism cannot be fully exploited. In this paper, such capacity loss is considered in the context of real-time locking protocols. In this context, lock nesting becomes a key concern as it can result in transitive blocking chains that force tasks to execute sequentially unnecessarily. Such chains can be quite long on a larger machine. Contention-sensitive real-time locking protocols have been proposed as a means of "breaking" transitive blocking chains, but such protocols tend to have high overhead due to more complicated lock/unlock logic. To ease such overhead, the usage of lock servers is considered herein. In particular, four specific lock-server paradigms are proposed and many nuances concerning their deployment are explored. Experiments are presented that show that, by executing cache hot, lock servers can enable reductions in lock/unlock overhead of up to 86%. Such reductions make contention-sensitive protocols a viable approach in practice.
Cite as
Catherine E. Nemitz, Tanya Amert, and James H. Anderson. Using Lock Servers to Scale Real-Time Locking Protocols: Chasing Ever-Increasing Core Counts. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{nemitz_et_al:LIPIcs.ECRTS.2018.25,
author = {Nemitz, Catherine E. and Amert, Tanya and Anderson, James H.},
title = {{Using Lock Servers to Scale Real-Time Locking Protocols: Chasing Ever-Increasing Core Counts}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {25:1--25:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.25},
URN = {urn:nbn:de:0030-drops-89789},
doi = {10.4230/LIPIcs.ECRTS.2018.25},
annote = {Keywords: multiprocess locking protocols, nested locks, priority-inversion blocking, reader/writer locks, real-time locking protocols}
}
Document
On Strong and Weak Sustainability, with an Application to Self-Suspending Real-Time Tasks
Abstract
Motivated by an apparent contradiction regarding whether certain scheduling policies are sustainable, we revisit the topic of sustainability in real-time scheduling and argue that the existing definitions of sustainability should be further clarified and generalized. After proposing a formal, generic sustainability theory, we relax the existing notion of (strongly) sustainable scheduling policy to provide a new classification called weak sustainability. Proving weak sustainability properties allows reducing the number of variables that must be considered in the search of a worst-case schedule, and hence enables more efficient schedulability analyses and testing regimes even for policies that are not (strongly) sustainable. As a proof of concept, and to better understand a model for which many mistakes were found in the literature, we study weak sustainability in the context of dynamic self-suspending tasks, where we formalize a generic suspension model using the Coq proof assistant and provide a machine-checked proof that any JLFP scheduling policy is weakly sustainable with respect to job costs and variable suspension times.
Cite as
Felipe Cerqueira, Geoffrey Nelissen, and Björn B. Brandenburg. On Strong and Weak Sustainability, with an Application to Self-Suspending Real-Time Tasks. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 26:1-26:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{cerqueira_et_al:LIPIcs.ECRTS.2018.26,
author = {Cerqueira, Felipe and Nelissen, Geoffrey and Brandenburg, Bj\"{o}rn B.},
title = {{On Strong and Weak Sustainability, with an Application to Self-Suspending Real-Time Tasks}},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
pages = {26:1--26:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-075-0},
ISSN = {1868-8969},
year = {2018},
volume = {106},
editor = {Altmeyer, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.26},
URN = {urn:nbn:de:0030-drops-89773},
doi = {10.4230/LIPIcs.ECRTS.2018.26},
annote = {Keywords: real-time scheduling, sustainability, self-suspending tasks, machine-checked proofs}
}