Search Results

Documents authored by Nolte, Thomas

Document
Artifact
DOI: 10.4230/DARTS.7.1.1
On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems (Artifact)

Authors: Filip Marković, Alessandro Vittorio Papadopoulos, and Thomas Nolte

Published in: DARTS, Volume 7, Issue 1, Special Issue of the 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

Abstract
This artifact describes the process for validation and reproduction of the experiments given in the associated paper "On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems". This document contains the information on the scope of the presented artifact, i.e. what are the considered experiments, instructions for obtaining the source code of the experiments, tested platforms, and other relevant information.
Cite as

Filip Marković, Alessandro Vittorio Papadopoulos, and Thomas Nolte. On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems (Artifact). In Special Issue of the 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Dagstuhl Artifacts Series (DARTS), Volume 7, Issue 1, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{markovic_et_al:DARTS.7.1.1,
  author =	{Markovi\'{c}, Filip and Papadopoulos, Alessandro Vittorio and Nolte, Thomas},
  title =	{{On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems (Artifact)}},
  pages =	{1:1--1:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2021},
  volume =	{7},
  number =	{1},
  editor =	{Markovi\'{c}, Filip and Papadopoulos, Alessandro Vittorio and Nolte, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.7.1.1},
  URN =		{urn:nbn:de:0030-drops-139804},
  doi =		{10.4230/DARTS.7.1.1},
  annote =	{Keywords: Probabilistic analysis, Random variables, Algorithm Complexity}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2021.16
On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems

Authors: Filip Marković, Alessandro Vittorio Papadopoulos, and Thomas Nolte

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

Abstract
This paper addresses two major problems in probabilistic analysis of real-time systems: space and time complexity of convolution of discrete random variables. For years, these two problems have limited the applicability of many methods for the probabilistic analysis of real-time systems, that rely on convolution as the main operation. Convolution in probabilistic analysis leads to a substantial space explosion and therefore space reductions may be necessary to make the problem tractable. However, the reductions lead to pessimism in the obtained probabilistic distributions, affecting the accuracy of the timing analysis. In this paper, we propose an optimal algorithm for down-sampling, which minimises the probabilistic expectation (i.e., the pessimism) in polynomial time. The second problem relates to the time complexity of the convolution between discrete random variables. It has been shown that quadratic time complexity of a single linear convolution, together with the space explosion of probabilistic analysis, limits its applicability for systems with a large number of tasks, jobs, and other analysed entities. In this paper, we show that the problem can be solved with a complexity of 𝒪(n log(n)), by proposing an algorithm that utilises circular convolution and vector space reductions. Evaluation results show several important improvements with respect to other state-of-the-art techniques.
Cite as

Filip Marković, Alessandro Vittorio Papadopoulos, and Thomas Nolte. On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{markovic_et_al:LIPIcs.ECRTS.2021.16,
  author =	{Markovi\'{c}, Filip and Papadopoulos, Alessandro Vittorio and Nolte, Thomas},
  title =	{{On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.16},
  URN =		{urn:nbn:de:0030-drops-139474},
  doi =		{10.4230/LIPIcs.ECRTS.2021.16},
  annote =	{Keywords: Probabilistic analysis, Random variables, Algorithm Complexity}
}
Document
DOI: 10.4230/LITES-v004-i002-a003
Per Processor Spin-Based Protocols for Multiprocessor Real-Time Systems

Authors: Sara Afshar, Moris Behnam, Reinder J. Bril, and Thomas Nolte

Published in: LITES, Volume 4, Issue 2 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 2

Abstract
This paper investigates preemptive spin-based global resource sharing protocols for resource-constrained real-time embedded multi-core systems based on partitioned fixed-priority preemptive scheduling. We present preemptive spin-based protocols that feature (i) an increased schedulability ratio of task sets and reduced response jitter of tasks compared to the classical non-preemptive spin-based protocol, (ii) similar memory requirements for the administration of waiting tasks as for the non-preemptive protocol whilst only causing (iii) a minimal increase of the minimal number of required stacks per core from one to at most two, and (iv) strong progress guarantees to tasks. We complement these protocols with a unified worst-case response time analysis that specializes to the classical analysis for the non-preemptive protocol. The paper includes a comparative evaluation of the preemptive protocols and the non-preemptive protocol based on synthetic data.
Cite as

Sara Afshar, Moris Behnam, Reinder J. Bril, and Thomas Nolte. Per Processor Spin-Based Protocols for Multiprocessor Real-Time Systems. In LITES, Volume 4, Issue 2 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 2, pp. 03:1-03:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{afshar_et_al:LITES-v004-i002-a003,
  author =	{Afshar, Sara and Behnam, Moris and Bril, Reinder J. and Nolte, Thomas},
  title =	{{Per Processor Spin-Based Protocols for Multiprocessor Real-Time Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{03:1--03:30},
  ISSN =	{2199-2002},
  year =	{2018},
  volume =	{4},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i002-a003},
  doi =		{10.4230/LITES-v004-i002-a003},
  annote =	{Keywords: Resource sharing, Real-time systems, Multiprocessors, Spin-locks}
}
Document
DOI: 10.4230/OASIcs.WCET.2007.1185
Clustering Worst-Case Execution Times for Software Components

Authors: Johan Fredriksson, Thomas Nolte, Andreas Ermedahl, and Mikael Nolin

Published in: OASIcs, Volume 6, 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07) (2007)

Abstract
For component-based systems, classical techniques for Worst-Case Execution Time (WCET) estimation produce unacceptable overestimations of a componentsWCET. This is because software components more general behavior, required in order to facilitate reuse. Existing tools and methods in the context of Component-Based Software Engineering (CBSE) do not yet adequately consider reusable analyses. We present a method that allows different WCETs to be associated with subsets of a components behavior by clustering WCETs with respect to behavior. The method is intended to be used for enabling reusable WCET analysis for reusable software components. We illustrate our technique and demonstrate its potential in achieving tight WCET-estimates for components with rich behavior.
Cite as

Johan Fredriksson, Thomas Nolte, Andreas Ermedahl, and Mikael Nolin. Clustering Worst-Case Execution Times for Software Components. In 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07). Open Access Series in Informatics (OASIcs), Volume 6, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fredriksson_et_al:OASIcs.WCET.2007.1185,
  author =	{Fredriksson, Johan and Nolte, Thomas and Ermedahl, Andreas and Nolin, Mikael},
  title =	{{Clustering Worst-Case Execution Times for Software Components}},
  booktitle =	{7th International Workshop on Worst-Case Execution Time Analysis (WCET'07)},
  pages =	{1--7},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-05-7},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{6},
  editor =	{Rochange, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2007.1185},
  URN =		{urn:nbn:de:0030-drops-11852},
  doi =		{10.4230/OASIcs.WCET.2007.1185},
  annote =	{Keywords: Worst-case execution time, Software components, Reuse, Analysis}
}
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