最小化最坏执行时间的指令缓存锁定算法

最小化最坏执行时间的指令缓存锁定算法 Instruction Cache Locking Algorithm Aiming to Minimizing Worst-Case Execution Time 曾辉 ZENG Hui 1 first-author 武汉大学计算机学院 武汉大学计算机学院 School of Computer,Wuhan University School of Computer,Wuhan University 通过静态指令缓存锁定,最小化实时嵌入式系统的最坏执行时间.本文使用执行流树来进行分析,将问题描述为一个线性规划模型;从理论上证明了一般性问题是NP难的;对于含有某些特定模式的具体的子问题,给出了求解其最优解的多项式时间算法.实验表明,本文的算法在减少应用的最坏执行时间上效果很好. This paper presents techniques exploring the lockdown of instruction caches at compile-time to minimize Worst Case Execution Time （WCET） for real-time embedded systems.We formulate the problem using an Execution Flow Tree （EFT） and linear programming model.For a subset of the problems with certain properties,corresponding polynomial time optimal algorithms are proposed.We prove that the general problem is NP-hard problem.We also show that optimal solutions can be achieved in polynomial time for a subset of the general problem with certain patterns.Experimental results show that our algorithms can reduce the applications WCET of well. 缓存锁定 执行流树 最坏执行时间 嵌入式系统 cache locking execution flow tree worst case execution time embedded systems 10.14188/j.1671-8836.2010.06.016 TP301.6 2010-06-01 2021-04-01 6 56