DROPS

Document

DOI: 10.4230/OASIcs.WCET.2012.38

Toward Static Timing Analysis of Parallel Software

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

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

Abstract

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

Cite as

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

Copy BibTex To Clipboard

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

Document

DOI: 10.4230/OASIcs.WCET.2010.101

Towards WCET Analysis of Multicore Architectures Using UPPAAL

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

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

Abstract

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

Cite as

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

Copy BibTex To Clipboard

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

Search Results

Documents authored by Gustavsson, Andreas

Toward Static Timing Analysis of Parallel Software

Abstract

Cite as

Towards WCET Analysis of Multicore Architectures Using UPPAAL

Abstract

Cite as

Thanks for your feedback!

Could not send message