| 主权项 |
一种精确计算任务高速缓存WCET的分析方法，其特征在于：包括以下步骤：步骤一：产生基本块的迭代范围；步骤二：计算高速缓存的丢失次数：程序指令以块的形式连续存放在内存中，以块为单位从内存调入到高速缓存，当CPU访问一条指令时，如果该指令不在高速缓存，CPU将该指令调入高速缓存，然后执行该指令；对任一高速缓存块，为该高速缓存块建立一个队列，该队列成员为循环体中所有映射到该高速缓存块的指令块；步骤2.1：计算循环体高速缓存块的最大丢失次数：对对应于一个高速缓存块的所有指令块，按照从小到大顺序进行排队，指令块x比指令块y小，其定义为：如果指令块x的最小迭代范围区间下限a<sub>1</sub>不大于指令块y的最小迭代范围区间下限a<sub>2</sub>，同时，如果x.a<sub>1</sub>=y.a<sub>2</sub>，则指令块x的最小迭代范围区间上限不大于指令块y的最小迭代范围区间上限；其中指令块的迭代范围为该指令块所涉及的基本块迭代范围的集合；一个指令块中的最小迭代范围[a,b]是指：a为该指令块中所有迭代范围的下限的最小值；如果有一个迭代范围[c,d]满足c=a，那么一定有b≤d；对高速缓存队列中的指令块的迭代范围进行遍历处理，直至队列中的指令块为空，处理方法为：形成一个最小迭代范围[e,f]；其中最小迭代范围[e,f]的产生方法为：下限e为高速缓存队列第一个指令块迭代范围的最小范围区间的下限，上限f取①和②中的最小值：①为高速缓存队列中所有指令块迭代范围区间上限的最小值；②为高速缓存队列中所有指令块迭代范围区间中大于e的下限最小值‑1；队列每遍历一次之后，需要将该高速缓存队列的指令块按照从小到大的顺序重新进行排队；按照从小到大的顺序，对高速缓存队列中的所有指令块的迭代范围进行处理，如果该指令块的迭代范围包括最小迭代范围[e,f]，那么将该指令块迭代范围减去范围[e,f]，同时对这样的指令块进行计数；如果这样的指令块只有一个，那么，在[e,f]的迭代范围里，只有这个指令块执行，因而其引起的丢失次数为1；如果在[e,f]的迭代范围里，有count个指令块(count>1)执行，那么，这些指令块在[e,f]范围的每一次迭代都将发生丢失，从而对应于指令块的迭代范围[e,f]的丢失次数为：(f‑e+1)*count；步骤2.2：对于非循环体指令，所有执行的指令块的丢失次数均为1；计算高速缓存的丢失次数：一个高速缓存块的丢失次数为所有这些丢失次数的累加；当针对一个高速缓存块的指令块的丢失次数计算完成之后，就可以计算整个高速缓存的丢失次数；整个高速缓存的丢失次数等于其中所有高速缓存块丢失次数的累加；步骤三：计算高速缓存的WCET:即一个运行在高速缓存处理器上实时任务的WCET，就是按照高速缓存全部命中计算出的WCET值加上高速缓存的丢失次数与时间惩罚的乘积。 |
