Search Results

Documents authored by Markovic, Filip

Found 2 Possible Name Variants:

Markovic, Filip

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/LIPIcs.ECRTS.2020.5
Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning

Authors: Filip Marković, Jan Carlson, Sebastian Altmeyer, and Radu Dobrin

Published in: LIPIcs, Volume 165, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)

Abstract
Schedulability analyses for preemptive real-time systems need to take into account cache-related preemption delays (CRPD) caused by preemptions between the tasks. The estimation of the CRPD values must be sound, i.e. it must not be lower than the worst-case CRPD that may occur at runtime, but also should minimise the pessimism of estimation. The existing methods over-approximate the computed CRPD upper bounds by accounting for multiple preemption combinations which cannot occur simultaneously during runtime. This over-approximation may further lead to the over-approximation of the worst-case response times of the tasks, and therefore a false-negative estimation of the system’s schedulability. In this paper, we propose a more precise cache-aware response time analysis for sporadic real-time systems under fully-preemptive fixed priority scheduling. The evaluation shows a significant improvement over the existing state of the art approaches.
Cite as

Filip Marković, Jan Carlson, Sebastian Altmeyer, and Radu Dobrin. Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{markovic_et_al:LIPIcs.ECRTS.2020.5,
  author =	{Markovi\'{c}, Filip and Carlson, Jan and Altmeyer, Sebastian and Dobrin, Radu},
  title =	{{Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{V\"{o}lp, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.5},
  URN =		{urn:nbn:de:0030-drops-123682},
  doi =		{10.4230/LIPIcs.ECRTS.2020.5},
  annote =	{Keywords: Real-time systems, Fixed-Priority Preemptive Scheduling, Preemption delay}
}
Document
DOI: 10.4230/OASIcs.WCET.2017.4
Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling

Authors: Filip Markovic, Jan Carlson, and Radu Dobrin

Published in: OASIcs, Volume 57, 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)

Abstract
Limited Preemptive Fixed Preemption Point scheduling (LP-FPP) has the ability to decrease and control the preemption-related overheads in the real-time task systems, compared to other limited or fully preemptive scheduling approaches. However, existing methods for computing the preemption overheads in LP-FPP systems rely on over-approximation of the evicting cache blocks (ECB) calculations, potentially leading to pessimistic schedulability analysis. In this paper, we propose a novel method for preemption cost calculation that exploits the benefits of the LP-FPP task model both at the scheduling and cache analysis level. The method identifies certain infeasible preemption combinations, based on analysis on the scheduling level, and combines it with cache analysis information into a constraint problem from which less pessimistic upper bounds on cache-related preemption delays (CRPD) can be derived. The evaluation results indicate that our proposed method has the potential to significantly reduce the upper bound on CRPD, by up to 50% in our experiments, compared to the existing over-approximating calculations of the eviction scenarios.
Cite as

Filip Markovic, Jan Carlson, and Radu Dobrin. Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{markovic_et_al:OASIcs.WCET.2017.4,
  author =	{Markovic, Filip and Carlson, Jan and Dobrin, Radu},
  title =	{{Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  pages =	{4:1--4:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-057-6},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{57},
  editor =	{Reineke, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2017.4},
  URN =		{urn:nbn:de:0030-drops-73066},
  doi =		{10.4230/OASIcs.WCET.2017.4},
  annote =	{Keywords: Real-time systems, CRPD Analysis, WCET analysis, Limited Preemptive Scheduling, Fixed Preemption Point Approach}
}

Marković, Filip

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/LIPIcs.ECRTS.2020.5
Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning

Authors: Filip Marković, Jan Carlson, Sebastian Altmeyer, and Radu Dobrin

Published in: LIPIcs, Volume 165, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)

Abstract
Schedulability analyses for preemptive real-time systems need to take into account cache-related preemption delays (CRPD) caused by preemptions between the tasks. The estimation of the CRPD values must be sound, i.e. it must not be lower than the worst-case CRPD that may occur at runtime, but also should minimise the pessimism of estimation. The existing methods over-approximate the computed CRPD upper bounds by accounting for multiple preemption combinations which cannot occur simultaneously during runtime. This over-approximation may further lead to the over-approximation of the worst-case response times of the tasks, and therefore a false-negative estimation of the system’s schedulability. In this paper, we propose a more precise cache-aware response time analysis for sporadic real-time systems under fully-preemptive fixed priority scheduling. The evaluation shows a significant improvement over the existing state of the art approaches.
Cite as

Filip Marković, Jan Carlson, Sebastian Altmeyer, and Radu Dobrin. Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{markovic_et_al:LIPIcs.ECRTS.2020.5,
  author =	{Markovi\'{c}, Filip and Carlson, Jan and Altmeyer, Sebastian and Dobrin, Radu},
  title =	{{Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{V\"{o}lp, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.5},
  URN =		{urn:nbn:de:0030-drops-123682},
  doi =		{10.4230/LIPIcs.ECRTS.2020.5},
  annote =	{Keywords: Real-time systems, Fixed-Priority Preemptive Scheduling, Preemption delay}
}
Document
DOI: 10.4230/OASIcs.WCET.2017.4
Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling

Authors: Filip Markovic, Jan Carlson, and Radu Dobrin

Published in: OASIcs, Volume 57, 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)

Abstract
Limited Preemptive Fixed Preemption Point scheduling (LP-FPP) has the ability to decrease and control the preemption-related overheads in the real-time task systems, compared to other limited or fully preemptive scheduling approaches. However, existing methods for computing the preemption overheads in LP-FPP systems rely on over-approximation of the evicting cache blocks (ECB) calculations, potentially leading to pessimistic schedulability analysis. In this paper, we propose a novel method for preemption cost calculation that exploits the benefits of the LP-FPP task model both at the scheduling and cache analysis level. The method identifies certain infeasible preemption combinations, based on analysis on the scheduling level, and combines it with cache analysis information into a constraint problem from which less pessimistic upper bounds on cache-related preemption delays (CRPD) can be derived. The evaluation results indicate that our proposed method has the potential to significantly reduce the upper bound on CRPD, by up to 50% in our experiments, compared to the existing over-approximating calculations of the eviction scenarios.
Cite as

Filip Markovic, Jan Carlson, and Radu Dobrin. Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{markovic_et_al:OASIcs.WCET.2017.4,
  author =	{Markovic, Filip and Carlson, Jan and Dobrin, Radu},
  title =	{{Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  pages =	{4:1--4:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-057-6},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{57},
  editor =	{Reineke, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2017.4},
  URN =		{urn:nbn:de:0030-drops-73066},
  doi =		{10.4230/OASIcs.WCET.2017.4},
  annote =	{Keywords: Real-time systems, CRPD Analysis, WCET analysis, Limited Preemptive Scheduling, Fixed Preemption Point Approach}
}
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