Document Open Access Logo

On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems

Authors Filip Marković , Alessandro Vittorio Papadopoulos , Thomas Nolte

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2021.16.pdf
  • Filesize: 0.92 MB
  • 22 pages

Document Identifiers

Author Details

Filip Marković
  • Mälardalen University, Västerås, Sweden
Alessandro Vittorio Papadopoulos
  • Mälardalen University, Västerås, Sweden
Thomas Nolte
  • Mälardalen University, Västerås, Sweden

Funding

This work was supported by the Swedish Research Council (VR) via the project "Practical Probabilistic Timing Analysis of Real-Time Systems (PARIS)", and by the Knowledge Foundation (KKS) via the project "Federated Choreography of an Integrated Embedded Systems Software Architecture (FIESTA)".
  • Papadopoulos, Alessandro Vittorio: Swedish Research Council (VR) via the project "Pervasive Self-Optimizing Computing Infrastructures (PSI)".

Acknowledgements

We want to thank Davor Čirkinagić who borrowed his computing system for performing the evaluation. Also, we are very grateful to the anonymous reviewers for their comments.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ECRTS.2021.16

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic algorithms
  • Computer systems organization → Real-time system specification
Keywords
  • Probabilistic analysis
  • Random variables
  • Algorithm Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. George B. Arfken and Hans J. Weber. Mathematical methods for physicists, 1999. Google Scholar
  2. Enrico Bini and Giorgio C Buttazzo. Measuring the performance of schedulability tests. Real-Time Syst., 30(1-2):129-154, 2005. Google Scholar
  3. Jonathan M. Blackledge. Digital image processing: mathematical and computational methods. Elsevier, 2005. Google Scholar
  4. Sergey Bozhko and Björn B Brandenburg. Abstract response-time analysis: A formal foundation for the busy-window principle. In Euromicro Conf. Real-Time Syst. (ECRTS 2020), 2020. Google Scholar
  5. Ronald Newbold Bracewell. The Fourier transform and its applications. McGraw-Hill, 1999. Google Scholar
  6. Kuan-Hsun Chen and Jian-Jia Chen. Probabilistic schedulability tests for uniprocessor fixed-priority scheduling under soft errors. In IEEE Int. Symp. Industrial Emb. Syst. (SIES), pages 1-8, 2017. Google Scholar
  7. Kuan-Hsun Chen, Niklas Ueter, Georg von der Brüggen, and Jian-Jia Chen. Efficient computation of deadline-miss probability and potential pitfalls. In Design, Automation & Test in Europe Conf. & Exhibition (DATE), pages 896-901, 2019. Google Scholar
  8. Kuan-Hsun Chen, Georg von der Brüggen, and Jian-Jia Chen. Analysis of deadline miss rates for uniprocessor fixed-priority scheduling. In IEEE Int. Conf. Emb. and Real-Time Computing Syst. and Applications (RTCSA), pages 168-178, 2018. Google Scholar
  9. James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90):297-301, 1965. Google Scholar
  10. Robert Ian Davis and Liliana Cucu-Grosjean. A survey of probabilistic schedulability analysis techniques for real-time systems. LITES: Leibniz Trans. Emb. Syst., pages 1-53, 2019. Google Scholar
  11. Robert Ian Davis and Liliana Cucu-Grosjean. A survey of probabilistic timing analysis techniques for real-time systems. LITES: Leibniz Transactions on Embedded Systems, pages 1-60, 2019. Google Scholar
  12. Jose Luis Diaz, Jose Maria Lopez, Manuel Garcia, Antonio M Campos, Kanghee Kim, and Lucia Lo Bello. Pessimism in the stochastic analysis of real-time systems: Concept and applications. In IEEE Int. Real-Time Syst. Symp. (RTSS), pages 197-207, 2004. Google Scholar
  13. Geoffrey Grimmett and Dominic Welsh. Probability: an introduction. Oxford U. Press, 2014. Google Scholar
  14. Kanghee Kim, Jose Luis Diaz, Lucia Lo Bello, José María López, Chang-Gun Lee, and Sang Lyul Min. An exact stochastic analysis of priority-driven periodic real-time systems and its approximations. IEEE Transactions on Computers, 54(11):1460-1466, 2005. Google Scholar
  15. Charan Langton and Victor Levin. The Intuitive Guide to Fourier Analysis and Spectral Estimation. Mountcastle Company, 2017. Google Scholar
  16. Advanpix LLC. Multiprecision computing toolbox for MATLAB. URL: http://www.advanpix.com/.
  17. Filip Marković, Alessandro Vittorio Papadopoulos, and Thomas Nolte. Artifact-evaluation - on-the-convolution-efficiency, 2021. URL: https://github.com/Aeoliphile/Artifact-Evaluation---On-the-convolution-efficiency.
  18. Dorin Maxim and Liliana Cucu-Grosjean. Response time analysis for fixed-priority tasks with multiple probabilistic parameters. In 2013 IEEE 34th Real-Time Systems Symposium, pages 224-235. IEEE, 2013. Google Scholar
  19. Dorin Maxim, Mike Houston, Luca Santinelli, Guillem Bernat, Robert I Davis, and Liliana Cucu-Grosjean. Re-sampling for statistical timing analysis of real-time systems. In Int. Conf. Real-Time and Network Syst. (RTNS), pages 111-120, 2012. Google Scholar
  20. Dorin Maxim, Luca Santinelli, and Liliana Cucu-Grosjean. Improved sampling for statistical timing analysis of real-time systems. Int. Conf. Real-Time and Network Syst. (RTNS), pages 17-20, 2010. Google Scholar
  21. Stephen McGovern. MATLAB Central File Exchange, Fast Convolution. https://www.mathworks.com/matlabcentral/fileexchange/5110-fast-convolution. Accessed: 2021-01.
  22. Suzana Milutinović, Jaume Abella, Damien Hardy, Eduardo Quiñones, Isabelle Puaut, and Francisco J Cazorla. Speeding up static probabilistic timing analysis. In Int. Conf. Architecture of Computing Syst. (ARCS), pages 236-247, 2015. Google Scholar
  23. Alan V Oppenheim, John R Buck, and Ronald W Schafer. Discrete-time signal processing. Vol. 2. Upper Saddle River, NJ: Prentice Hall, 2001. Google Scholar
  24. Athanasios Papoulis. The fourier integral and its applications. McCraw-Hill, 1962. Google Scholar
  25. Khaled S Refaat and Pierre-Emmanuel Hladik. Efficient stochastic analysis of real-time systems via random sampling. In Euromicro Conf. Real-Time Syst. (ECRTS), pages 175-183, 2010. Google Scholar
  26. Moshe Shaked and J. George Shanthikumar, editors. Univariate Stochastic Orders, pages 3-79. Springer New York, New York, NY, 2007. Google Scholar
  27. Georg von der Brüggen. Realistic Scheduling Models and Analyses for Advanced Real-Time Embedded Systems. PhD thesis, TU Dortmund (Germany), 2019. Google Scholar
  28. Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik. Efficiently approximating the probability of deadline misses in real-time systems. In Euromicro Conf. Real-Time Syst. (ECRTS), 2018. Google Scholar
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 About DROPS Imprint Privacy Contact