一种快速程序最坏执行时间分析方法研究

Study on fast program worst-case execution time estimation

给出一种带有路径冲突检测的程序最坏情况执行时间估计方法,这种方法首先检测程序中存在的分支约束,然后将程序中存在的分支约束信息转化为程序流程控制图(CFG图)中结点之间的语义冲突,并按照结点对的形式保存在相应的冲突数组里,在接下来的WCET计算阶段通过边搜索程序执行路径边检测冲突数组里保存的已有的冲突关系以便在搜索路径的同时排除非可行执行路径,最终在可行执行路径集中选择具有最大执行时间的执行路径。与以往的方法相比,在保持估计精度的前提下,本文的方法避免了穷举所有执行路径带来的复杂度,提高了搜索的效率。实验结果表明本文方法对于语句间语义依赖关系比较强的实时程序能够快速且有效地给出估计结果。

A new program worst-case execution time estimation method with path conflict detection is proposed.Firstly,the method pre-computes program branch constraints,then converts these branch constraints to semantic conflicts between node-pair of Control Flow Graph（CFG） and saves these semantic conflicts into conflicts array of corresponding program in order to exclude impossible paths when searching path and improve searching path efficiency.The method finally selects path which has the maximum execution time from possible paths collection.Compared with some other former methods,this method can avoid high cost of all path enumeration and improve search efficiency while holding the same estimation precision. The experimental results show that the proposed method can efficiently and quickly give WCET estimation for high seman-tic dependency real-time programs.