https://www.mdu.se/

mdu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the convolution efficiency for probabilistic analysis of real-time systems
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-3210-3819
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-1364-8127
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0001-6132-7945
2021 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2021Conference paper, Published paper (Refereed)
Abstract [en]

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 O(nlog(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. 

Place, publisher, year, edition, pages
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2021.
Keywords [en]
Algorithm complexity, Probabilistic analysis, Random variables, Convolution, Interactive computer systems, Polynomial approximation, Probability distributions, Vector spaces, Circular convolutions, Discrete random variables, Evaluation results, Linear convolution, Probabilistic distribution, Space and time complexity, State-of-the-art techniques, Real time systems
National Category
Computer Sciences Control Engineering
Identifiers
URN: urn:nbn:se:mdh:diva-55968DOI: 10.4230/LIPIcs.ECRTS.2021.16Scopus ID: 2-s2.0-85114963300ISBN: 9783959771924 (print)OAI: oai:DiVA.org:mdh-55968DiVA, id: diva2:1596820
Conference
33rd Euromicro Conference on Real-Time Systems, ECRTS 2021, 5 July 2021 through 9 July 2021
Available from: 2021-09-23 Created: 2021-09-23 Last updated: 2022-11-08Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Markovic, FilipPapadopoulos, AlessandroNolte, Thomas

Search in DiVA

By author/editor
Markovic, FilipPapadopoulos, AlessandroNolte, Thomas
By organisation
Embedded Systems
Computer SciencesControl Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 102 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf