Adaptive Runtime Estimate of Task Execution Times using Bayesian Modeling
Adaptive Runtime Estimate of Task Execution Times using Bayesian Modeling
复制标题
使用贝叶斯建模对任务执行时间进行自适应运行时估计
DOI：
10.1109/rtcsa52859.2021.00008
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Thomas Nolte
中科院分区：
文献类型：
--
作者：
A. Friebe;Filip Marković;A. Papadopoulos;Thomas Nolte
在最近的工作中，分析实时任务的执行时间变化，表明这种变化可能符合常规行为。这种规律性可能有多种来源，例如，由于硬件或程序状态、程序结构、任务间依赖或任务间干扰的周期性变化。与假设独立且分布相同的随机变量的常用方法相比，马尔可夫模型可以更好地捕捉这种复杂性。然而，尽管可以用马尔可夫模型描述规律性，但随着时间的推移，由于输入、硬件状态或程序状态的不规则变化，执行时间可能会发生变化。在本文中，我们提出了一种贝叶斯方法来适应运行时马尔可夫模型的发射分布，以解释这种不规则变化。预处理步骤从执行时间序列的一部分确定状态数和马尔可夫模型的转移矩阵。在预处理步骤中，识别具有相似属性的执行时间跟踪片段并将其组合到集群中。在运行时，该方法基于广义似然比（GLR）在这些聚类之间切换。使用贝叶斯方法，更新集群和估计排放分布。可以识别新的集群，并且可以在运行时合并集群。在线步骤的时间复杂度为$O(N^{2}+ NC)$，其中N为预处理步骤后固定的隐马尔可夫模型（HMM）状态数，C为聚类数。
In the recent works that analyzed execution-time variation of real-time tasks, it was shown that such variation may conform to regular behavior. This regularity may arise from multiple sources, e.g., due to periodic changes in hardware or program state, program structure, inter-task dependence or inter-task interference. Such complexity can be better captured by a Markov Model, compared to the common approach of assuming independent and identically distributed random variables. However, despite the regularity that may be described with a Markov model, over time, the execution times may change, due to irregular changes in input, hardware state, or program state. In this paper, we propose a Bayesian approach to adapt the emission distributions of the Markov Model at runtime, in order to account for such irregular variation. A preprocessing step determines the number of states and the transition matrix of the Markov Model from a portion of the execution time sequence. In the preprocessing step, segments of the execution time trace with similar properties are identified and combined into clusters. At runtime, the proposed method switches between these clusters based on a Generalized Likelihood Ratio (GLR). Using a Bayesian approach, clusters are updated and emission distributions estimated. New clusters can be identified and clusters can be merged at runtime. The time complexity of the online step is $O(N^{2}+ NC)$ where N is the number of states in the Hidden Markov Model (HMM) that is fixed after the preprocessing step, and C is the number of clusters.