Search Results

Documents authored by Puaut, Isabelle

Document
DOI: 10.4230/OASIcs.WCET.2024.1
WORTEX: Worst-Case Execution Time and Energy Estimation in Low-Power Microprocessors Using Explainable ML

Authors: Hugo Reymond, Abderaouf Nassim Amalou, and Isabelle Puaut

Published in: OASIcs, Volume 121, 22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024)

Abstract
Real-time and energy-constrained systems heavily rely on estimates of the worst-case execution time (WCET) and worst-case energy consumption (WCEC) of code snippets to ensure trustworthy operation. Designing architecture-specific analytical models for time and energy is often challenging and time-consuming. In situations where analytical models are unavailable or incomplete, machine learning (ML) techniques emerge as a promising solution to build WCEC/WCET models. This paper introduces WORTEX, a toolkit for WCEC/WCET estimation of basic blocks based on ML techniques. To ensure the real-world applicability of its models, WORTEX extracts large datasets of basic blocks from real programs and precisely measures their energy consumption/execution time on the physical target platform. The dataset is used to train various WCEC/WCET models using different ML techniques. Experimental results on simple and time-predictable hardware show that even the most basic ML techniques provide accurate results, that never underestimate actual values. We also discuss the use of explainability techniques to gain trustworthiness for the models.
Cite as

Hugo Reymond, Abderaouf Nassim Amalou, and Isabelle Puaut. WORTEX: Worst-Case Execution Time and Energy Estimation in Low-Power Microprocessors Using Explainable ML. In 22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024). Open Access Series in Informatics (OASIcs), Volume 121, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{reymond_et_al:OASIcs.WCET.2024.1,
  author =	{Reymond, Hugo and Amalou, Abderaouf Nassim and Puaut, Isabelle},
  title =	{{WORTEX: Worst-Case Execution Time and Energy Estimation in Low-Power Microprocessors Using Explainable ML}},
  booktitle =	{22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024)},
  pages =	{1:1--1:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-346-1},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{121},
  editor =	{Carle, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2024.1},
  URN =		{urn:nbn:de:0030-drops-204691},
  doi =		{10.4230/OASIcs.WCET.2024.1},
  annote =	{Keywords: Worst-Case Execution Time (WCET), Worst-Case Energy Consumption (WCEC), Machine Learning, Explainable ML models}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.WCET.2024.7
Machine Learning for Timing Analysis: The Good, the Bad and the Ugly (Invited Talk)

Authors: Isabelle Puaut

Published in: OASIcs, Volume 121, 22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024)

Abstract
The microarchitecture of processors is becoming increasingly complex and less documented, making the design of timing models for WCET calculation increasingly complicated, if not impossible. We have recently experimented with the use of machine learning techniques (ML) to predict the WCET of basic blocks [Amalou et al., 2021; Abderaouf N. Amalou et al., 2022; Amalou et al., 2023; Abderaouf Nassim Amalou, 2023; Abderaouf Nassim Amalou et al., 2024]. Predicted WCETs can then be integrated into static WCET calculation tools, resulting in a hybrid WCET calculation. In this keynote, we present our experience using ML for WCET calculation, across a range of architectures, from very simple ones (MSP430, Cortex M4) to more complex architectures. Rather than presenting only what worked, we also discuss in this keynote the bad, and even very bad, surprises encountered during the process, and how we overcame (most of) them.
Cite as

Isabelle Puaut. Machine Learning for Timing Analysis: The Good, the Bad and the Ugly (Invited Talk). In 22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024). Open Access Series in Informatics (OASIcs), Volume 121, p. 7:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{puaut:OASIcs.WCET.2024.7,
  author =	{Puaut, Isabelle},
  title =	{{Machine Learning for Timing Analysis: The Good, the Bad and the Ugly}},
  booktitle =	{22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024)},
  pages =	{7:1--7:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-346-1},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{121},
  editor =	{Carle, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2024.7},
  URN =		{urn:nbn:de:0030-drops-204753},
  doi =		{10.4230/OASIcs.WCET.2024.7},
  annote =	{Keywords: Worst-Case Execution Time (WCET) estimation, Machine Learning, Explainable ML models}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2023.7
CAWET: Context-Aware Worst-Case Execution Time Estimation Using Transformers

Authors: Abderaouf N Amalou, Elisa Fromont, and Isabelle Puaut

Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

Abstract
This paper presents CAWET, a hybrid worst-case program timing estimation technique. CAWET identifies the longest execution path using static techniques, whereas the worst-case execution time (WCET) of basic blocks is predicted using an advanced language processing technique called Transformer-XL. By employing Transformers-XL in CAWET, the execution context formed by previously executed basic blocks is taken into account, allowing for consideration of the micro-architecture of the processor pipeline without explicit modeling. Through a series of experiments on the TacleBench benchmarks, using different target processors (Arm Cortex M4, M7, and A53), our method is demonstrated to never underestimate WCETs and is shown to be less pessimistic than its competitors.
Cite as

Abderaouf N Amalou, Elisa Fromont, and Isabelle Puaut. CAWET: Context-Aware Worst-Case Execution Time Estimation Using Transformers. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{amalou_et_al:LIPIcs.ECRTS.2023.7,
  author =	{Amalou, Abderaouf N and Fromont, Elisa and Puaut, Isabelle},
  title =	{{CAWET: Context-Aware Worst-Case Execution Time Estimation Using Transformers}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.7},
  URN =		{urn:nbn:de:0030-drops-180367},
  doi =		{10.4230/LIPIcs.ECRTS.2023.7},
  annote =	{Keywords: Worst-case execution time, machine learning, transformers, hybrid technique}
}
Document
DOI: 10.4230/OASIcs.WCET.2022.1
StAMP: Static Analysis of Memory Access Profiles for Real-Time Tasks

Authors: Théo Degioanni and Isabelle Puaut

Published in: OASIcs, Volume 103, 20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022)

Abstract
Accesses to shared resources in multi-core systems raise predictability issues. The delay in accessing a resource for a task executing on a core depends on concurrent resource sharing from tasks executing on the other cores. In this paper, we present StAMP, a compiler technique that splits the code of tasks into a sequence of code intervals intervals, each with a distinct worst-case memory access profile. The intervals identified by StAMP can serve as inputs to scheduling techniques for a tight calculation of worst-case delays of memory accesses. The provided information can also ease the design of mechanisms that avoid and/or control interference between tasks at run-time. An important feature of StAMP compared to related work lies in its ability to link back time intervals to unique locations in the code of tasks, allowing easy implementation of elaborate run-time decisions related to interference management.
Cite as

Théo Degioanni and Isabelle Puaut. StAMP: Static Analysis of Memory Access Profiles for Real-Time Tasks. In 20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022). Open Access Series in Informatics (OASIcs), Volume 103, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{degioanni_et_al:OASIcs.WCET.2022.1,
  author =	{Degioanni, Th\'{e}o and Puaut, Isabelle},
  title =	{{StAMP: Static Analysis of Memory Access Profiles for Real-Time Tasks}},
  booktitle =	{20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022)},
  pages =	{1:1--1:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-244-0},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{103},
  editor =	{Ballabriga, Cl\'{e}ment},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2022.1},
  URN =		{urn:nbn:de:0030-drops-166231},
  doi =		{10.4230/OASIcs.WCET.2022.1},
  annote =	{Keywords: Worst-Case Execution Time Estimation, Static Analysis, Multicore, Interference, Implicit Path Enumeration Technique}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2022.18
RT-DFI: Optimizing Data-Flow Integrity for Real-Time Systems

Authors: Nicolas Bellec, Guillaume Hiet, Simon Rokicki, Frederic Tronel, and Isabelle Puaut

Published in: LIPIcs, Volume 231, 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
The emergence of Real-Time Systems with increased connections to their environment has led to a greater demand in security for these systems. Memory corruption attacks, which modify the memory to trigger unexpected executions, are a significant threat against applications written in low-level languages. Data-Flow Integrity (DFI) is a protection that verifies that only a trusted source has written any loaded data. The overhead of such a security mechanism remains a major issue that limits its adoption. This article presents RT-DFI, a new approach that optimizes Data-Flow Integrity to reduce its overhead on the Worst-Case Execution Time. We model the number and order of the checks and use an Integer Linear Programming solver to optimize the protection on the Worst-Case Execution Path. Our approach protects the program against many memory-corruption attacks, including Return-Oriented Programming and Data-Only attacks. Moreover, our experimental results show that our optimization reduces the overhead by 7% on average compared to a state-of-the-art implementation.
Cite as

Nicolas Bellec, Guillaume Hiet, Simon Rokicki, Frederic Tronel, and Isabelle Puaut. RT-DFI: Optimizing Data-Flow Integrity for Real-Time Systems. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 18:1-18:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bellec_et_al:LIPIcs.ECRTS.2022.18,
  author =	{Bellec, Nicolas and Hiet, Guillaume and Rokicki, Simon and Tronel, Frederic and Puaut, Isabelle},
  title =	{{RT-DFI: Optimizing Data-Flow Integrity for Real-Time Systems}},
  booktitle =	{34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
  pages =	{18:1--18:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-239-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{231},
  editor =	{Maggio, Martina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.18},
  URN =		{urn:nbn:de:0030-drops-163351},
  doi =		{10.4230/LIPIcs.ECRTS.2022.18},
  annote =	{Keywords: Real-time system, Software security, Data-flow integrity, Worst-case execution time}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2020.8
Attack Detection Through Monitoring of Timing Deviations in Embedded Real-Time Systems

Authors: Nicolas Bellec, Simon Rokicki, and Isabelle Puaut

Published in: LIPIcs, Volume 165, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)

Abstract
Real-time embedded systems (RTES) are required to interact more and more with their environment, thereby increasing their attack surface. Recent security breaches on car brakes and other critical components have already proven the feasibility of attacks on RTES. Such attacks may change the control-flow of the programs, which may lead to violations of the system’s timing constraints. In this paper, we present a technique to detect attacks in RTES based on timing information. Our technique, designed for single-core processors, is based on a monitor implemented in hardware to preserve the predictability of instrumented programs. The monitor uses timing information (Worst-Case Execution Time - WCET) of code regions to detect attacks. The proposed technique guarantees that attacks that delay the run-time of any region beyond its WCET are detected. Since the number of regions in programs impacts the memory resources consumed by the hardware monitor, our method includes a region selection algorithm that limits the amount of memory consumed by the monitor. An implementation of the hardware monitor and its simulation demonstrates the practicality of our approach. In particular, an experimental study evaluates the attack detection latency.
Cite as

Nicolas Bellec, Simon Rokicki, and Isabelle Puaut. Attack Detection Through Monitoring of Timing Deviations in Embedded Real-Time Systems. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bellec_et_al:LIPIcs.ECRTS.2020.8,
  author =	{Bellec, Nicolas and Rokicki, Simon and Puaut, Isabelle},
  title =	{{Attack Detection Through Monitoring of Timing Deviations in Embedded Real-Time Systems}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{V\"{o}lp, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.8},
  URN =		{urn:nbn:de:0030-drops-123719},
  doi =		{10.4230/LIPIcs.ECRTS.2020.8},
  annote =	{Keywords: Real-time systems, security, attack detection, control flow hijacking, WCET estimation, hardware monitoring}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2019.17
Impact of DM-LRU on WCET: A Static Analysis Approach

Authors: Renato Mancuso, Heechul Yun, and Isabelle Puaut

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
Cache memories in modern embedded processors are known to improve average memory access performance. Unfortunately, they are also known to represent a major source of unpredictability for hard real-time workload. One of the main limitations of typical caches is that content selection and replacement is entirely performed in hardware. As such, it is hard to control the cache behavior in software to favor caching of blocks that are known to have an impact on an application’s worst-case execution time (WCET). In this paper, we consider a cache replacement policy, namely DM-LRU, that allows system designers to prioritize caching of memory blocks that are known to have an important impact on an application’s WCET. Considering a single-core, single-level cache hierarchy, we describe an abstract interpretation-based timing analysis for DM-LRU. We implement the proposed analysis in a self-contained toolkit and study its qualitative properties on a set of representative benchmarks. Apart from being useful to compute the WCET when DM-LRU or similar policies are used, the proposed analysis can allow designers to perform WCET impact-aware selection of content to be retained in cache.
Cite as

Renato Mancuso, Heechul Yun, and Isabelle Puaut. Impact of DM-LRU on WCET: A Static Analysis Approach. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mancuso_et_al:LIPIcs.ECRTS.2019.17,
  author =	{Mancuso, Renato and Yun, Heechul and Puaut, Isabelle},
  title =	{{Impact of DM-LRU on WCET: A Static Analysis Approach}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.17},
  URN =		{urn:nbn:de:0030-drops-107546},
  doi =		{10.4230/LIPIcs.ECRTS.2019.17},
  annote =	{Keywords: real-time, static cache analysis, abstract interpretation, LRU, deterministic memory, static cache locking, dynamic cache locking, cache profiling, WCET analysis}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2019.25
Hiding Communication Delays in Contention-Free Execution for SPM-Based Multi-Core Architectures

Authors: Benjamin Rouxel, Stefanos Skalistis, Steven Derrien, and Isabelle Puaut

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
Multi-core systems using ScratchPad Memories (SPMs) are attractive architectures for executing time-critical embedded applications, because they provide both predictability and performance. In this paper, we propose a scheduling technique that jointly selects SPM contents off-line, in such a way that the cost of SPM loading/unloading is hidden. Communications are fragmented to augment hiding possibilities. Experimental results show the effectiveness of the proposed technique on streaming applications and synthetic task-graphs. The overlapping of communications with computations allows the length of generated schedules to be reduced by 4% on average on streaming applications, with a maximum of 16%, and by 8% on average for synthetic task graphs. We further show on a case study that generated schedules can be implemented with low overhead on a predictable multi-core architecture (Kalray MPPA).
Cite as

Benjamin Rouxel, Stefanos Skalistis, Steven Derrien, and Isabelle Puaut. Hiding Communication Delays in Contention-Free Execution for SPM-Based Multi-Core Architectures. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rouxel_et_al:LIPIcs.ECRTS.2019.25,
  author =	{Rouxel, Benjamin and Skalistis, Stefanos and Derrien, Steven and Puaut, Isabelle},
  title =	{{Hiding Communication Delays in Contention-Free Execution for SPM-Based Multi-Core Architectures}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{25:1--25:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.25},
  URN =		{urn:nbn:de:0030-drops-107626},
  doi =		{10.4230/LIPIcs.ECRTS.2019.25},
  annote =	{Keywords: Real-time Systems, Contention-Free Scheduling, SPM multi-core architecture}
}
Document
DOI: 10.4230/OASIcs.WCET.2018.9
Fine-Grain Iterative Compilation for WCET Estimation

Authors: Isabelle Puaut, Mickaël Dardaillon, Christoph Cullmann, Gernot Gebhard, and Steven Derrien

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

Abstract
Compiler optimizations, although reducing the execution times of programs, raise issues in static WCET estimation techniques and tools. Flow facts, such as loop bounds, may not be automatically found by static WCET analysis tools after aggressive code optimizations. In this paper, we explore the use of iterative compilation (WCET-directed program optimization to explore the optimization space), with the objective to (i) allow flow facts to be automatically found and (ii) select optimizations that result in the lowest WCET estimates. We also explore to which extent code outlining helps, by allowing the selection of different optimization options for different code snippets of the application.
Cite as

Isabelle Puaut, Mickaël Dardaillon, Christoph Cullmann, Gernot Gebhard, and Steven Derrien. Fine-Grain Iterative Compilation for WCET Estimation. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{puaut_et_al:OASIcs.WCET.2018.9,
  author =	{Puaut, Isabelle and Dardaillon, Micka\"{e}l and Cullmann, Christoph and Gebhard, Gernot and Derrien, Steven},
  title =	{{Fine-Grain Iterative Compilation for WCET Estimation}},
  booktitle =	{18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
  pages =	{9:1--9:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-073-6},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{63},
  editor =	{Brandner, Florian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.9},
  URN =		{urn:nbn:de:0030-drops-97556},
  doi =		{10.4230/OASIcs.WCET.2018.9},
  annote =	{Keywords: Worst-Case Execution Time Estimation, Compiler optimizations, Iterative Compilation, Flow fact extraction, Outlining}
}
Document
DOI: 10.4230/OASIcs.WCET.2017.1
STR2RTS: Refactored StreamIT Benchmarks into Statically Analyzable Parallel Benchmarks for WCET Estimation & Real-Time Scheduling

Authors: Benjamin Rouxel and Isabelle Puaut

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

Abstract
We all had quite a time to find non-proprietary architecture-independent exploitable parallel benchmarks for Worst-Case Execution Time (WCET) estimation and real-time scheduling. However, there is no consensus on a parallel benchmark suite, when compared to the single-core era and the Mälardalen benchmark suite. This document bridges part of this gap, by presenting a collection of benchmarks with the following good properties: (i) easily analyzable by static WCET estimation tools (written in structured C language, in particular neither goto nor dynamic memory allocation, containing flow information such as loop bounds); (ii) independent from any particular run-time system (MPI, OpenMP) or real-time operating system. Each benchmark is composed of the C source code of its tasks, and an XML description describing the structure of the application (tasks and amount of data exchanged between them when applicable). Each benchmark can be integrated in a full end-to-end empirical method validation protocol on multi-core architecture. This proposed collection of benchmarks is derived from the well known StreamIT [Thies et al., Comp. Constr., 2002] benchmark suite and will be integrated in the TACleBench suite [Falk et al., WCET, 2016] in a near future. All these benchmarks are available at https://gitlab.inria.fr/brouxel/STR2RTS.
Cite as

Benjamin Rouxel and Isabelle Puaut. STR2RTS: Refactored StreamIT Benchmarks into Statically Analyzable Parallel Benchmarks for WCET Estimation & Real-Time Scheduling. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 1:1-1:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{rouxel_et_al:OASIcs.WCET.2017.1,
  author =	{Rouxel, Benjamin and Puaut, Isabelle},
  title =	{{STR2RTS: Refactored StreamIT Benchmarks into Statically Analyzable Parallel Benchmarks for WCET Estimation \& Real-Time Scheduling}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  pages =	{1:1--1:12},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2017.1},
  URN =		{urn:nbn:de:0030-drops-73047},
  doi =		{10.4230/OASIcs.WCET.2017.1},
  annote =	{Keywords: Parallel benchmarks, Tasks scheduling, Worst-Case Execution Time estimation}
}
Document
DOI: 10.4230/OASIcs.WCET.2017.8
The Heptane Static Worst-Case Execution Time Estimation Tool

Authors: Damien Hardy, Benjamin Rouxel, and Isabelle Puaut

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

Abstract
Estimation of worst-case execution times (WCETs) is required to validate the temporal behavior of hard real time systems. Heptane is an open-source software program that estimates upper bounds of execution times on MIPS and ARM v7 architectures, offered to the WCET estimation community to experiment new WCET estimation techniques. The software architecture of Heptane was designed to be as modular and extensible as possible to facilitate the integration of new approaches. This paper is devoted to a description of Heptane, and includes information on the analyses it implements, how to use it and extend it.
Cite as

Damien Hardy, Benjamin Rouxel, and Isabelle Puaut. The Heptane Static Worst-Case Execution Time Estimation Tool. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hardy_et_al:OASIcs.WCET.2017.8,
  author =	{Hardy, Damien and Rouxel, Benjamin and Puaut, Isabelle},
  title =	{{The Heptane Static Worst-Case Execution Time Estimation Tool}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  pages =	{8:1--8:12},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2017.8},
  URN =		{urn:nbn:de:0030-drops-73033},
  doi =		{10.4230/OASIcs.WCET.2017.8},
  annote =	{Keywords: Worst-Case Execution Time Estimation, Static Analysis, WCET Estimation Tool, Implicit Path Enumeration Technique}
}
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.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/LIPIcs.ECRTS.2017.14
Cache-Conscious Offline Real-Time Task Scheduling for Multi-Core Processors

Authors: Viet Anh Nguyen, Damien Hardy, and Isabelle Puaut

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)

Abstract
Most schedulability analysis techniques for multi-core architectures assume a single Worst-Case Execution Time (WCET) per task, which is valid in all execution conditions. This assumption is too pessimistic for parallel applications running on multi-core architectures with local instruction or data caches, for which the WCET of a task depends on the cache contents at the beginning of its execution, itself depending on the task that was executed before the task under study. In this paper, we propose two scheduling techniques for multi-core architectures equipped with local instruction and data caches. The two techniques schedule a parallel application modeled as a task graph, and generate a static partitioned non-preemptive schedule. We propose an optimal method, using an Integer Linear Programming (ILP) formulation, as well as a heuristic method based on list scheduling. Experimental results show that by taking into account the effect of private caches on tasks' WCETs, the length of generated schedules is significantly reduced as compared to schedules generated by cache-unaware scheduling methods. The observed schedule length reduction on streaming applications is 11% on average for the optimal method and 9% on average for the heuristic method.
Cite as

Viet Anh Nguyen, Damien Hardy, and Isabelle Puaut. Cache-Conscious Offline Real-Time Task Scheduling for Multi-Core Processors. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nguyen_et_al:LIPIcs.ECRTS.2017.14,
  author =	{Nguyen, Viet Anh and Hardy, Damien and Puaut, Isabelle},
  title =	{{Cache-Conscious Offline Real-Time Task Scheduling for Multi-Core Processors}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.14},
  URN =		{urn:nbn:de:0030-drops-71642},
  doi =		{10.4230/LIPIcs.ECRTS.2017.14},
  annote =	{Keywords: Real-time scheduling, Cache-conscious scheduling, Many-core architectures, ILP, Static list scheduling}
}
Document
DOI: 10.4230/OASIcs.WCET.2014.11
A Formally Verified WCET Estimation Tool

Authors: André Maroneze, Sandrine Blazy, David Pichardie, and Isabelle Puaut

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

Abstract
The application of formal methods in the development of safety-critical embedded software is recommended in order to provide strong guarantees about the absence of software errors. In this context, WCET estimation tools constitute an important element to be formally verified. We present a formally verified WCET estimation tool, integrated to the formally verified CompCert C compiler. Our tool comes with a machine-checked proof which ensures that its WCET estimates are safe. Our tool operates over C programs and is composed of two main parts, a loop bound estimation and an Implicit Path Enumeration Technique (IPET)-based WCET calculation method. We evaluated the precision of the WCET estimates on a reference benchmark and obtained results which are competitive with state-of-the-art WCET estimation techniques.
Cite as

André Maroneze, Sandrine Blazy, David Pichardie, and Isabelle Puaut. A Formally Verified WCET Estimation Tool. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 11-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{maroneze_et_al:OASIcs.WCET.2014.11,
  author =	{Maroneze, Andr\'{e} and Blazy, Sandrine and Pichardie, David and Puaut, Isabelle},
  title =	{{A Formally Verified WCET Estimation Tool}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{11--20},
  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.11},
  URN =		{urn:nbn:de:0030-drops-46003},
  doi =		{10.4230/OASIcs.WCET.2014.11},
  annote =	{Keywords: Formal Verification, CompCert C Compiler, WCET Estimation}
}
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.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.2009.2283
WCET Analysis of Multi-Level Set-Associative Data Caches

Authors: Benjamin Lesage, Damien Hardy, and Isabelle Puaut

Published in: OASIcs, Volume 10, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) (2009)

Abstract
Nowadays, the presence of cache hierarchies tends to be a common trend in processor architectures, even in hardware for real-time embedded systems. Caches are used to fill the gap between the processor and the main memory, reducing access times based on spatial and temporal locality properties of tasks. Cache hierarchies are going even further however at the price of increased complexity. In this paper, we present a safe static data cache analysis method for hierarchies of non-inclusive caches. Using this method, we show that considering the cache hierarchy in the context of data caches allows tighter estimates of the worst case execution time than when considering only the first cache level. We also present considerations about the update policy for data caches.
Cite as

Benjamin Lesage, Damien Hardy, and Isabelle Puaut. WCET Analysis of Multi-Level Set-Associative Data Caches. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{lesage_et_al:OASIcs.WCET.2009.2283,
  author =	{Lesage, Benjamin and Hardy, Damien and Puaut, Isabelle},
  title =	{{WCET Analysis of Multi-Level Set-Associative Data Caches}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2283},
  URN =		{urn:nbn:de:0030-drops-22837},
  doi =		{10.4230/OASIcs.WCET.2009.2283},
  annote =	{Keywords: WCET analysis, data cache, multi-level, set-associative}
}
Document
DOI: 10.4230/OASIcs.WCET.2005.808
Safe measurement-based WCET estimation

Authors: Jean-François Deverge and Isabelle Puaut

Published in: OASIcs, Volume 1, 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05) (2007)

Abstract
This paper explores the issues to be addressed to provide safe worst-case execution time (WCET) estimation methods based on measurements. We suggest to use structural testing for the exhaustive exploration of paths in a program. Since test data generation is in general too complex to be used in practice for most real-size programs, we propose to generate test data for program segments only, using program clustering. Moreover, to be able to combine execution time of program segments and to obtain the WCET of the whole program, we advocate the use of compiler techniques to reduce (ideally eliminate) the timing variability of program segments and to make the time of program segments independent from one another.
Cite as

Jean-François Deverge and Isabelle Puaut. Safe measurement-based WCET estimation. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 13-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{deverge_et_al:OASIcs.WCET.2005.808,
  author =	{Deverge, Jean-Fran\c{c}ois and Puaut, Isabelle},
  title =	{{Safe measurement-based WCET estimation}},
  booktitle =	{5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
  pages =	{13--16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-24-8},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{1},
  editor =	{Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.808},
  URN =		{urn:nbn:de:0030-drops-8089},
  doi =		{10.4230/OASIcs.WCET.2005.808},
  annote =	{Keywords: Real-Time, Timing Analysis, Test-Case generation, Processor Architecture}
}
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