On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems (Artifact)
On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems (Artifact)
复制标题
关于实时系统概率分析的卷积效率（工件）
DOI：
10.4230/darts.7.1.1
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
T. Nolte
中科院分区：
文献类型：
--
作者：
Filip Marković;A. Papadopoulos;T. Nolte
本文讨论了实时系统概率分析中的两个主要问题：离散随机变量卷积的空间复杂度和时间复杂度。多年来，这两个问题限制了许多以卷积为主要运算的实时系统概率分析方法的适用性。概率分析中的卷积导致大量空间爆炸，因此可能需要减少空间以使问题易于处理。然而，这种减少导致得到的概率分布的悲观情绪，影响了时间分析的准确性。在本文中，我们提出了一种下采样的最优算法，该算法在多项式时间内使概率期望（即悲观主义）最小化。第二个问题涉及离散随机变量之间卷积的时间复杂度。研究表明，单次线性卷积的二次时间复杂度以及概率分析的空间爆炸限制了其对具有大量任务、作业和其他分析实体的系统的适用性。在本文中，我们通过提出一种利用循环卷积和向量空间约简的算法，证明了这个问题可以用O （n log(n)）的复杂度来解决。评价结果表明，与其他最先进的技术相比，有几项重要的改进。
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 ( 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.
使用X射线相位成像法观察轮岛涂
DOI：
--
发表时间：
2019
期刊：
影响因子：
--
作者：
宮部さやか;藤井規史;藤本慎司;岡本博之，藤森茜，森川公彦，水野薫
通讯作者：
岡本博之，藤森茜，森川公彦，水野薫