Static probabilistic timing analysis for real-time systems using random replacement caches
Static probabilistic timing analysis for real-time systems using random replacement caches
复制标题
使用随机替换缓存的实时系统的静态概率时序分析
DOI：
10.1007/s11241-014-9218-4
复制
发表时间：
2015
影响因子：
1.3
通讯作者：
Altmeyer S
中科院分区：
文献类型：
--
作者：
Altmeyer S
在本文中，我们研究了单处理器实时系统的静态概率时序分析（SPTA），该系统使用具有未完成即退出随机替换策略的缓存。我们表明，以前发布的缓存命中概率公式在用于计算概率最坏情况执行时间（pWCET）分布时可能会产生乐观和不可靠的结果。我们研究了随机替换缓存的不同SPTA方法的正确性、最优性和精度。我们证明了先前发表的关于缓存命中概率的公式之一是最优的，相对于它使用的有限信息（重用距离和缓存关联性）。我们推导了一个替代公式，该公式利用了以访问的不同内存块数量（堆栈距离）的形式提供的附加信息。这提供了一个互补的下界，可以与以前发表的公式一起使用，以获得更准确的分析。我们通过使用关于缓存争用的额外信息来改进这种联合方法。为了研究各种SPTA方法的精度，我们引入了一种简单的穷举方法来计算精确的pWCET分布，尽管代价是指数复杂度。我们将这种精确的方法，应用于少量频繁访问的内存块，与其他内存块的不精确分析相结合，形成一种组合方法，提高精度，而不会显著增加复杂性。在基准程序上比较了各种方法的性能。我们还比较了最近最少使用的替代政策的确定性分析。
In this paper, we investigate static probabilistic timing analysis (SPTA) for single processor real-time systems that use a cache with an evict-on-miss random replacement policy. We show that previously published formulae for the probability of a cache hit can produce results that are optimistic and unsound when used to compute probabilistic worst-case execution time (pWCET) distributions. We investigate the correctness, optimality, and precision of different approaches to SPTA for random replacement caches. We prove that one of the previously published formulae for the probability of a cache hit is optimal with respect to the limited information (reuse distance and cache associativity) that it uses. We derive an alternative formulation that makes use of additional information in the form of the number of distinct memory blocks accessed (the stack distance). This provides a complementary lower bound that can be used together with previously published formula to obtain more accurate analysis. We improve upon this joint approach by using extra information about cache contention. To investigate the precision of various approaches to SPTA, we introduce a simple exhaustive method that computes a precise pWCET distribution, albeit at the cost of exponential complexity. We integrate this precise approach, applied to small numbers of frequently accessed memory blocks, with imprecise analysis of other memory blocks, to form a combined approach that improves precision, without significantly increasing complexity. The performance of the various approaches are compared on benchmark programs. We also make comparisons against deterministic analysis of the least recently used replacement policy.
登录
查看更多内容
最坏情况执行时间统计分析的现实性
DOI：
--
发表时间：
2010
期刊：
Worst-Case Execution Time Analysis
影响因子：
--
作者：
D. Griffin;A. Burns
通讯作者：
A. Burns
概率时序分析：使用 copula 的方法
DOI：
--
发表时间：
2005
期刊：
Journal of Embedded Computing
影响因子：
--
作者：
G. Bernat;A. Burns;M. Newby
通讯作者：
M. Newby
具有随机缓存替换策略的系统的静态概率时序分析的改进
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
R. Davis
通讯作者：
R. Davis
通过随机采样对实时系统进行高效随机分析
DOI：
--
发表时间：
2010
期刊：
Euromicro Conference on Real-Time Systems
影响因子：
--
作者：
Khaled S. Refaat;P. Hladik
通讯作者：
P. Hladik