License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2021.16
URN: urn:nbn:de:0030-drops-139474
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13947/
Marković, Filip ;
Papadopoulos, Alessandro Vittorio ;
Nolte, Thomas
On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems
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.
BibTeX - Entry
@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/opus/volltexte/2021/13947},
URN = {urn:nbn:de:0030-drops-139474},
doi = {10.4230/LIPIcs.ECRTS.2021.16},
annote = {Keywords: Probabilistic analysis, Random variables, Algorithm Complexity}
}
|
Keywords: |
|
Probabilistic analysis, Random variables, Algorithm Complexity |
|
Collection: |
|
33rd Euromicro Conference on Real-Time Systems (ECRTS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.06.2021 |
|
Supplementary Material: |
|
Software (ECRTS 2021 Artifact Evaluation approved artifact): https://doi.org/10.4230/DARTS.7.1.1 |
