博文
Worst-Case Execution Time and Energy Analysis 2
||
1. 前面提到，程序路径分析和体系结构建模是WCET分析必不可少的两步。本文讨论程序路径分析。程序路径分析，考虑的是，在程序输入未知的情况下，估计执行路径的长度的边界。以后，借助体系结构建模，执行路径的长度可以折合成机器的时钟数，并最终折合成时间。
https://blog.sciencenet.cn/blog-385122-489543.html
上一篇：Worst-Case Execution Time and Energy Analysis 1
下一篇：休息一年后的第一周
2. 要知道一个程序的执行路径，需要考虑如下程序结构：
（1）循环：循环的执行次数是影响执行路径长度的最大因素。进行这种分析，需要一个假设，循环的迭代次数是有界的。
（2）分支：程序执行哪一条分支也会影响执行路径的长度。
因此，需要检测不可执行分支，以及确定循环次数的边界。
3. 我们首先假设上面两个问题：检测不可执行分支和确定循环次数边界已经得到某种程度的结局，讨论一下WCET分析的几种方法。
3.1 基于树结构的方法（Tree-based Methods）
上下文无关程序语言的语法结构能够很自然地对应到树结构（比如抽象语法树）。树结构的最大有点是其组合性质（或递归性质）。基于树结构的计算WCET的组合方法如下：
- Time(S1;S2) = Time(S1) + Time(S2)
- Time(if B {S1} else {S2} ) = Time(B) + max(Time(S1), Time(S2))
- Time(while B {S1} ) = (n+1) * Time(B) + n * Time(S1) // 其中n是循环次数边界
缺点：展开的语法结构，以及自底向上的模式，不便于集成不可执行分支信息。比如，假设已知在一个循环中的两个分支，分支S1执行代价比S2高，但是执行频率比S2低。以上的代价估计就会过于保守。？？
3.2 基于路径的方法（Path-based Methods）
基于路径的方法，基本思路就是通过搜索程序执行流图的最长路径。循环边界用于避免循环的无穷展开；不可执行分支用于减少路径搜索空间。但是，理论上的最大搜索空间仍然是指数级增长的（需要枚举所有的循环迭代，以及组合所有的分支）。
减少搜索空间的方法：
（1）使用符号状态搜索而不是简单的路径搜索（符号模型检测）。但是模型检测的方法需要验证一个时序属性，因此需要先猜测WCET，再来验证该猜测的WCET确实是WCET。所以，在实际使用中很困难。
（2）一种流行的方法是，分开程序流图的有环部分和无环部分。采用Dijkstra的最短路径算法的变种，寻找无环图的最长路径，然后在组合循环次数边界，来确定程序的最长路径。
优点：路径敏感的分析可以更精确地利用程序执行流的信息。
缺点：方法复杂，搜索空间巨大。
3.3 ILP 方法
ILP方法同时具有树方法和路径方法的优点。其目标函数是：
其中b是控制流图中的基本块，N_b是基本块b的执行次数，c_b是基本块b的WCET估计。其约束条件主要是：
（1）对于任意一个基本块的执行执行频率N_b，其大小等于所有入边的频率总和，以及出边的频率总和。
（2）对于程序入口基本块，其执行频率为1.
（3）对于循环回边，其执行频率由循环边界确定。
（4）对于不可执行分支，其执行频率为0.
4. 检测不可执行分支
最常用的思路是数据流分析。数据流分析本质是为每一个静态程序点建立一个映射：从程序变量到其取值范围的映射。但是，数据流分析基于静态程序点，不仅需要考虑各种输入，而且需要考虑到达该点的各种路径，然后用一个集合来表示变量的范围。因此，数据流分析本质上不是路径敏感的，其分析结果过于保守。
符号执行（symbolic execution）以及约束解决器（constraints solver）可以改进数据流分析的精度。缺点仍然是巨大的搜索空间。
仍然有很多启发被提出来，在路径敏感与数据流的分析精度与分析复杂度之间折中。比如，pair-wise检测，即不做全路径分析，只处理相邻的（分支，分支）或者（赋值，分支）之间的冲突关系，从而减少搜索空间。循环内部，基于迭代变量的条件判断也提出了启发式。
5. 循环边界推导
最初的循环边界依赖于程序员注释。但是，程序员注释并不足够可靠。所以，自动推导不可避免。对于函数式程序和命令式程序，都有了一定进展。思路主要是识别循环内部的能够修改循环迭代器的的分支。
https://blog.sciencenet.cn/blog-385122-489543.html
上一篇：Worst-Case Execution Time and Energy Analysis 1
下一篇：休息一年后的第一周
