14th International Workshop on Worst-Case Execution Time Analysis

Document

Complete Volume

DOI: 10.4230/OASIcs.WCET.2014

OASIcs, Volume 39, WCET'14, Complete Volume

Authors: Heiko Falk

Abstract

OASIcs, Volume 39, WCET'14, Complete Volume

Cite as

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

Copy BibTex To Clipboard

@Proceedings{falk:OASIcs.WCET.2014,
  title =	{{OASIcs, Volume 39, WCET'14, Complete Volume}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  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},
  URN =		{urn:nbn:de:0030-drops-46115},
  doi =		{10.4230/OASIcs.WCET.2014},
  annote =	{Keywords: Performance Analysis and Design Aids, Real-time and embedded systems, Software/Program Verification}
}

Document

Front Matter

DOI: 10.4230/OASIcs.WCET.2014.i

Frontmatter, Contents, Welcome, List of Authors, Committee

Authors: Heiko Falk

Abstract

Frontmatter, Contents, Welcome, List of Authors, Committee

Cite as

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

Copy BibTex To Clipboard

@InProceedings{falk:OASIcs.WCET.2014.i,
  author =	{Falk, Heiko},
  title =	{{Frontmatter, Contents, Welcome, List of Authors, Committee}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{i--xii},
  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.i},
  URN =		{urn:nbn:de:0030-drops-45980},
  doi =		{10.4230/OASIcs.WCET.2014.i},
  annote =	{Keywords: Frontmatter, Contents, Welcome, List of Authors, Committee}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.1

Principles for Value Annotation Languages

Authors: Björn Lisper

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

DOI: 10.4230/OASIcs.WCET.2014.11

A Formally Verified WCET Estimation Tool

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

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.2014.21

On the Sustainability of the Extreme Value Theory for WCET Estimation

Authors: Luca Santinelli, Jérôme Morio, Guillaume Dufour, and Damien Jacquemart

Abstract

Measurement-based approaches with extreme value worst-case estimations are beginning to be proficiently considered for timing analyses. In this paper, we intend to make more formal extreme value theory applicability to safe worst-case execution time estimations. We outline complexities and challenges behind extreme value theory assumptions and parameter tuning. Including the knowledge requirements, we are able to conclude about safety of the probabilistic worst-case execution estimations from the extreme value theory, and execution time measurements.

Cite as

Luca Santinelli, Jérôme Morio, Guillaume Dufour, and Damien Jacquemart. On the Sustainability of the Extreme Value Theory for WCET Estimation. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 21-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{santinelli_et_al:OASIcs.WCET.2014.21,
  author =	{Santinelli, Luca and Morio, J\'{e}r\^{o}me and Dufour, Guillaume and Jacquemart, Damien},
  title =	{{On the Sustainability of the Extreme Value Theory for WCET Estimation}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{21--30},
  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.21},
  URN =		{urn:nbn:de:0030-drops-46013},
  doi =		{10.4230/OASIcs.WCET.2014.21},
  annote =	{Keywords: Extreme Value Theory, Worst-Case Execution Time, Probabilistic Worst-Case Execution Time, Dependence, Stationarity}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.31

Contention in Multicore Hardware Shared Resources: Understanding of the State of the Art

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

Abstract

The real-time systems community has over the years devoted considerable attention to the impact on execution timing that arises from contention on access to hardware shared resources. The relevance of this problem has been accentuated with the arrival of multicore processors. From the state of the art on the subject, there appears to be considerable diversity in the understanding of the problem and in the "approach" to solve it. This sparseness makes it difficult for any reader to form a coherent picture of the problem and solution space. This paper draws a tentative taxonomy in which each known approach to the problem can be categorised based on its specific goals and assumptions.

Cite as

Gabriel Fernandez, Jaume Abella, Eduardo Quiñones, Christine Rochange, Tullio Vardanega, and Francisco J. Cazorla. Contention in Multicore Hardware Shared Resources: Understanding of the State of the Art. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 31-42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{fernandez_et_al:OASIcs.WCET.2014.31,
  author =	{Fernandez, Gabriel and Abella, Jaume and Qui\~{n}ones, Eduardo and Rochange, Christine and Vardanega, Tullio and Cazorla, Francisco J.},
  title =	{{Contention in Multicore Hardware Shared Resources: Understanding of the State of the Art}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{31--42},
  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.31},
  URN =		{urn:nbn:de:0030-drops-46027},
  doi =		{10.4230/OASIcs.WCET.2014.31},
  annote =	{Keywords: Contention, Multicores, WCET Analysis}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.43

On Static Timing Analysis of GPU Kernels

Authors: Vesa Hirvisalo

Abstract

We study static timing analysis of programs running on GPU accelerators. Such programs follow a data parallel programming model that allows massive parallelism on manycore processors. Data parallel programming and GPUs as accelerators have received wide use during the recent years. The timing analysis of programs running on single core machines is well known and applied also in practice. However for multicore and manycore machines, timing analysis presents a significant but yet not properly solved problem. In this paper, we present static timing analysis of GPU kernels based on a method that we call abstract CTA simulation. Cooperative Thread Arrays (CTA) are the basic execution structure that GPU devices use in their operation that proceeds in thread groups called warps. Abstract CTA simulation is based on static analysis of thread divergence in warps and their abstract scheduling.

Cite as

Vesa Hirvisalo. On Static Timing Analysis of GPU Kernels. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 43-52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{hirvisalo:OASIcs.WCET.2014.43,
  author =	{Hirvisalo, Vesa},
  title =	{{On Static Timing Analysis of GPU Kernels}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{43--52},
  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.43},
  URN =		{urn:nbn:de:0030-drops-46033},
  doi =		{10.4230/OASIcs.WCET.2014.43},
  annote =	{Keywords: Parallelism, WCET}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.53

A Time-Predictable Memory Network-on-Chip

Authors: Martin Schoeberl, David Vh Chong, Wolfgang Puffitsch, and Jens Sparsø

Abstract

To derive safe bounds on worst-case execution times (WCETs), all components of a computer system need to be time-predictable: the processor pipeline, the caches, the memory controller, and memory arbitration on a multicore processor. This paper presents a solution for time-predictable memory arbitration and access for chip-multiprocessors. The memory network-on-chip is organized as a tree with time-division multiplexing (TDM) of accesses to the shared memory. The TDM based arbitration completely decouples processor cores and allows WCET analysis of the memory accesses on individual cores without considering the tasks on the other cores. Furthermore, we perform local, distributed arbitration according to the global TDM schedule. This solution avoids a central arbiter and scales to a large number of processors.

Cite as

Martin Schoeberl, David Vh Chong, Wolfgang Puffitsch, and Jens Sparsø. A Time-Predictable Memory Network-on-Chip. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 53-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{schoeberl_et_al:OASIcs.WCET.2014.53,
  author =	{Schoeberl, Martin and Chong, David Vh and Puffitsch, Wolfgang and Spars{\o}, Jens},
  title =	{{A Time-Predictable Memory Network-on-Chip}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{53--62},
  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.53},
  URN =		{urn:nbn:de:0030-drops-46047},
  doi =		{10.4230/OASIcs.WCET.2014.53},
  annote =	{Keywords: Real-Time Systems, Time-predictable Computer Architecture, Network-on-Chip, Memory Arbitration}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.63

The Challenge of Time-Predictability in Modern Many-Core Architectures

Authors: Vincent Nélis, Patrick Meumeu Yomsi, Luís Miguel Pinho, José Carlos Fonseca, Marko Bertogna, Eduardo Quiñones, Roberto Vargas, and Andrea Marongiu

Abstract

The recent technological advancements and market trends are causing an interesting phenomenon towards the convergence of High-Performance Computing (HPC) and Embedded Computing (EC) domains. Many recent HPC applications require huge amounts of information to be processed within a bounded amount of time while EC systems are increasingly concerned with providing higher performance in real-time. The convergence of these two domains towards systems requiring both high performance and a predictable time-behavior challenges the capabilities of current hardware architectures. Fortunately, the advent of next-generation many-core embedded platforms has the chance of intercepting this converging need for predictability and high-performance, allowing HPC and EC applications to be executed on efficient and powerful heterogeneous architectures integrating general-purpose processors with many-core computing fabrics. However, addressing this mixed set of requirements is not without its own challenges and it is now of paramount importance to develop new techniques to exploit the massively parallel computation capabilities of many-core platforms in a predictable way.

Cite as

Vincent Nélis, Patrick Meumeu Yomsi, Luís Miguel Pinho, José Carlos Fonseca, Marko Bertogna, Eduardo Quiñones, Roberto Vargas, and Andrea Marongiu. The Challenge of Time-Predictability in Modern Many-Core Architectures. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 63-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{nelis_et_al:OASIcs.WCET.2014.63,
  author =	{N\'{e}lis, Vincent and Yomsi, Patrick Meumeu and Pinho, Lu{\'\i}s Miguel and Fonseca, Jos\'{e} Carlos and Bertogna, Marko and Qui\~{n}ones, Eduardo and Vargas, Roberto and Marongiu, Andrea},
  title =	{{The Challenge of Time-Predictability in Modern Many-Core Architectures}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{63--72},
  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.63},
  URN =		{urn:nbn:de:0030-drops-46050},
  doi =		{10.4230/OASIcs.WCET.2014.63},
  annote =	{Keywords: Time-Predictability, Many-Cores, Multi-Cores, Timing Analysis}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.73

Scope-Based Method Cache Analysis

Authors: Benedikt Huber, Stefan Hepp, and Martin Schoeberl

Abstract

The quest for time-predictable systems has led to the exploration of new hardware architectures that simplify analysis and reasoning in the temporal domain, while still providing competitive performance. For the instruction memory, the method cache is a conceptually attractive solution, as it requests memory transfers at well-defined instructions only. In this article, we present a new cache analysis framework that generalizes and improves work on cache persistence analysis. The analysis demonstrates that a global view on the cache behavior permits the precise analyses of caches which are hard to analyze by inspecting cache state locally.

Cite as

Benedikt Huber, Stefan Hepp, and Martin Schoeberl. Scope-Based Method Cache Analysis. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 73-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{huber_et_al:OASIcs.WCET.2014.73,
  author =	{Huber, Benedikt and Hepp, Stefan and Schoeberl, Martin},
  title =	{{Scope-Based Method Cache Analysis}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{73--82},
  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.73},
  URN =		{urn:nbn:de:0030-drops-46066},
  doi =		{10.4230/OASIcs.WCET.2014.73},
  annote =	{Keywords: Real-Time Systems, Cache Analysis, Time-predictable Computer Architecture}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.83

Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis

Authors: Sahar Abbaspour, Alexander Jordan, and Florian Brandner

Abstract

The growing complexity of modern computer architectures increasingly complicates the prediction of the run-time behavior of software. For real-time systems, where a safe estimation of the program's worst-case execution time is needed, time-predictable computer architectures promise to resolve this problem. A stack cache, for instance, allows the compiler to efficiently cache a program's stack, while static analysis of its behavior remains easy. Likewise, its implementation requires little hardware overhead. This work introduces an optimization of the standard stack cache to avoid redundant spilling of the cache content to main memory, if the content was not modified in the meantime. At first sight, this appears to be an average-case optimization. Indeed, measurements show that the number of cache blocks spilled is reduced to about 17% and 30% in the mean, depending on the stack cache size. Furthermore, we show that lazy spilling can be analyzed with little extra effort, which benefits the worst-case spilling behavior that is relevant for a real-time system.

Cite as

Sahar Abbaspour, Alexander Jordan, and Florian Brandner. Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 83-92, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{abbaspour_et_al:OASIcs.WCET.2014.83,
  author =	{Abbaspour, Sahar and Jordan, Alexander and Brandner, Florian},
  title =	{{Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{83--92},
  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.83},
  URN =		{urn:nbn:de:0030-drops-46073},
  doi =		{10.4230/OASIcs.WCET.2014.83},
  annote =	{Keywords: Lazy Spilling, Stack Cache, Real-Time Systems, Program Analysis}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.93

Identifying Relevant Parameters to Improve WCET Analysis

Authors: Jakob Zwirchmayr, Pascal Sotin, Armelle Bonenfant, Denis Claraz, and Philippe Cuenot

Abstract

Highly-configurable systems usually depend on a large number of parameters imposed by both hardware and software configuration. Due to the pessimistic assumptions of WCET analysis, if left unspecified, they deteriorate the quality of WCET analysis. In such a case, supplying the WCET analyzer with additional information about parameters (a scenario), e.g. possible variable ranges or values, allows reducing WCET over-estimation, either by improving the estimate, or by validating the initial estimate for a specific configuration or mode of execution. Nevertheless, exhaustively specifying constraints on all parameters is usually infeasible and identifying relevant ones (i.e. those impacting the WCET) is difficult. To address this issue, we propose the branching statement analysis, which uses a source-based heuristic to compute branch weights and that aims at listing unbalanced conditionals that correspond to system parameters. The goal is to help system-experts identify and formulate concise scenarios about modes or configurations that have a positive impact on the quality of the WCET analysis.

Cite as

Jakob Zwirchmayr, Pascal Sotin, Armelle Bonenfant, Denis Claraz, and Philippe Cuenot. Identifying Relevant Parameters to Improve WCET Analysis. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 93-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{zwirchmayr_et_al:OASIcs.WCET.2014.93,
  author =	{Zwirchmayr, Jakob and Sotin, Pascal and Bonenfant, Armelle and Claraz, Denis and Cuenot, Philippe},
  title =	{{Identifying Relevant Parameters to Improve WCET Analysis}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{93--102},
  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.93},
  URN =		{urn:nbn:de:0030-drops-46085},
  doi =		{10.4230/OASIcs.WCET.2014.93},
  annote =	{Keywords: WCET Accuracy, Modes and Configuration, Flow Facts, Scenario Specification}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.103

Towards Automated Generation of Time-Predictable Code

Authors: Daniel Prokesch, Benedikt Huber, and Peter Puschner

Abstract

Knowledge of the worst-case execution time of software components is essential in safety-critical hard real-time systems. The analysis thereof is not trivial as the execution time depends on many factors, including the underlying hardware platform, the program structure, and the code produced by the compiler. Often, the execution time is variable and highly sensitive to the input data the program has to process. This paper presents a code transformation applicable in a compiler backend that produces time-predictable code. The resulting code contains a single input-data independent execution path, in order to obtain programs of stable timing behaviour. The transformation technique has been validated by applying it on a number of benchmarks. Experiments show a reduction of execution time variability, at acceptable costs for the single execution path.

Cite as

Daniel Prokesch, Benedikt Huber, and Peter Puschner. Towards Automated Generation of Time-Predictable Code. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 103-112, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{prokesch_et_al:OASIcs.WCET.2014.103,
  author =	{Prokesch, Daniel and Huber, Benedikt and Puschner, Peter},
  title =	{{Towards Automated Generation of Time-Predictable Code}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{103--112},
  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.103},
  URN =		{urn:nbn:de:0030-drops-46090},
  doi =		{10.4230/OASIcs.WCET.2014.103},
  annote =	{Keywords: Single-Path, Graph Transformation, Predictable Code, Compiler}
}

OASIcs, Volume 39

14th International Workshop on Worst-Case Execution Time Analysis

Event

Editor

Publication Details

Access Numbers

Documents

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Filters

Thanks for your feedback!

Could not send message