关于wcet(Worst Case Execution Time)我阅读了一些文章,总结以下几点：1.首先是wcet的概念，在程序设计中，尤其是实时系统中，对最坏情况的时间计算是很重要的，这可能会影响到软件及整个系统的运行。可以从这个术语的英语翻译看出，这个概念指的是某一种可能性的假设，假设程序的某一部分可能会发生什么问题，可能需要运行多少时间。比如对于分支的情况A和情况B，其中就已存在这个概念（wcet）。当然分支结构只是所有程序结构中的一种，其他当然还包括循环等等。在数据结构算法中有这么一个概念就是平均运行时间，他们之间是有联系的却又不尽相同。平均运行时间是考虑整体程序的运行时间，以把最坏情况考虑在内，考虑的是整体效率，而wcet是指单单考虑某一段程序的运行情况，考虑的是特定情况的发生。这两个概念无本质区别。2.影响wcet的因素有几点：一，程序本身的分支跳转，循环；二，目标机器的硬件结构，比如pipeline,cache等；三，可能是编译器或者外部环境的影响。3.wcet的不可靠性及分析方法：由于可能会有不同情况之间的跳转和外部影响，所以动态wcet分析是不可靠的，，现今一般使用是静态分析方法。静态分析方法主要的key是设定固定值，决定程序运行路径，然后进行分析从而得出wcet。4.静态分析有两个层次，一个是高层分析，另一个是底层分析。高层分析主要是对程序路径的分析，其中也包括很多分析方法和算法,可视化方法就是其中之一，当然可视化方法中还有很多内容，比如代码段提取算法和最大/小时间预估算法等。对于程序这层来说，最基本的wcet公式是：wcet(s1;s2)=wcet(s1)+wcet(s2); wcet(if(c)s1;else s2)=wcet(c)+max(wcet(s1),wcet(s2));wcet(for(c) s1)=(n+1)*wcet(c)+n*wcet(s1)在这种情况下n已被固定为某个值（静态分析）。5.高层分析：这也是对程序结构的分析，一般从最小的连续代码段开始分析，这时候可能会用到代码段提取算法，现在我们不考虑这些，假设有一段程序是循环内的判断，这个代码可以把条件的每个判断画成一个2叉树，然后根据程序结构将这些2叉树相连，在每一个树的分支旁写下可能循环的最大和最小次数，通过找出整个树林的最大运行次数，可以得到这个代码段的wcet。具体的算法在最后给出。 底层分析：这是关于硬件结构的分析方法，主要的分析内容有cache，pipeline。大家都知道cache有失效率，而往往wcet就是统计其失效情况下运行时间。关于pipeline，一般来说只要不引起register等资源相关，两个连续代码段的pipeline运行的wcet就是他们分别运行时wcet的联结(concatenation).6.可视化分析方法：最近有人提出一种可视化分析wcet的方法，它通过将一个要分析的代码段从其编译器已编译完成的汇编代码中提取其代码，然后通过算法对其进行最大或最小时间分析，并将结果用图形等界面显示出来，当然，一些完善的可视化分析软件可把操作全部图形化。这种方法的优点在于它是把代码已被编译的汇编代码中提取代码段，所以这可以算是一种结合了高层和底层分析的方法，易于实现也不失精准。还有其可视性，可以实现基于流程的时间分析。当然由于分析算法的复杂性和自动选择程序路径的局限性，这个要运用于工业分析上尚需一段时间。
最大时间算法：输入:StartBlock,EndBlock,程序的二叉树结构,程序语句行时间数; 输出:最大时间数. 算法过程如下: 步骤1. 可达性判断,当且仅当起始块等于终止块,或者起始块经过有限次的顺接块到达终止块时,则设可达性标志为TRUE,否则设为FALSE; 步骤2. 如果可达性标志为TRUE,则转步骤3;否则退出,并给出不可达信息; 步骤3. 按照先序遍历以块为节点的程序结构二叉树,并按照表2中的规则求得各种基本块节点和特殊基本块节点的基线时间数Time; 步骤4. 采用递归算法,并按照表2中的各种块的最大时间MaxTime的计算规则,计算各种块的最大时间数MaxTime; 步骤5. 按如下算法求得指定程序段的最大时间数: MaxTime=∑(i=0->n)Next(i)(startBlock).MaxTime,其中Next(0)(block)=block, Next(1)(block)=block.NextBlock, Next(i+1)(block)=Next(Nexti(Block)). 步骤6. 返回最大时间数MaxTime.#
加油鼓励看好你，一天更比一天强
