基于MPA与静态预估的最坏执行时间分析方法

Worst-case Execution Time Analysis Method Based on MPA and Static Prediction

针对现有嵌入式系统最坏执行时间(WCET)的静态分析方法效率低下问题,利用最小传播算法对程序流进行分析,获得程序中每一个基本块的最小树约束,通过象征性循环上界约束对所求函数中的内部循环变量进行再次约束,并结合最小树约束获得程序的WCET表达式。使用静态预估分析方法对每一个基本块的底层指令周期进行绝对估值,将底层指令周期代入WCET表达式计算出程序最终的WCET值。实验结果表明,与基于程序控制流程图的程序执行时间静态分析方法相比,该方法在保证程序分析精度的同时,大幅提高了分析效率。

Aiming at the problem of low efficiency for embedded system Worst-case Execution Time（WCET）static analysis methods,this paper uses Minimum Propagation Algorithm（MPA）to analyze the program flow and obtain the min-tree of each code block.Then it gets more strict constraints through the analysis of inner loop variables of function by symbolic loop bounds computation,and gets a WCET expression through constraints of min-tree and the loop bounds.Finally,it uses static prediction method to solve the WCET by absolute valuation of underlying instruction cycle of each basic block,and calculates the final WCET value.Experimental results show that this method increases the analysis efficiency as well as ensures accuracy compared with program execution time static analysis method based on process control flow diagram.