17 Search Results for "Maiza, Claire"

Volume

OASIcs, Volume 30

13th International Workshop on Worst-Case Execution Time Analysis

WCET 2013, July 9, 2013, Paris, France

Editors: Claire Maiza

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-dev.dagstuhl.de/entities/document/10.4230/LITES-v006-i001-a002},
  doi =		{10.4230/LITES-v006-i001-a002},
  annote =	{Keywords: Worst Case Execution Time estimation, Infeasible Execution Paths, Abstract Interpretation}
}
Document
DOI: 10.4230/OASIcs.WCET.2017.9
The W-SEPT Project: Towards Semantic-Aware WCET Estimation

Authors: Claire Maiza, Pascal Raymond, Catherine Parent-Vigouroux, Armelle Bonenfant, Fabienne Carrier, Hugues Cassé, Philippe Cuenot, Denis Claraz, Nicolas Halbwachs, Erwan Jahier, Hanbing Li, Marianne de Michiel, Vincent Mussot, Isabelle Puaut, Christine Rochange, Erven Rohou, Jordy Ruiz, Pascal Sotin, and Wei-Tsun Sun

Published in: OASIcs, Volume 57, 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)

Abstract
Critical embedded systems are generally composed of repetitive tasks that must meet hard timing constraints, such as termination deadlines. Providing an upper bound of the worst-case execution time (WCET) of such tasks at design time is necessary to guarantee the correctness of the system. In static WCET analysis, a main source of over-approximation comes from the complexity of the modern hardware platforms: their timing behavior tends to become more unpredictable because of features like caches, pipeline, branch prediction, etc. Another source of over-approximation comes from the software itself: WCET analysis may consider potential worst-cases executions that are actually infeasible, because of the semantics of the program or because they correspond to unrealistic inputs. The W-SEPT project, for "WCET, Semantics, Precision and Traceability", has been carried out to study and exploit the influence of program semantics on the WCET estimation. This paper presents the results of this project : a semantic-aware WCET estimation workflow for high-level designed systems.
Cite as

Claire Maiza, Pascal Raymond, Catherine Parent-Vigouroux, Armelle Bonenfant, Fabienne Carrier, Hugues Cassé, Philippe Cuenot, Denis Claraz, Nicolas Halbwachs, Erwan Jahier, Hanbing Li, Marianne de Michiel, Vincent Mussot, Isabelle Puaut, Christine Rochange, Erven Rohou, Jordy Ruiz, Pascal Sotin, and Wei-Tsun Sun. The W-SEPT Project: Towards Semantic-Aware WCET Estimation. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{maiza_et_al:OASIcs.WCET.2017.9,
  author =	{Maiza, Claire and Raymond, Pascal and Parent-Vigouroux, Catherine and Bonenfant, Armelle and Carrier, Fabienne and Cass\'{e}, Hugues and Cuenot, Philippe and Claraz, Denis and Halbwachs, Nicolas and Jahier, Erwan and Li, Hanbing and de Michiel, Marianne and Mussot, Vincent and Puaut, Isabelle and Rochange, Christine and Rohou, Erven and Ruiz, Jordy and Sotin, Pascal and Sun, Wei-Tsun},
  title =	{{The W-SEPT Project: Towards Semantic-Aware WCET Estimation}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  pages =	{9:1--9:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-057-6},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{57},
  editor =	{Reineke, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2017.9},
  URN =		{urn:nbn:de:0030-drops-73097},
  doi =		{10.4230/OASIcs.WCET.2017.9},
  annote =	{Keywords: Worst-case execution time analysis, Static analysis, Program analysis}
}
Document
DOI: 10.4230/DagRep.5.3.84
Mixed Criticality on Multicore/Manycore Platforms (Dagstuhl Seminar 15121)

Authors: Sanjoy K. Baruah, Liliana Cucu-Grosjean, Roabert I. Davis, and Claire Maiza

Published in: Dagstuhl Reports, Volume 5, Issue 3 (2015)

Abstract
This report provides an overview of the discussions, the program and the outcomes of the first Dagstuhl Seminar on Mixed Criticality on multicore/Manycore Platforms. The seminar brought together researchers working on challenges related to executing mixed criticality real-time applications on multicore and manycore architectures with the main purpose of promoting a closer interaction between the sub-communities involved in real-time scheduling, real-time operating systems / runtime environments, and timing analysis as well as interaction with specialists in hardware architectures.
Cite as

Sanjoy K. Baruah, Liliana Cucu-Grosjean, Roabert I. Davis, and Claire Maiza. Mixed Criticality on Multicore/Manycore Platforms (Dagstuhl Seminar 15121). In Dagstuhl Reports, Volume 5, Issue 3, pp. 84-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{baruah_et_al:DagRep.5.3.84,
  author =	{Baruah, Sanjoy K. and Cucu-Grosjean, Liliana and Davis, Roabert I. and Maiza, Claire},
  title =	{{Mixed Criticality on Multicore/Manycore Platforms (Dagstuhl Seminar 15121)}},
  pages =	{84--142},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{3},
  editor =	{Baruah, Sanjoy K. and Cucu-Grosjean, Liliana and Davis, Roabert I. and Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.3.84},
  URN =		{urn:nbn:de:0030-drops-52707},
  doi =		{10.4230/DagRep.5.3.84},
  annote =	{Keywords: Mixed-Criticality, Real-time systems, Multicore/Manycore Platforms, fixed priority; probabilistic scheduling, varying-speed processors model combination}
}
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-dev.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
Complete Volume
DOI: 10.4230/OASIcs.WCET.2013
OASIcs, Volume 30, WCET'13, Complete Volume

Authors: Claire Maiza

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
OASIcs, Volume 30, WCET'13, Complete Volume
Cite as

13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{maiza:OASIcs.WCET.2013,
  title =	{{OASIcs, Volume 30, WCET'13, Complete Volume}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013},
  URN =		{urn:nbn:de:0030-drops-41333},
  doi =		{10.4230/OASIcs.WCET.2013},
  annote =	{Keywords: Performance Analysis and Design Aids, Real-time and embedded systems, Software/Program Verification}
}
Document
Front Matter
DOI: 10.4230/OASIcs.WCET.2013.i
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Claire Maiza

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

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

13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. i-x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{maiza:OASIcs.WCET.2013.i,
  author =	{Maiza, Claire},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{i--x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.i},
  URN =		{urn:nbn:de:0030-drops-41162},
  doi =		{10.4230/OASIcs.WCET.2013.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.1
Evaluation of resource arbitration methods for multi-core real-time systems

Authors: Timon Kelter, Tim Harde, Peter Marwedel, and Heiko Falk

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
Multi-core systems have become prevalent in the last years, because of their favorable properties in terms of energy consumption, computing power and design complexity. First attempts have been made to devise WCET analyses for multi-core processors, which have to deal with the problem that the cores may experience interferences during accesses to shared resources. To limit these interferences, the vast amount of previous work is proposing a strict TDMA (time division multiple access) schedule for arbitrating shared resources. Though this type of arbitration yields a high predictability, this advantage is paid for with a poor resource utilization. In this work, we compare different arbitration methods with respect to their predictability and average case performance. We show how known WCET analysis techniques can be extended to work with the presented arbitration strategies and perform an evaluation of the resulting ACETs and WCETs on an extensive set of realworld benchmarks. Results show that there are cases when TDMA is not the best strategy, especially when predictability and performance are equally important.
Cite as

Timon Kelter, Tim Harde, Peter Marwedel, and Heiko Falk. Evaluation of resource arbitration methods for multi-core real-time systems. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{kelter_et_al:OASIcs.WCET.2013.1,
  author =	{Kelter, Timon and Harde, Tim and Marwedel, Peter and Falk, Heiko},
  title =	{{Evaluation of resource arbitration methods for multi-core real-time systems}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{1--10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.1},
  URN =		{urn:nbn:de:0030-drops-41173},
  doi =		{10.4230/OASIcs.WCET.2013.1},
  annote =	{Keywords: WCET analysis, multi-core, arbitration, shared resources}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.11
Automatic WCET Analysis of Real-Time Parallel Applications

Authors: Haluk Ozaktas, Christine Rochange, and Pascal Sainrat

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
Tomorrow's real-time embedded systems will be built upon multicore architectures. This raises two challenges. First, shared resources should be arbitrated in such a way that the WCET of independent threads running concurrently can be computed: in this paper, we assume that timepredictable multicore architectures are available. The second challenge is to develop software that achieves a high level of performance without impairing timing predictability. We investigate parallel software based on the POSIX threads standard and we show how the WCET of a parallel program can be analysed. We report experimental results obtained for typical parallel programs with an extended version of the OTAWA toolset.
Cite as

Haluk Ozaktas, Christine Rochange, and Pascal Sainrat. Automatic WCET Analysis of Real-Time Parallel Applications. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 11-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{ozaktas_et_al:OASIcs.WCET.2013.11,
  author =	{Ozaktas, Haluk and Rochange, Christine and Sainrat, Pascal},
  title =	{{Automatic WCET Analysis of Real-Time Parallel Applications}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{11--20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.11},
  URN =		{urn:nbn:de:0030-drops-41186},
  doi =		{10.4230/OASIcs.WCET.2013.11},
  annote =	{Keywords: WCET analysis, parallel programming, thread synchronisation}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.21
Integrated Worst-Case Execution Time Estimation of Multicore Applications

Authors: Dumitru Potop-Butucaru and Isabelle Puaut

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
Worst-case execution time (WCET) analysis has reached a high level of precision in the analysis of sequential programs executing on single-cores. In this paper we extend a state-of-the-art WCET analysis technique to compute tight WCETs estimates of parallel applications running on multicores. The proposed technique is termed integrated because it considers jointly the sequential code regions running on the cores and the communications between them. This allows to capture the hardware effects across code regions assigned to the same core, which significantly improves analysis precision. We demonstrate that our analysis produces tighter execution time bounds than classical techniques which first determine the WCET of sequential code regions and then compute the global response time by integrating communication costs. Comparison is done on two embedded control applications, where the gain is of 21% on average.
Cite as

Dumitru Potop-Butucaru and Isabelle Puaut. Integrated Worst-Case Execution Time Estimation of Multicore Applications. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 21-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{potopbutucaru_et_al:OASIcs.WCET.2013.21,
  author =	{Potop-Butucaru, Dumitru and Puaut, Isabelle},
  title =	{{Integrated Worst-Case Execution Time Estimation of Multicore Applications}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{21--31},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.21},
  URN =		{urn:nbn:de:0030-drops-41193},
  doi =		{10.4230/OASIcs.WCET.2013.21},
  annote =	{Keywords: WCET estimation, multicore architectures, parallel programming}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.32
Program Semantics in Model-Based WCET Analysis: A State of the Art Perspective

Authors: Mihail Asavoae, Claire Maiza, and Pascal Raymond

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
Advanced design techniques of safety-critical applications use specialized development model based methods. Under this setting, the application exists at several levels of description, as the result of a sequence of transformations. On the positive side, the application is developed in a systematic way, while on the negative side, its high-level semantics may be obfuscated when represented at the lower levels. The application should provide certain functional and non-functional guarantees. When the application is a hard real-time program, such guarantees could be deadlines, thus making the computation of worst-case execution time (WCET) bounds mandatory. This paper overviews, in the context of WCET analysis, what are the existing techniques to extract, express and exploit the program semantics along the model-based development workflow.
Cite as

Mihail Asavoae, Claire Maiza, and Pascal Raymond. Program Semantics in Model-Based WCET Analysis: A State of the Art Perspective. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 32-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{asavoae_et_al:OASIcs.WCET.2013.32,
  author =	{Asavoae, Mihail and Maiza, Claire and Raymond, Pascal},
  title =	{{Program Semantics in Model-Based WCET Analysis: A State of the Art Perspective}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{32--41},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.32},
  URN =		{urn:nbn:de:0030-drops-41209},
  doi =		{10.4230/OASIcs.WCET.2013.32},
  annote =	{Keywords: survey, WCET analysis, program semantics, model-based design, infeasible paths}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.42
Multi-architecture Value Analysis for Machine Code

Authors: Hugues Cassé, Florian Birée, and Pascal Sainrat

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
Safety verification of critical real-time embedded systems requires Worst Case Execution Time information (WCET). Among the existing approaches to estimate the WCET, static analysis at the machine code level has proven to get safe results. A lot of different architectures are used in real-time systems but no generic solution provides the ability to perform static analysis of values handled by machine instructions. Nonetheless, results of such analyses are worth to improve the precision of other analyzes like data cache, indirect branches, etc. This paper proposes a semantic language aimed at expressing semantics of machine instructions whatever the underlying instruction set is. This ensures abstraction and portability of the value analysis or any analysis based on the semantic expression of the instructions. As a proof of concept, we adapted and refined an existing analysis representing values as Circular-Linear Progression (CLP), that is, as a sparse integer interval effective to model pointers. In addition, we show how our semantic instructions allow to build back conditions of loop in order to refine the CLP values and improve the precision of the analysis.Both contributions have been implemented in our framework, OTAWA, and experimented on the Malärdalen benchmark to desmonstrate the effectiveness of the approach.
Cite as

Hugues Cassé, Florian Birée, and Pascal Sainrat. Multi-architecture Value Analysis for Machine Code. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 42-52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{casse_et_al:OASIcs.WCET.2013.42,
  author =	{Cass\'{e}, Hugues and Bir\'{e}e, Florian and Sainrat, Pascal},
  title =	{{Multi-architecture Value Analysis for Machine Code}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{42--52},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.42},
  URN =		{urn:nbn:de:0030-drops-41211},
  doi =		{10.4230/OASIcs.WCET.2013.42},
  annote =	{Keywords: machine code, static analysis, value analysis, semantics}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.53
The Auspicious Couple: Symbolic Execution and WCET Analysis

Authors: Armin Biere, Jens Knoop, Laura Kovács, and Jakob Zwirchmayr

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
We have recently shown that symbolic execution together with the implicit path enumeration technique can successfully be applied in the Worst-Case Execution Time (WCET) analysis of programs. Symbolic execution offers a precise framework for program analysis and tracks complex program properties by analyzing single program paths in isolation. This path-wise program exploration of symbolic execution is, however, computationally expensive, which often prevents full symbolic analysis of larger applications: the number of paths in a program increases exponentially with the number of conditionals, a situation denoted as the path explosion problem. Therefore, for applying symbolic execution in the timing analysis of programs, we propose to use WCET analysis as a guidance for symbolic execution in order to avoid full symbolic coverage of the program. By focusing only on paths or program fragments that are relevant for WCET analysis, we keep the computational costs of symbolic execution low. Our WCET analysis also profits from the precise results derived via symbolic execution. In this article we describe how use-cases of symbolic execution are materialized in the r-TuBound toolchain and present new applications of WCET-guided symbolic execution for WCET analysis. The new applications of selective symbolic execution are based on reducing the effort of symbolic analysis by focusing only on relevant program fragments. By using partial symbolic program coverage obtained by selective symbolic execution, we improve the WCET analysis and keep the effort for symbolic execution low.
Cite as

Armin Biere, Jens Knoop, Laura Kovács, and Jakob Zwirchmayr. The Auspicious Couple: Symbolic Execution and WCET Analysis. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 53-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{biere_et_al:OASIcs.WCET.2013.53,
  author =	{Biere, Armin and Knoop, Jens and Kov\'{a}cs, Laura and Zwirchmayr, Jakob},
  title =	{{The Auspicious Couple: Symbolic Execution and WCET Analysis}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{53--63},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.53},
  URN =		{urn:nbn:de:0030-drops-41225},
  doi =		{10.4230/OASIcs.WCET.2013.53},
  annote =	{Keywords: WCET analysis, Symbolic execution, WCET refinement, Flow Facts}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.64
Upper-bounding Program Execution Time with Extreme Value Theory

Authors: Francisco J. Cazorla, Tullio Vardanega, Eduardo Quiñones, and Jaume Abella

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
In this paper we discuss the limitations of and the precautions to account for when using Extreme Value Theory (EVT) to compute upper bounds to the execution time of programs. We analyse the requirements placed by EVT on the observations to be made of the events of interest, and the conditions that render safe the computations of execution time upper bounds. We also study the requirements that a recent EVT-based timing analysis technique, Measurement-Based Probabilistic Timing Analysis (MBPTA), introduces, besides those imposed by EVT, on the computing system under analysis to increase the trustworthiness of the upper bounds that it computes.
Cite as

Francisco J. Cazorla, Tullio Vardanega, Eduardo Quiñones, and Jaume Abella. Upper-bounding Program Execution Time with Extreme Value Theory. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 64-76, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{cazorla_et_al:OASIcs.WCET.2013.64,
  author =	{Cazorla, Francisco J. and Vardanega, Tullio and Qui\~{n}ones, Eduardo and Abella, Jaume},
  title =	{{Upper-bounding Program Execution Time with Extreme Value Theory}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{64--76},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.64},
  URN =		{urn:nbn:de:0030-drops-41232},
  doi =		{10.4230/OASIcs.WCET.2013.64},
  annote =	{Keywords: WCET, Extreme Value Theory, Probabilistic, Deterministic}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.77
PRADA: Predictable Allocations by Deferred Actions

Authors: Florian Haupenthal and Jörg Herter

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
Modern hard real-time systems still employ static memory management. However, dynamic storage allocation (DSA) can improve the flexibility and readability of programs as well as drastically shorten their development times. But allocators introduce unpredictability that makes deriving tight bounds on an application's worst-case execution time even more challenging. Especially their statically unpredictable influence on the cache, paired with zero knowledge about the cache set mapping of dynamically allocated objects leads to prohibitively large overestimations of execution times when dynamic memory allocation is employed. Recently, a cache-aware memory allocator, called CAMA, was proposed that gives strong guarantees about its cache influence and the cache set mapping of allocated objects. CAMA itself is rather complex due to its cache-aware implementations of split and merge operations. This paper proposes PRADA, a lighter but less general dynamic memory allocator with equally strong guarantees about its influence on the cache. We compare the memory consumption of PRADA and CAMA for a small set of real-time applications as well as synthetical (de-) allocation sequences to investigate whether a simpler approach to cache awareness is still sufficient for the current generation of real-time applications.
Cite as

Florian Haupenthal and Jörg Herter. PRADA: Predictable Allocations by Deferred Actions. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 77-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{haupenthal_et_al:OASIcs.WCET.2013.77,
  author =	{Haupenthal, Florian and Herter, J\"{o}rg},
  title =	{{PRADA: Predictable Allocations by Deferred Actions}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{77--86},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.77},
  URN =		{urn:nbn:de:0030-drops-41243},
  doi =		{10.4230/OASIcs.WCET.2013.77},
  annote =	{Keywords: Dynamic Memory Allocation, Worst-Case Execution-Time, Cache Predictability}
}
  • Refine by Author
  • 7 Maiza, Claire
  • 3 Raymond, Pascal
  • 3 Rochange, Christine
  • 2 Abella, Jaume
  • 2 Asavoae, Mihail
  • Show More...

  • Refine by Classification
  • 1 Software and its engineering → Real-time systems software

  • Refine by Keyword
  • 5 WCET analysis
  • 2 Real-time systems
  • 2 WCET
  • 2 parallel programming
  • 2 static analysis
  • Show More...

  • Refine by Type
  • 16 document
  • 1 volume

  • Refine by Publication Year
  • 13 2013
  • 2 2015
  • 1 2017
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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