21 Search Results for "Lisper, Björn"

Volume

OASIcs, Volume 15

10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)

WCET 2010, July 6, 2010, Brussels, Belgium

Editors: Björn Lisper

Document
DOI: 10.4230/LIPIcs.ECRTS.2025.12
Real-Time System Evaluation Techniques: A Systematic Mapping Study

Authors: Tilmann L. Unte and Sebastian Altmeyer

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

Abstract
A systematic mapping study assesses a broad selection of research publications with the aim of categorizing them according to a research question. We present the first systematic mapping study on evaluation practices within the field of real-time systems, by analyzing publications from the top three conferences ECRTS, RTAS, and RTSS from 2017 until 2024. Our study provides a comprehensive view on the evaluation practices prevalent in our community, including benchmark software, task set and graph generators, case studies, industrial challenges, and custom solutions. Based on our study, we construct and publish a dataset enabling quantitative analysis of evaluation practices within the real-time systems community. Our analysis indicates shortcomings in current practice: custom case studies are abundant, while industrial challenges have very minor impact. Reproducibility has only been shown for a small subset of evaluations and there is no indication of change. Adoption of new and improved tools and benchmarks is very slow or even non-existent. Evaluation must not be viewed as an obligation when publishing a paper, but as a key element in ensuring practicability, comparability, and reproducibility. Based on our study, we conclude that our community currently falls short on these objectives.
Cite as

Tilmann L. Unte and Sebastian Altmeyer. Real-Time System Evaluation Techniques: A Systematic Mapping Study. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{unte_et_al:LIPIcs.ECRTS.2025.12,
  author =	{Unte, Tilmann L. and Altmeyer, Sebastian},
  title =	{{Real-Time System Evaluation Techniques: A Systematic Mapping Study}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{12:1--12:21},
  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.12},
  URN =		{urn:nbn:de:0030-drops-235903},
  doi =		{10.4230/LIPIcs.ECRTS.2025.12},
  annote =	{Keywords: Systematic Mapping Study, Real-Time Systems, Evaluation}
}
Document
DOI: 10.4230/LITES.10.1.3
Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks

Authors: Benjamin Standaert, Fatima Raadia, Marion Sudvarg, Sanjoy Baruah, Thidapat Chantem, Nathan Fisher, and Christopher Gill

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

Abstract
Safety-critical embedded systems such as autonomous vehicles typically have only very limited computational capabilities on board that must be carefully managed to provide required enhanced functionalities. As these systems become more complex and inter-connected, some parts may need to be secured to prevent unauthorized access, or isolated to ensure correctness. We propose the multi-phase secure (MPS) task model as a natural extension of the widely used sporadic task model for modeling both the timing and the security (and isolation) requirements for such systems. Under MPS, task phases reflect execution using different security mechanisms which each have associated execution time costs for startup and teardown. We develop corresponding limited-preemption EDF scheduling algorithms and associated pseudo-polynomial schedulability tests for constrained-deadline MPS tasks. In doing so, we provide a correction to a long-standing schedulability condition for EDF under limited-preemption. Evaluation shows that the proposed tests are efficient to compute for bounded utilizations. We empirically demonstrate that the MPS model successfully schedules more task sets compared to non-preemptive approaches.
Cite as

Benjamin Standaert, Fatima Raadia, Marion Sudvarg, Sanjoy Baruah, Thidapat Chantem, Nathan Fisher, and Christopher Gill. Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks. In LITES, Volume 10, Issue 1 (2025). Leibniz Transactions on Embedded Systems, Volume 10, Issue 1, pp. 3:1-3:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{standaert_et_al:LITES.10.1.3,
  author =	{Standaert, Benjamin and Raadia, Fatima and Sudvarg, Marion and Baruah, Sanjoy and Chantem, Thidapat and Fisher, Nathan and Gill, Christopher},
  title =	{{Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{3:1--3:27},
  ISSN =	{2199-2002},
  year =	{2025},
  volume =	{10},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.1.3},
  URN =		{urn:nbn:de:0030-drops-230799},
  doi =		{10.4230/LITES.10.1.3},
  annote =	{Keywords: real-time systems, limited-preemption scheduling, trusted execution environments}
}
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
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/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}
}
Document
DOI: 10.4230/OASIcs.WCET.2016.2
TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research

Authors: Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sørensen, Peter Wägemann, and Simon Wegener

Published in: OASIcs, Volume 55, 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016)

Abstract
Engineering related research, such as research on worst-case execution time, uses experimentation to evaluate ideas. For these experiments we need example programs. Furthermore, to make the research experimentation repeatable those programs shall be made publicly available. We collected open-source programs, adapted them to a common coding style, and provide the collection in open-source. The benchmark collection is called TACLeBench and is available from GitHub in version 1.9 at the publication date of this paper. One of the main features of TACLeBench is that all programs are self-contained without any dependencies on standard libraries or an operating system.
Cite as

Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sørensen, Peter Wägemann, and Simon Wegener. TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research. In 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016). Open Access Series in Informatics (OASIcs), Volume 55, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{falk_et_al:OASIcs.WCET.2016.2,
  author =	{Falk, Heiko and Altmeyer, Sebastian and Hellinckx, Peter and Lisper, Bj\"{o}rn and Puffitsch, Wolfgang and Rochange, Christine and Schoeberl, Martin and S{\o}rensen, Rasmus Bo and W\"{a}gemann, Peter and Wegener, Simon},
  title =	{{TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research}},
  booktitle =	{16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016)},
  pages =	{2:1--2:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-025-5},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{55},
  editor =	{Schoeberl, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2016.2},
  URN =		{urn:nbn:de:0030-drops-68958},
  doi =		{10.4230/OASIcs.WCET.2016.2},
  annote =	{Keywords: Benchmark, WCET analysis, real-time systems}
}
Document
DOI: 10.4230/OASIcs.WCET.2015.65
WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?

Authors: Sebastian Altmeyer, Björn Lisper, Claire Maiza, Jan Reineke, and Christine Rochange

Published in: OASIcs, Volume 47, 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)

Abstract
Mixed-criticality systems integrate components of different criticality. Different criticality levels require different levels of confidence in the correct behavior of a component. One aspect of correctness is timing. Confidence in worst-case execution time (WCET) estimates depends on the process by which they have been obtained. A somewhat naive view is that static WCET analyses determines safe bounds in which we can have absolute confidence, while measurement-based approaches are inherently unreliable. In this paper, we refine this view by exploring sources of doubt in the correctness of both static and measurement-based WCET analysis.
Cite as

Sebastian Altmeyer, Björn Lisper, Claire Maiza, Jan Reineke, and Christine Rochange. WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015). Open Access Series in Informatics (OASIcs), Volume 47, pp. 65-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{altmeyer_et_al:OASIcs.WCET.2015.65,
  author =	{Altmeyer, Sebastian and Lisper, Bj\"{o}rn and Maiza, Claire and Reineke, Jan and Rochange, Christine},
  title =	{{WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?}},
  booktitle =	{15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)},
  pages =	{65--74},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-95-8},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{47},
  editor =	{Cazorla, Francisco J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2015.65},
  URN =		{urn:nbn:de:0030-drops-52574},
  doi =		{10.4230/OASIcs.WCET.2015.65},
  annote =	{Keywords: mixed criticality, WCET analysis, confidence in WCET estimates}
}
Document
DOI: 10.4230/OASIcs.WCET.2015.85
Analysing Switch-Case Code with Abstract Execution

Authors: Niklas Holsti, Jan Gustafsson, Linus Källberg, and Björn Lisper

Published in: OASIcs, Volume 47, 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)

Abstract
Constructing the control-flow graph (CFG) of machine code is made difficult by dynamic transfers of control (DTC), where the address of the next instruction is computed at run-time. Switchcase statements make compilers generate a large variety of machine-code forms with DTC. Two analysis approaches are commonly used: pattern-matching methods identify predefined instruction patterns to extract the target addresses, while analytical methods try to compute the set of target addresses using a general value-analysis. We tested the abstract execution method of the SWEET tool as a value analysis for switch-case code. SWEET is here used as a plugin to the Bound-T tool: thus our work can also be seen as an experiment in modular tool design, where a general value-analysis tool is used to aid the CFG construction in a WCET analysis tool. We find that the abstract-execution analysis works at least as well as the switch-case analyses in Bound-T itself, which are mostly based on pattern-matching. However, there are still some weaknesses: the abstract domains available in SWEET are not well suited to representing sets of DTC target addresses, which are small but sparse and irregular. Also, in some cases the abstract-execution analysis fails because the used domain is not relational, that is, does not model arithmetic relationships between the values of different variables. Future work will be directed towards the design of abstract domains eliminating these weaknesses.
Cite as

Niklas Holsti, Jan Gustafsson, Linus Källberg, and Björn Lisper. Analysing Switch-Case Code with Abstract Execution. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015). Open Access Series in Informatics (OASIcs), Volume 47, pp. 85-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{holsti_et_al:OASIcs.WCET.2015.85,
  author =	{Holsti, Niklas and Gustafsson, Jan and K\"{a}llberg, Linus and Lisper, Bj\"{o}rn},
  title =	{{Analysing Switch-Case Code with Abstract Execution}},
  booktitle =	{15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)},
  pages =	{85--94},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-95-8},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{47},
  editor =	{Cazorla, Francisco J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2015.85},
  URN =		{urn:nbn:de:0030-drops-52598},
  doi =		{10.4230/OASIcs.WCET.2015.85},
  annote =	{Keywords: ynamic control flow, indexed branch, machine-code analysis, WCET analysis}
}
Document
DOI: 10.4230/OASIcs.WCET.2014.1
Principles for Value Annotation Languages

Authors: Björn Lisper

Published in: OASIcs, Volume 39, 14th International Workshop on Worst-Case Execution Time Analysis (2014)

Abstract
Tools for code-level program analysis need formats to express various properties, like relevant properties of the environment where the analysed code will execute, and the analysis results. Different WCET analysis tools typically use tool-specific annotation languages for this purpose. These languages are often geared towards expressing properties that the particular tool can handle rather than being general, and mostly their semantics is only specified informally. This makes it harder for tools to communicate, as well as for users to provide relevant information to them. Here, we propose a small but general assertion language for value constraints including IPET flow facts, which is an important class of annotations for WCET analysis tools. We show how to express interesting properties in this language, we propose some syntactic conveniences, and we give the language a formal semantics. The language could be used directly as a tool-independent annotation language, or as a meta-language to give exact semantics to existing value annotation and flow fact formats.
Cite as

Björn Lisper. Principles for Value Annotation Languages. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{lisper:OASIcs.WCET.2014.1,
  author =	{Lisper, Bj\"{o}rn},
  title =	{{Principles for Value Annotation Languages}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{1--10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-69-9},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{39},
  editor =	{Falk, Heiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2014.1},
  URN =		{urn:nbn:de:0030-drops-45996},
  doi =		{10.4230/OASIcs.WCET.2014.1},
  annote =	{Keywords: Real-Time System, WCET analysis, Flow Fact, Assertion}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.WCET.2010
OASIcs, Volume 15, WCET'10, Complete Volume

Authors: Björn Lisper

Published in: OASIcs, Volume 15, 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)

Abstract
OASIcs, Volume 15, WCET'10, Complete Volume
Cite as

10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010). Open Access Series in Informatics (OASIcs), Volume 15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{lisper:OASIcs.WCET.2010,
  title =	{{OASIcs, Volume 15, WCET'10, Complete Volume}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-21-7},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{15},
  editor =	{Lisper, Bj\"{o}rn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2010},
  URN =		{urn:nbn:de:0030-drops-35771},
  doi =		{10.4230/OASIcs.WCET.2010},
  annote =	{Keywords: Performance of Systems, Software/Program Verification, Computers in Other Systems}
}
Document
DOI: 10.4230/OASIcs.WCET.2012.38
Toward Static Timing Analysis of Parallel Software

Authors: Andreas Gustavsson, Jan Gustafsson, and Björn Lisper

Published in: OASIcs, Volume 23, 12th International Workshop on Worst-Case Execution Time Analysis (2012)

Abstract
The current trend within computer, and even real-time, systems is to incorporate parallel hardware, e.g., multicore processors, and parallel software. Thus, the ability to safely analyse such parallel systems, e.g., regarding the timing behaviour, becomes necessary. Static timing analysis is an approach to mathematically derive safe bounds on the execution time of a program, when executed on a given hardware platform. This paper presents an algorithm that statically analyses the timing of parallel software, with threads communicating through shared memory, using abstract interpretation. It also gives an extensive example to clarify how the algorithm works.
Cite as

Andreas Gustavsson, Jan Gustafsson, and Björn Lisper. Toward Static Timing Analysis of Parallel Software. In 12th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 23, pp. 38-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{gustavsson_et_al:OASIcs.WCET.2012.38,
  author =	{Gustavsson, Andreas and Gustafsson, Jan and Lisper, Bj\"{o}rn},
  title =	{{Toward Static Timing Analysis of Parallel Software}},
  booktitle =	{12th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{38--47},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-41-5},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{23},
  editor =	{Vardanega, Tullio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2012.38},
  URN =		{urn:nbn:de:0030-drops-35552},
  doi =		{10.4230/OASIcs.WCET.2012.38},
  annote =	{Keywords: Parallelism, BCET, WCET, Static analysis, Abstract interpretation}
}
Document
DOI: 10.4230/OASIcs.WCET.2012.48
Towards Parallel Programming Models for Predictability

Authors: Björn Lisper

Published in: OASIcs, Volume 23, 12th International Workshop on Worst-Case Execution Time Analysis (2012)

Abstract
Future embedded systems for performance-demanding applications will be massively parallel. High performance tasks will be parallel programs, running on several cores, rather than single threads running on single cores. For hard real-time applications, WCETs for such tasks must be bounded. Low-level parallel programming models, based on concurrent threads, are notoriously hard to use due to their inherent nondeterminism. Therefore the parallel processing community has long considered high-level parallel programming models, which restrict the low-level models to regain determinism. In this position paper we argue that such parallel programming models are beneficial also for WCET analysis of parallel programs. We review some proposed models, and discuss their influence on timing predictability. In particular we identify data parallel programming as a suitable paradigm as it is deterministic and allows current methods for WCET analysis to be extended to parallel code. GPUs are increasingly used for high performance applications: we discuss a current GPU architecture, and we argue that it offers a parallel platform for compute-intensive applications for which it seems possible to construct precise timing models. Thus, a promising route for the future is to develop WCET analyses for data-parallel software running on GPUs.
Cite as

Björn Lisper. Towards Parallel Programming Models for Predictability. In 12th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 23, pp. 48-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{lisper:OASIcs.WCET.2012.48,
  author =	{Lisper, Bj\"{o}rn},
  title =	{{Towards Parallel Programming Models for Predictability}},
  booktitle =	{12th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{48--58},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-41-5},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{23},
  editor =	{Vardanega, Tullio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2012.48},
  URN =		{urn:nbn:de:0030-drops-35565},
  doi =		{10.4230/OASIcs.WCET.2012.48},
  annote =	{Keywords: Real-Time System, WCET analysis, Parallel Program, Data Parallelism}
}
Document
Front Matter
DOI: 10.4230/OASIcs.WCET.2010.i
Frontmatter, Preface, Table of Contents, Workshop Organization

Authors: Björn Lisper

Published in: OASIcs, Volume 15, 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)

Abstract
Frontmatter, Preface, Table of Contents, Workshop Organization.
Cite as

10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010). Open Access Series in Informatics (OASIcs), Volume 15, pp. i-ix, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{lisper:OASIcs.WCET.2010.i,
  author =	{Lisper, Bj\"{o}rn},
  title =	{{Frontmatter, Preface, Table of Contents, Workshop Organization}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{i--ix},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-21-7},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{15},
  editor =	{Lisper, Bj\"{o}rn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2010.i},
  URN =		{urn:nbn:de:0030-drops-28195},
  doi =		{10.4230/OASIcs.WCET.2010.i},
  annote =	{Keywords: Frontmatter, Preface, Table of Contents, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.WCET.2010.101
Towards WCET Analysis of Multicore Architectures Using UPPAAL

Authors: Andreas Gustavsson, Andreas Ermedahl, Björn Lisper, and Paul Pettersson

Published in: OASIcs, Volume 15, 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)

Abstract
To take full advantage of the increasingly used shared-memory multicore architectures, software algorithms will need to be parallelized over multiple threads. This means that threads will have to share resources (e.g. some level of cache) and communicate and synchronize with each other. There already exist software libraries (e.g. OpenMP) used to explicitly parallelize available sequential C/C++ and Fortran code, which means that parallel code could be easily obtained. To be able to use parallel software running on multicore architectures in embedded systems with hard real-time constraints, new WCET (Worst-Case Execution Time) analysis methods and tools must be developed. This paper investigates a method based on model-checking a system of timed automata using the UPPAAL tool box. It is found that it is possible to perform WCET analysis on (small) parallel systems using UPPAAL. We also show how to model thread synchronization using spinlock-like primitives.
Cite as

Andreas Gustavsson, Andreas Ermedahl, Björn Lisper, and Paul Pettersson. Towards WCET Analysis of Multicore Architectures Using UPPAAL. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010). Open Access Series in Informatics (OASIcs), Volume 15, pp. 101-112, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{gustavsson_et_al:OASIcs.WCET.2010.101,
  author =	{Gustavsson, Andreas and Ermedahl, Andreas and Lisper, Bj\"{o}rn and Pettersson, Paul},
  title =	{{Towards WCET Analysis of Multicore Architectures Using UPPAAL}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{101--112},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-21-7},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{15},
  editor =	{Lisper, Bj\"{o}rn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2010.101},
  URN =		{urn:nbn:de:0030-drops-28304},
  doi =		{10.4230/OASIcs.WCET.2010.101},
  annote =	{Keywords: WCET, Multicore, Parallel, Thread Synchronization, Model-Checking, UPPAAL}
}
  • Refine by Type
  • 20 Document/PDF
  • 2 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 2 2025
  • 1 2019
  • 1 2018
  • 1 2017
  • 1 2016
  • Show More...

  • Refine by Author
  • 15 Lisper, Björn
  • 6 Ermedahl, Andreas
  • 6 Gustafsson, Jan
  • 3 Altmeyer, Sebastian
  • 3 Rochange, Christine
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 15 OASIcs
  • 4 LITES

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

  • Refine by Keyword
  • 9 WCET analysis
  • 3 WCET
  • 2 Real-Time System
  • 2 abstract interpretation
  • 2 real-time systems
  • 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