Reducing the Size of the Constraint Model in Implicit Path Enumeration Using Super Blocks
Reducing the Size of the Constraint Model in Implicit Path Enumeration Using Super Blocks
复制标题
使用超级块减小隐式路径枚举中约束模型的大小
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
A. Betts
中科院分区：
文献类型：
--
作者：
A. Betts
隐式路径枚举（IPE）是WCET分析中使用的最流行的计算技术，因为它通常提供了最精度。它利用控制流程图（CFG）构建一个约束系统，该系统由结构约束（源自CFG）和相对容量约束（相对于最内置的封闭环路）组成。但是，解决约束系统是一个NP硬性问题，因此需要减少模型的大小。本文表明，当CFG循环没有突破性构建体时，由IPE产生的约束系统由许多多余的结构约束组成，因为它们的消除不会降低WCET估计的精度。我们通过从新的中间数据结构（Super Block Control Flow图（SB-CFG））构建替代约束系统来证明这一事实。此外，我们说明了SB-CFG如何允许我们在实际需要相对容量限制时推断出来 - 直到现在，它们被认为是必须的，以避免使用循环高估。比较大量自动生成的控制流程图的两个约束系统，我们的结果表明，变量数量减少了50％，约束数量减少了55％，解决时间减少了69％ 。
Implicit Path Enumeration (IPE) is the most popular calculation technique used in WCET analysis as it generally provides the most precision. It utilises the Control Flow Graph (CFG) to build a constraint system consisting of, amongst others, structural constraints (derived from the CFG) and relative capacity constraints (loop bounds relative to the innermost enclosing loop). However, solving the constraint system is an NP-hard problem and reducing the size of the model is therefore desirable. This paper shows that, when the CFG loops are free of break-like constructs, the constraint system produced by IPE consists of many superfluous structural constraints in that their elimination does not detract from the precision of the WCET estimate. We demonstrate this fact by building an alternative constraint system from a new intermediate data structure called the Super Block Control Flow Graph (SB-CFG). Furthermore, we illustrate how the SB-CFG allows us to deduce when relative capacity constraints are actually needed -- until now they have been considered mandatory to avoid overestimations with loops. Comparing the two constraint systems across a large number of automatically generated control flow graphs, our results show there is: a 50% reduction in the number of variables, a 55% reduction in the number of constraints, and a 69% reduction in solving time.