Volume
OASIcs, Volume 63
18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)
-
Part of:
Series:
Open Access Series in Informatics (OASIcs)
Conference: Workshop on Worst-Case Execution Time Analysis (WCET)
Event
WCET 2018, July 3, 2018, Barcelona, SpainEditor
Publication Details
- published at: 2018-09-24
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-073-6
- DBLP: db/conf/wcet/wcet2018
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
OASIcs, Volume 63, WCET'18, Complete Volume
Abstract
OASIcs, Volume 63, WCET'18, Complete Volume
Cite as
18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@Proceedings{brandner:OASIcs.WCET.2018,
title = {{OASIcs, Volume 63, WCET'18, Complete Volume}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018},
URN = {urn:nbn:de:0030-drops-97578},
doi = {10.4230/OASIcs.WCET.2018},
annote = {Keywords: Computer systems organization, Real-time systems, Theory of computation, Program analysis, Software and its engineering, Software performance}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{brandner:OASIcs.WCET.2018.0,
author = {Brandner, Florian},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {0:i--0:x},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.0},
URN = {urn:nbn:de:0030-drops-97460},
doi = {10.4230/OASIcs.WCET.2018.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Paper
Mixed Feelings About Mixed Criticality (Invited Paper)
Abstract
I point to some challenges for WCET analysis offered in the transition to integrated mixed-criticality systems (MCSs) and to multi-core platforms, claim that proposed certification standards are inadequate, show that the MCS model heavily used by the scheduling community is fraught, and clarify why the traditional abstract interface between WCET analysis and schedulability analysis is obsolete.
A central point is the insistence on sound approaches. I give a detailed account of how the most rigid certification procedures, those of the avionics domain, are satisfied, to defend the validity of my claims.
Cite as
Reinhard Wilhelm. Mixed Feelings About Mixed Criticality (Invited Paper). In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 1:1-1:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{wilhelm:OASIcs.WCET.2018.1,
author = {Wilhelm, Reinhard},
title = {{Mixed Feelings About Mixed Criticality}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {1:1--1:9},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.1},
URN = {urn:nbn:de:0030-drops-97473},
doi = {10.4230/OASIcs.WCET.2018.1},
annote = {Keywords: WCET analysis, mixed criticality systems, multi-core platforms, scheduling, schedulability}
}
Document
Formal Executable Models for Automatic Detection of Timing Anomalies
Abstract
A timing anomaly is a counterintuitive timing behavior in the sense that a local fast execution slows down an overall global execution. The presence of such behaviors is inconvenient for the WCET analysis which requires, via abstractions, a certain monotony property to compute safe bounds. In this paper we explore how to systematically execute a previously proposed formal definition of timing anomalies. We ground our work on formal designs of architecture models upon which we employ guided model checking techniques. Our goal is towards the automatic detection of timing anomalies in given computer architecture designs.
Cite as
Mihail Asavoae, Belgacem Ben Hedia, and Mathieu Jan. Formal Executable Models for Automatic Detection of Timing Anomalies. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{asavoae_et_al:OASIcs.WCET.2018.2,
author = {Asavoae, Mihail and Ben Hedia, Belgacem and Jan, Mathieu},
title = {{Formal Executable Models for Automatic Detection of Timing Anomalies}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {2:1--2:13},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.2},
URN = {urn:nbn:de:0030-drops-97481},
doi = {10.4230/OASIcs.WCET.2018.2},
annote = {Keywords: timing anomalies, predictability, formal methods, model checking}
}
Document
Reducing Timing Interferences in Real-Time Applications Running on Multicore Architectures
Abstract
We introduce a unified wcet analysis and scheduling framework for real-time applications deployed on multicore architectures. Our method does not follow a particular programming model, meaning that any piece of existing code (in particular legacy) can be re-used, and aims at reducing automatically the worst-case number of timing interferences between tasks. Our method is based on the notion of Time Interest Points (tips), which are instructions that can generate and/or suffer from timing interferences. We show how such points can be extracted from the binary code of applications and selected prior to performing the wcet analysis. We then represent real-time tasks as sequences of time intervals separated by tips, and schedule those tasks so that the overall makespan (including the potential timing penalties incurred by interferences) is minimized. This scheduling phase is performed using an Integer Linear Programming (ilp) solver. Preliminary results on state-of-the-art benchmarks show promising results and pave the way for future extensions of the model and optimizations.
Cite as
Thomas Carle and Hugues Cassé. Reducing Timing Interferences in Real-Time Applications Running on Multicore Architectures. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{carle_et_al:OASIcs.WCET.2018.3,
author = {Carle, Thomas and Cass\'{e}, Hugues},
title = {{Reducing Timing Interferences in Real-Time Applications Running on Multicore Architectures}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {3:1--3:12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.3},
URN = {urn:nbn:de:0030-drops-97493},
doi = {10.4230/OASIcs.WCET.2018.3},
annote = {Keywords: Multicore architecture, WCET, Time Interest Points}
}
Document
Toward Contention Analysis for Parallel Executing Real-Time Tasks
Abstract
In measurement-based probabilistic timing analysis, the execution conditions imposed to tasks as measurement scenarios, have a strong impact to the worst-case execution time estimates. The scenarios and their effects on the task execution behavior have to be deeply investigated. The aim has to be to identify and to guarantee the scenarios that lead to the maximum measurements, i.e. the worst-case scenarios, and use them to assure the worst-case execution time estimates.
We propose a contention analysis in order to identify the worst contentions that a task can suffer from concurrent executions. The work focuses on the interferences on shared resources (cache memories and memory buses) from parallel executions in multi-core real-time systems. Our approach consists of searching for possible task contenders for parallel executions, modeling their contentiousness, and classifying the measurement scenarios accordingly. We identify the most contentious ones and their worst-case effects on task execution times. The measurement-based probabilistic timing analysis is then used to verify the analysis proposed, qualify the scenarios with contentiousness, and compare them. A parallel execution simulator for multi-core real-time system is developed and used for validating our framework.
The framework applies heuristics and assumptions that simplify the system behavior. It represents a first step for developing a complete approach which would be able to guarantee the worst-case behavior.
Cite as
Fabrice Guet, Luca Santinelli, Jérôme Morio, Guillaume Phavorin, and Eric Jenn. Toward Contention Analysis for Parallel Executing Real-Time Tasks. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{guet_et_al:OASIcs.WCET.2018.4,
author = {Guet, Fabrice and Santinelli, Luca and Morio, J\'{e}r\^{o}me and Phavorin, Guillaume and Jenn, Eric},
title = {{Toward Contention Analysis for Parallel Executing Real-Time Tasks}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {4:1--4:13},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.4},
URN = {urn:nbn:de:0030-drops-97506},
doi = {10.4230/OASIcs.WCET.2018.4},
annote = {Keywords: Contention analysis, parallel executions, measurement-based probabilistic timing analysis, probabilistic worst-case execution time}
}
Document
A New Hybrid Approach on WCET Analysis for Real-Time Systems Using Machine Learning
Abstract
The notion of the Worst-Case Execution Time (WCET) allows system engineers to create safe real-time systems. This value is used to schedule all software tasks before their deadlines. Failing these deadlines will cause catastrophic events, e.g. vehicle crashes, failing to detect dangerous anomalies, etc. Different analysis methodologies exist to determine the WCET. However, these methods do not provide early insight in the WCET during development. Therefore, pessimistic assumptions are made by system designers resulting in more expensive, overqualified hardware.
In this paper, an extension on the hybrid methodology is proposed which implements a predictor model using Machine Learning (ML). This new approach estimates the WCET on smaller entities of the code, so-called hybrid blocks, based on software and hardware features. As a result, the ML-based hybrid analysis provides insight of the WCET early-on in the development process and refines its estimate when more detailed features are available. In order to facilitate the extraction of code-related features, a new tool for the COBRA framework is proposed.
This paper proves the potential of the ML-based hybrid approach by conducting multiple experiments based on the TACLeBench on a first prototype. A set of annotated code features were used to train and validate eight different regression models. The results already show promising estimates without tuning any hyperparameters, proving the potential of the methodology.
Cite as
Thomas Huybrechts, Siegfried Mercelis, and Peter Hellinckx. A New Hybrid Approach on WCET Analysis for Real-Time Systems Using Machine Learning. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{huybrechts_et_al:OASIcs.WCET.2018.5,
author = {Huybrechts, Thomas and Mercelis, Siegfried and Hellinckx, Peter},
title = {{A New Hybrid Approach on WCET Analysis for Real-Time Systems Using Machine Learning}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {5:1--5:12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.5},
URN = {urn:nbn:de:0030-drops-97510},
doi = {10.4230/OASIcs.WCET.2018.5},
annote = {Keywords: Worst-Case Execution Time, Machine Learning, Hybrid Analysis, Feature Selection, COde Behaviour fRamework}
}
Document
TASKers: A Whole-System Generator for Benchmarking Real-Time-System Analyses
Abstract
Implementation-based benchmarking of timing and schedulability analyses requires system code that can be executed on real hardware and has defined properties, for example, known worst-case execution times (WCETs) of tasks. Traditional approaches for creating benchmarks with such characteristics often result in implementations that do not resemble real-world systems, either due to work only being simulated by means of busy waiting, or because tasks have no control-flow dependencies between each other. In this paper, we address this problem with TASKers, a generator that constructs realistic benchmark systems with predefined properties. To achieve this, TASKers composes patterns of real-world programs to generate tasks that produce known outputs and exhibit preconfigured WCETs when being executed with certain inputs. Using this knowledge during the generation process, TASKers is able to specifically introduce inter-task control-flow dependencies by mapping the output of one task to the input of another.
Cite as
Christian Eichler, Tobias Distler, Peter Ulbrich, Peter Wägemann, and Wolfgang Schröder-Preikschat. TASKers: A Whole-System Generator for Benchmarking Real-Time-System Analyses. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{eichler_et_al:OASIcs.WCET.2018.6,
author = {Eichler, Christian and Distler, Tobias and Ulbrich, Peter and W\"{a}gemann, Peter and Schr\"{o}der-Preikschat, Wolfgang},
title = {{TASKers: A Whole-System Generator for Benchmarking Real-Time-System Analyses}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {6:1--6:12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.6},
URN = {urn:nbn:de:0030-drops-97528},
doi = {10.4230/OASIcs.WCET.2018.6},
annote = {Keywords: benchmarking real-time-system analyses, task-set generation, whole-system generation, static timing analysis, WCET analysis}
}
Document
Experimental Evaluation of Cache-Related Preemption Delay Aware Timing Analysis
Abstract
In the presence of caches, preemptive scheduling may incur a significant overhead referred to as cache-related preemption delay (CRPD). CRPD is caused by preempting tasks evicting cached memory blocks of preempted tasks, which have to be reloaded when the preempted tasks resume their execution.
In this paper we experimentally evaluate state-of-the-art techniques to account for the CRPD during timing analysis. We find that purely synthetically-generated task sets may yield misleading conclusions regarding the relative precision of different CRPD analysis techniques and the impact of CRPD on schedulability in general. Based on task characterizations obtained by static worst-case execution time (WCET) analysis, we shed new light on the state of the art.
Cite as
Darshit Shah, Sebastian Hahn, and Jan Reineke. Experimental Evaluation of Cache-Related Preemption Delay Aware Timing Analysis. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{shah_et_al:OASIcs.WCET.2018.7,
author = {Shah, Darshit and Hahn, Sebastian and Reineke, Jan},
title = {{Experimental Evaluation of Cache-Related Preemption Delay Aware Timing Analysis}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {7:1--7:11},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.7},
URN = {urn:nbn:de:0030-drops-97532},
doi = {10.4230/OASIcs.WCET.2018.7},
annote = {Keywords: real-time systems, timing analysis, cache-related preemption delay}
}
Document
Embedded Program Annotations for WCET Analysis
Abstract
We present __builtin_ais_annot(), a user-friendly, versatile way to transfer annotations (also known as flow facts) written on the source code level to the machine code level. To do so, we couple two tools often used during the development of safety-critical hard real-time systems, the formally verified C compiler CompCert and the static WCET analyzer aiT. CompCert stores the AIS annotations given via __builtin_ais_annot() in a special section of the ELF binary, which can later be extracted automatically by aiT.
Cite as
Bernhard Schommer, Christoph Cullmann, Gernot Gebhard, Xavier Leroy, Michael Schmidt, and Simon Wegener. Embedded Program Annotations for WCET Analysis. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{schommer_et_al:OASIcs.WCET.2018.8,
author = {Schommer, Bernhard and Cullmann, Christoph and Gebhard, Gernot and Leroy, Xavier and Schmidt, Michael and Wegener, Simon},
title = {{Embedded Program Annotations for WCET Analysis}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {8:1--8:13},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.8},
URN = {urn:nbn:de:0030-drops-97543},
doi = {10.4230/OASIcs.WCET.2018.8},
annote = {Keywords: Worst-Case Execution Time (WCET) Analysis, Annotation Support, CompCert, Tool Coupling, aiT}
}
Document
Fine-Grain Iterative Compilation for WCET Estimation
Abstract
Compiler optimizations, although reducing the execution times of programs, raise issues in static WCET estimation techniques and tools. Flow facts, such as loop bounds, may not be automatically found by static WCET analysis tools after aggressive code optimizations. In this paper, we explore the use of iterative compilation (WCET-directed program optimization to explore the optimization space), with the objective to (i) allow flow facts to be automatically found and (ii) select optimizations that result in the lowest WCET estimates. We also explore to which extent code outlining helps, by allowing the selection of different optimization options for different code snippets of the application.
Cite as
Isabelle Puaut, Mickaël Dardaillon, Christoph Cullmann, Gernot Gebhard, and Steven Derrien. Fine-Grain Iterative Compilation for WCET Estimation. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{puaut_et_al:OASIcs.WCET.2018.9,
author = {Puaut, Isabelle and Dardaillon, Micka\"{e}l and Cullmann, Christoph and Gebhard, Gernot and Derrien, Steven},
title = {{Fine-Grain Iterative Compilation for WCET Estimation}},
booktitle = {18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
pages = {9:1--9:12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-073-6},
ISSN = {2190-6807},
year = {2018},
volume = {63},
editor = {Brandner, Florian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.9},
URN = {urn:nbn:de:0030-drops-97556},
doi = {10.4230/OASIcs.WCET.2018.9},
annote = {Keywords: Worst-Case Execution Time Estimation, Compiler optimizations, Iterative Compilation, Flow fact extraction, Outlining}
}