程序最坏执行时间极值统计方法

Program worst-case execution time extreme value statistics estimation method

程序的最坏执行时间WCET是实时系统时间操作方面的可信基础,现有的WCET静态分析方法都需要对系统某种程度上的额外知识和限定性假设,导致现有的WCET分析方法本质上为偏高估计,降低了资源的利用率和系统的性能。给出一种基于极值统计的程序最坏执行时间估计新方法,采用程序执行时间的测量值作为样本,利用Gumbel分布建立程序最坏执行时间统计模型,根据测量样本序列预测执行时间的最大值,与以往的方法相比,这种方法综合体现了各种硬件特性对程序执行时间的影响,估计结果更为精确,更适合处理硬件特性和软件复杂度较高情况下的程序最坏执行时间估计。实验结果表明利用Gumbel分布建立的WCET估计模型能够快速且有效地给出实时程序的最坏执行时间估计。

The worst case execution time of program is convincing time basic for real-time system, existing WCET analysis methods need additional knowledge and limited assumptions of the system to some degree, which result in pessimistic WCET estimation and lower the resource utilization ratio and system performance.A new WCET estimation methods based on extreme value statistics is proposed in this paper,which builds WCET estimation model using Gumbel distribution based on the program execution time samples and predicts extreme execution time.Compared to the former methods, the proposed method can include all the effect causing by hardware characters,and the estimation result is more accurate,and is more suitable for the situation that hardware and software is more complex.The experimental results show that the proposed WCET estimation model based on Gumbel distribution can efficiently and quickly give WCET estimation for real-time program.