103 Search Results for "Wilhelm, Reinhard"

Volume

OASIcs, Volume 18

Bringing Theory to Practice: Predictability and Performance in Embedded Systems

PPES 2011, March 18, 2011, Grenoble, France

Editors: Philipp Lucas and Reinhard Wilhelm

Volume

OASIcs, Volume 1

5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)

WCET 2005, July 5, 2005, Palma de Mallorca, Spain

Editors: Reinhard Wilhelm

Volume

OASIcs, Volume 3

Workshop on Trustworthy Software

TrustworthySW 2006, May 18-19, 2006, Saarbruecken, Germany

Editors: Serge Autexier, Stephan Merz, Leon van der Torre, Reinhard Wilhelm, and Pierre Wolper

Document
DOI: 10.4230/LITES.11.1.1
A Survey of Real-Time Support, Analysis, and Advancements in ROS 2

Authors: Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper

Published in: LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1

Abstract
The Robot Operating System 2 (ROS 2) has emerged as a relevant middleware framework for robotic applications, offering modularity, distributed execution, and communication. In the last six years, ROS 2 has drawn increasing attention from the real-time systems community and industry. This survey presents a comprehensive overview of research efforts that analyze, enhance, and extend ROS 2 to support real-time execution. We first provide a detailed description of the internal scheduling mechanisms of ROS 2 and its layered architecture, including the interaction with DDS-based communication and other communication middleware. We then review key contributions from the literature, covering timing analysis for both single- and multi-threaded executors, metrics such as response time, reaction time, and data age, and different communication modes. The survey also discusses community-driven enhancements to the ROS 2 runtime, including new executor algorithm designs, real-time GPU management, and microcontroller support via micro-ROS. Furthermore, we summarize techniques for bounding DDS communication delays, message filters, and profiling tools that have been developed to support analysis and experimentation. To help systematize this growing body of work, we introduce taxonomies that classify the surveyed contributions based on different criteria. This survey aims to guide both researchers and practitioners in understanding and improving the real-time capabilities of ROS 2.
Cite as

Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper. A Survey of Real-Time Support, Analysis, and Advancements in ROS 2. In LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1, pp. 1:1-1:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{casini_et_al:LITES.11.1.1,
  author =	{Casini, Daniel and Chen, Jian-Jia and Li, Jing and Reghenzani, Federico and Teper, Harun},
  title =	{{A Survey of Real-Time Support, Analysis, and Advancements in ROS 2}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:37},
  ISSN =	{2199-2002},
  year =	{2026},
  volume =	{11},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.11.1.1},
  URN =		{urn:nbn:de:0030-drops-257914},
  doi =		{10.4230/LITES.11.1.1},
  annote =	{Keywords: ROS 2, middleware, real-time, timing predictability, publish-subscribe}
}
Document
DOI: 10.4230/LITES.10.2.1
Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management

Authors: Franco Cordeiro, Samuel Tardieu, and Laurent Pautet

Published in: LITES, Volume 10, Issue 2 (2025): Special Issue on Industrial Real-Time Systems. Leibniz Transactions on Embedded Systems, Volume 10, Issue 2

Abstract
Managing actions with uncertain resource costs is a complex challenge, particularly in autonomous robot mission planning. Robots are often assigned multiple objectives with varying criticality levels, ranging from catastrophic to minor impacts, where failures can significantly affect system safety. Uncertainties in worst-case costs of resources, such as energy and operating time - the time it takes to carry out an action - further complicate mission planning and execution. Monte Carlo Tree Search (MCTS) is a powerful tool for online planning, yet it struggles to account for uncertainty in worst-case cost estimations. Optimistic estimates risk resource shortages, while pessimistic ones lead to inefficient allocation. The Mixed-Criticality (MC) approach, originally developed for real-time systems to schedule critical tasks by allocating processing resources under Worst-Case Execution Time (WCET) uncertainty, provides a framework of rules, models and design principles. We claim this framework can be adapted to autonomous robot mission planning, where critical objectives are met through analogous allocation of different kinds of resources such as energy and operating time despite uncertainties. We propose enhancing MCTS with MC principles to handle uncertainty in worst-case costs across multiple resources and criticality of objectives. High-critical objectives must always be completed, regardless of resource constraints, while low-critical objectives operate flexibly, consuming resources within optimistic estimates when possible or being discarded when resources become scarce. This ensures efficient resource reallocation and prioritization of high-critical objectives. To implement this, we present (MC)²TS, a novel variant of MCTS that integrates MC principles for dynamic resource management. It supports more than two criticality levels to ensure that the most critical components meet the most stringent safety and reliability requirements, while also enabling robust resource management. By enabling replanning and mode changes, (MC)²TS improves MCTS’s efficiency and enhances MC systems’ adaptability to both degrading and improving resource conditions. We evaluate (MC)²TS in an active perception scenario, where a drone retrieves data from distributed sensors under unpredictable environmental conditions. (MC)²TS outperforms MCTS by achieving more objectives, adapting plans when costs drop. It explores more objective sequences, minimizes oversizing, and enhances efficiency. Balancing safety and performance, it monitors robot battery, mission and objective resource constraints such as deadlines. Its robustness ensures low-critical objectives do not compromise high-critical objectives, making it a reliable solution for complex systems characterized by uncertain resource costs and critical objectives.
Cite as

Franco Cordeiro, Samuel Tardieu, and Laurent Pautet. Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management. In LITES, Volume 10, Issue 2 (2025): Special Issue on Industrial Real-Time Systems. Leibniz Transactions on Embedded Systems, Volume 10, Issue 2, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{cordeiro_et_al:LITES.10.2.1,
  author =	{Cordeiro, Franco and Tardieu, Samuel and Pautet, Laurent},
  title =	{{Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:23},
  ISSN =	{2199-2002},
  year =	{2025},
  volume =	{10},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.2.1},
  URN =		{urn:nbn:de:0030-drops-252339},
  doi =		{10.4230/LITES.10.2.1},
  annote =	{Keywords: Embedded Systems, Safety / Mixed-Critical Systems, Real-Time Systems, Energy Aware Systems}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.15
Parameterized Complexity of Directed Traveling Salesman Problem

Authors: Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be visited multiple times. The goal is to find a directed closed walk of minimum length (or total weight) that visits every vertex of the given graph at least once. In a yet more general version, Directed Waypoint Routing Problem (DWRP), some vertices are marked as terminals and we are only required to visit all terminals. Furthermore, each edge has its capacity bounding the number of times this edge can be used by a solution. While both problems (and many other variants of TSP) were extensively investigated, mostly from the approximation point of view, there are surprisingly few results concerning the parameterized complexity. Our starting point is the result of Marx et al. [APPROX/RANDOM 2016] who proved that DTSP is W[1]-hard parameterized by distance to pathwidth 3. In this paper we aim to initiate the systematic complexity study of variants of Directed Traveling Salesman Problem with respect to various, mostly structural, parameters. We show that DWRP is FPT parameterized by the solution size, the feedback edge number and the vertex integrity of the underlying undirected graph. Furthermore, the problem is XP parameterized by treewidth. On the complexity side, we show that the problem is W[1]-hard parameterized by the distance to constant treedepth.
Cite as

Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý. Parameterized Complexity of Directed Traveling Salesman Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ISAAC.2025.15,
  author =	{Bla\v{z}ej, V\'{a}clav and Feldmann, Andreas Emil and Fioravantes, Foivos and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej},
  title =	{{Parameterized Complexity of Directed Traveling Salesman Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.15},
  URN =		{urn:nbn:de:0030-drops-249231},
  doi =		{10.4230/LIPIcs.ISAAC.2025.15},
  annote =	{Keywords: Directed TSP, parameterized complexity, vertex integrity, treedepth}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.2
Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems

Authors: Binqi Sun, Zhihang Wei, Andrea Bastoni, Debayan Roy, Mirco Theile, Tomasz Kloda, Rodolfo Pellizzoni, and Marco Caccamo

Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)

Abstract
Memory bandwidth regulation and cache partitioning are widely used techniques for achieving predictable timing in real-time computing systems. Combined with partitioned scheduling, these methods require careful co-allocation of tasks and resources to cores, as task execution times strongly depend on available allocated resources. To address this challenge, this paper presents a 0-1 linear program for task-resource co-allocation, along with a multi-objective heuristic designed to minimize resource usage while guaranteeing schedulability under a preemptive EDF scheduling policy. Our heuristic employs a multi-layer framework, where an outer layer explores resource allocations using Pareto-pruned search, and an inner layer optimizes task allocation by solving a knapsack problem using dynamic programming. To evaluate the performance of the proposed optimization algorithm, we profile real-world benchmarks on an embedded AMD UltraScale+ ZCU102 platform, with fine-grained resource partitioning enabled by the Jailhouse hypervisor, leveraging cache set partitioning and MemGuard for memory bandwidth regulation. Experiments based on the benchmarking results show that the proposed 0-1 linear program outperforms existing mixed-integer programs by finding more optimal solutions within the same time limit. Moreover, the proposed multi-objective multi-layer heuristic performs consistently better than the state-of-the-art multi-resource-task co-allocation algorithm in terms of schedulability, resource usage, number of non-dominated solutions, and computational efficiency.
Cite as

Binqi Sun, Zhihang Wei, Andrea Bastoni, Debayan Roy, Mirco Theile, Tomasz Kloda, Rodolfo Pellizzoni, and Marco Caccamo. Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.ECRTS.2025.2,
  author =	{Sun, Binqi and Wei, Zhihang and Bastoni, Andrea and Roy, Debayan and Theile, Mirco and Kloda, Tomasz and Pellizzoni, Rodolfo and Caccamo, Marco},
  title =	{{Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-377-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{335},
  editor =	{Mancuso, Renato},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.2},
  URN =		{urn:nbn:de:0030-drops-235807},
  doi =		{10.4230/LIPIcs.ECRTS.2025.2},
  annote =	{Keywords: Multi-objective optimization, memory bandwidth regulation, cache partitioning, partitioned scheduling, real-time systems}
}
Document
DOI: 10.4230/OASIcs.PARMA-DITAM.2025.4
Towards Studying the Effect of Compiler Optimizations and Software Randomization on GPU Reliability

Authors: Pau López Castillón, Xavier Caricchio Hernández, and Leonidas Kosmidis

Published in: OASIcs, Volume 127, 16th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 14th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2025)

Abstract
The evolution of Graphics Processing Unit (GPU) compilers has facilitated the support for general-purpose programming languages across various architectures. The NVIDIA CUDA Compiler (NVCC) employs multiple compilation levels prior to generating machine code, implementing intricate optimizations to enhance performance. These optimizations influence the manner in which software is mapped to the underlying hardware, which can also impact GPU reliability. TASA is a source-to-source code randomization tool designed to alter the mapping of software onto the underlying hardware. It achieves this by generating random permutations of variable and function declarations, thereby introducing random padding between declarations of different types and modifying the program memory layout. Since this modifies their location in the memory, it also modifies their cache placement, affecting both their execution time (due to the different conflicts between them, which result in a different amount of cache misses in every execution), as well as their lifetime in the cache. In this work, which is part of the HiPEAC Student Challenge 2025, we first examine the reproducibility of a subset of data presented in the ACM TACO paper "Assessing the Impact of Compiler Optimizations on GPU Reliability" [Santos et al., 2024], and second we extend it by combining it with our proposal of software randomization. The paper indicates that the -O3 optimization flag facilitates an increased workload before failures occur within the application. By employing TASA, we investigate the impact of GPU randomization on reliability and performance metrics. By reproducing the results of the paper on a different GPU platform, we observe the same trend as reported in the original publication. Moreover, our preliminary results with the application of software randomization show in several cases an improved Mean Waiting Before Failure (MWBF) compared to the original source code.
Cite as

Pau López Castillón, Xavier Caricchio Hernández, and Leonidas Kosmidis. Towards Studying the Effect of Compiler Optimizations and Software Randomization on GPU Reliability. In 16th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 14th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2025). Open Access Series in Informatics (OASIcs), Volume 127, pp. 4:1-4:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{castillon_et_al:OASIcs.PARMA-DITAM.2025.4,
  author =	{Castill\'{o}n, Pau L\'{o}pez and Hern\'{a}ndez, Xavier Caricchio and Kosmidis, Leonidas},
  title =	{{Towards Studying the Effect of Compiler Optimizations and Software Randomization on GPU Reliability}},
  booktitle =	{16th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 14th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2025)},
  pages =	{4:1--4:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-363-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{127},
  editor =	{Cattaneo, Daniele and Fazio, Maria and Kosmidis, Leonidas and Morabito, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.PARMA-DITAM.2025.4},
  URN =		{urn:nbn:de:0030-drops-229083},
  doi =		{10.4230/OASIcs.PARMA-DITAM.2025.4},
  annote =	{Keywords: Graphics processing units, reliability, software randomization, error rate}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.12
Structural Summarization of Semantic Graphs Using Quotients

Authors: Ansgar Scherp, David Richerby, Till Blume, Michael Cochez, and Jannik Rau

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Graph summarization is the process of computing a compact version of an input graph while preserving chosen features of its structure. We consider semantic graphs where the features include edge labels and label sets associated with a vertex. Graph summaries are typically much smaller than the original graph. Applications that depend on the preserved features can perform their tasks on the summary, but much faster or with less memory overhead, while producing the same outcome as if they were applied on the original graph. In this survey, we focus on structural summaries based on quotients that organize vertices in equivalence classes of shared features. Structural summaries are particularly popular for semantic graphs and have the advantage of defining a precise graph-based output. We consider approaches and algorithms for both static and temporal graphs. A common example of quotient-based structural summaries is bisimulation, and we discuss this in detail. While there exist other surveys on graph summarization, to the best of our knowledge, we are the first to bring in a focused discussion on quotients, bisimulation, and their relation. Furthermore, structural summarization naturally connects well with formal logic due to the discrete structures considered. We complete the survey with a brief description of approaches beyond structural summaries.
Cite as

Ansgar Scherp, David Richerby, Till Blume, Michael Cochez, and Jannik Rau. Structural Summarization of Semantic Graphs Using Quotients. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 12:1-12:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{scherp_et_al:TGDK.1.1.12,
  author =	{Scherp, Ansgar and Richerby, David and Blume, Till and Cochez, Michael and Rau, Jannik},
  title =	{{Structural Summarization of Semantic Graphs Using Quotients}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{12:1--12:25},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.12},
  URN =		{urn:nbn:de:0030-drops-194862},
  doi =		{10.4230/TGDK.1.1.12},
  annote =	{Keywords: graph summarization, quotients, stratified bisimulation}
}
Document
DOI: 10.4230/LITES.7.1.1
Randomization as Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Real-Time Systems with Task Replication

Authors: Kristin Krüger, Nils Vreman, Richard Pates, Martina Maggio, Marcus Völp, and Gerhard Fohler

Published in: LITES, Volume 7, Issue 1 (2021): Special Issue on Embedded System Security. Leibniz Transactions on Embedded Systems, Volume 7, Issue 1

Abstract
Time-triggered real-time systems achieve deterministic behavior using schedules that are constructed offline, based on scheduling constraints. Their deterministic behavior makes time-triggered systems suitable for usage in safety-critical environments, like avionics. However, this determinism also allows attackers to fine-tune attacks that can be carried out after studying the behavior of the system through side channels, targeting safety-critical victim tasks. Replication -- i.e., the execution of task variants across different cores -- is inherently able to tolerate both accidental and malicious faults (i.e. attacks) as long as these faults are independent of one another. Yet, targeted attacks on the timing behavior of tasks which utilize information gained about the system behavior violate the fault independence assumption fault tolerance is based on. This violation may give attackers the opportunity to compromise all replicas simultaneously, in particular if they can mount the attack from already compromised components. In this paper, we analyze vulnerabilities of time-triggered systems, focusing on safety-certified multicore real-time systems. We introduce two runtime mitigation strategies to withstand directed timing inference based attacks: (i) schedule randomization at slot level, and (ii) randomization within a set of offline constructed schedules. We evaluate these mitigation strategies with synthetic experiments and a real case study to show their effectiveness and practicality.
Cite as

Kristin Krüger, Nils Vreman, Richard Pates, Martina Maggio, Marcus Völp, and Gerhard Fohler. Randomization as Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Real-Time Systems with Task Replication. In LITES, Volume 7, Issue 1 (2021): Special Issue on Embedded System Security. Leibniz Transactions on Embedded Systems, Volume 7, Issue 1, pp. 01:1-01:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{kruger_et_al:LITES.7.1.1,
  author =	{Kr\"{u}ger, Kristin and Vreman, Nils and Pates, Richard and Maggio, Martina and V\"{o}lp, Marcus and Fohler, Gerhard},
  title =	{{Randomization as Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Real-Time Systems with Task Replication}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:29},
  ISSN =	{2199-2002},
  year =	{2021},
  volume =	{7},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.7.1.1},
  URN =		{urn:nbn:de:0030-drops-192847},
  doi =		{10.4230/LITES.7.1.1},
  annote =	{Keywords: real-time systems, time-triggered systems, security}
}
Document
DOI: 10.4230/LITES-v006-i001-a002
Improving WCET Evaluation using Linear Relation Analysis

Authors: Pascal Raymond, Claire Maiza, Catherine Parent-Vigouroux, Erwan Jahier, Nicolas Halbwachs, Fabienne Carrier, Mihail Asavoae, and Rémy Boutonnet

Published in: LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1

Abstract
The precision of a worst case execution time (WCET) evaluation tool on a given program is highly dependent on how the tool is able to detect and discard semantically infeasible executions of the program. In this paper, we propose to use the classical abstract interpretation-based method of linear relation analysis to discover and exploit relations between execution paths. For this purpose, we add auxiliary variables (counters) to the program to trace its execution paths. The results are easily incorporated in the classical workflow of a WCET evaluator, when the evaluator is based on the popular implicit path enumeration technique. We use existing tools - a WCET evaluator and a linear relation analyzer - to build and experiment a prototype implementation of this idea.
Cite as

Pascal Raymond, Claire Maiza, Catherine Parent-Vigouroux, Erwan Jahier, Nicolas Halbwachs, Fabienne Carrier, Mihail Asavoae, and Rémy Boutonnet. Improving WCET Evaluation using Linear Relation Analysis. In LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1, pp. 02:1-02:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{raymond_et_al:LITES-v006-i001-a002,
  author =	{Raymond, Pascal and Maiza, Claire and Parent-Vigouroux, Catherine and Jahier, Erwan and Halbwachs, Nicolas and Carrier, Fabienne and Asavoae, Mihail and Boutonnet, R\'{e}my},
  title =	{{Improving WCET Evaluation using Linear Relation Analysis}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{02:1--02:28},
  ISSN =	{2199-2002},
  year =	{2019},
  volume =	{6},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v006-i001-a002},
  URN =		{urn:nbn:de:0030-drops-192784},
  doi =		{10.4230/LITES-v006-i001-a002},
  annote =	{Keywords: Worst Case Execution Time estimation, Infeasible Execution Paths, Abstract Interpretation}
}
Document
Invited Paper
DOI: 10.4230/OASIcs.WCET.2018.1
Mixed Feelings About Mixed Criticality (Invited Paper)

Authors: Reinhard Wilhelm

Published in: OASIcs, Volume 63, 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)

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
DOI: 10.4230/LITES-v005-i001-a003
The Semantic Foundations and a Landscape of Cache-Persistence Analyses

Authors: Jan Reineke

Published in: LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1

Abstract
We clarify the notion of cache persistence and contribute to the understanding of persistence analysis for caches with least-recently-used replacement.To this end, we provide the first formal definition of persistence as a property of a trace semantics. Based on this trace semantics we introduce a semantics-based, i.e., abstract-interpretation-based persistence analysis framework.We identify four basic persistence analyses and prove their correctness as instances of this analysis framework.Combining these basic persistence analyses via two generic cooperation mechanisms yields a lattice of ten persistence analyses.Notably, this lattice contains all persistence analyses previously described in the literature. As a consequence, we obtain uniform correctness proofs for all prior analyses and a precise understanding of how and why these analyses work, as well as how they relate to each other in terms of precision.
Cite as

Jan Reineke. The Semantic Foundations and a Landscape of Cache-Persistence Analyses. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 03:1-03:52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{reineke:LITES-v005-i001-a003,
  author =	{Reineke, Jan},
  title =	{{The Semantic Foundations and a Landscape of Cache-Persistence Analyses}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{03:1--03:52},
  ISSN =	{2199-2002},
  year =	{2018},
  volume =	{5},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v005-i001-a003},
  URN =		{urn:nbn:de:0030-drops-192748},
  doi =		{10.4230/LITES-v005-i001-a003},
  annote =	{Keywords: caches, persistence analysis, WCET analysis}
}
Document
DOI: 10.4230/DagRep.7.7.72
Resource Bound Analysis (Dagstuhl Seminar 17291)

Authors: Marco Gaboardi, Jan Hoffman, Reinhard Wilhelm, and Florian Zuleger

Published in: Dagstuhl Reports, Volume 7, Issue 7 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17291 "Resource Bound Analysis". Resource-bound analysis is studied in formal methods and programming languages at different levels of abstraction. The goal of the Dagstuhl seminar was to bring together leading researchers with different backgrounds in resource-bound analysis to address challenging open problems and to facilitate communication across research areas.
Cite as

Marco Gaboardi, Jan Hoffman, Reinhard Wilhelm, and Florian Zuleger. Resource Bound Analysis (Dagstuhl Seminar 17291). In Dagstuhl Reports, Volume 7, Issue 7, pp. 72-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{gaboardi_et_al:DagRep.7.7.72,
  author =	{Gaboardi, Marco and Hoffman, Jan and Wilhelm, Reinhard and Zuleger, Florian},
  title =	{{Resource Bound Analysis (Dagstuhl Seminar 17291)}},
  pages =	{72--87},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{7},
  editor =	{Gaboardi, Marco and Hoffman, Jan and Wilhelm, Reinhard and Zuleger, Florian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.7.72},
  URN =		{urn:nbn:de:0030-drops-84241},
  doi =		{10.4230/DagRep.7.7.72},
  annote =	{Keywords: quantitative analysis, resource-bound analysis, WCET}
}
Document
DOI: 10.4230/LITES-v004-i002-a002
EMSBench: Benchmark and Testbed for Reactive Real-Time Systems

Authors: Florian Kluge, Christine Rochange, and Theo Ungerer

Published in: LITES, Volume 4, Issue 2 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 2

Abstract
Benchmark suites for real-time embedded systems (RTES) usually contain only pure computations that are often used in this domain. They allow to evaluate computing performance, but do not reproduce the complexity and behaviour that is typical for such systems. Actual RTES have to interact with the physical environment, which is often reflected by code that is executed concurrently. In this article, we present the software package EMSBench that mimics such complex behaviour, and highlight some of its use cases. The benchmark code ems of EMSBench is based on the open-source engine management system (EMS) FreeEMS. Additionally, EMSBench contains a trace generator (tg) that provides input signals for ems and enables to execute ems close to reality. We provide detailed descriptions of the ems's execution behaviour and of trace generation. EMSBench can be used as test or benchmark program to compare different hardware platforms, e.g. in terms of schedulability. Also, we use EMSBench as a benchmark for static worst-case execution time (WCET) analysis and compare these results to measurements performed on existing hardware. Our results based on the OTAWA WCET estimation tool show WCET overestimations by the static analysis from 11.9% to 41.1% depending on the complexity of the analysed functions.
Cite as

Florian Kluge, Christine Rochange, and Theo Ungerer. EMSBench: Benchmark and Testbed for Reactive Real-Time Systems. In LITES, Volume 4, Issue 2 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 2, pp. 02:1-02:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{kluge_et_al:LITES-v004-i002-a002,
  author =	{Kluge, Florian and Rochange, Christine and Ungerer, Theo},
  title =	{{EMSBench: Benchmark and Testbed for Reactive Real-Time Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{02:1--02:23},
  ISSN =	{2199-2002},
  year =	{2017},
  volume =	{4},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i002-a002},
  URN =		{urn:nbn:de:0030-drops-192698},
  doi =		{10.4230/LITES-v004-i002-a002},
  annote =	{Keywords: Real-time benchmark, WCET Analysis, Engine Management System}
}
  • Refine by Type
  • 100 Document/PDF
  • 5 Document/HTML
  • 3 Volume

  • Refine by Publication Year
  • 1 2026
  • 4 2025
  • 1 2023
  • 1 2021
  • 1 2019
  • Show More...

  • Refine by Author
  • 58 Wilhelm, Reinhard
  • 21 Müller-von Brochowski, Angelika
  • 14 Müller, Fritz
  • 6 Reineke, Jan
  • 4 Thiele, Lothar
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 38 OASIcs
  • 10 LITES
  • 1 TGDK
  • 1 DagMan
  • Show More...

  • Refine by Classification
  • 4 Computer systems organization → Real-time systems
  • 4 Software and its engineering → Real-time systems software
  • 3 Computer systems organization → Real-time system architecture
  • 2 General and reference → Surveys and overviews
  • 2 Hardware → Safety critical systems
  • Show More...

  • Refine by Keyword
  • 24 IBFI
  • 24 Internationales Begegnungs- und Forschungszentrum für Informatik
  • 24 Schloss Dagstuhl
  • 21 Schloss Dagstuhl - Leibniz-Zentrum für Informatik
  • 16 International Conference and Research Center for Computer Science
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact