面向MRU替换策略的Cache分析技术的研究

发布时间：2020-04-29 21:51

【摘要】：实时系统对任务的执行时间有着苛刻的要求,因此需要保证系统在最坏情况下也能够满足时间需求,这就需要知道任务最坏情况执行时间(Worst-Case Execution Time, WCET)。Cache作为计算机存储体系结构中的重要层次,对于任务的执行时间有着巨大的影响,因此WCET分析的重要任务之一,就是分析任务在Cache中命中或失效的情况。传统的Cache分析的研究,普遍假设替换策略为LRU。但是在实际的处理器中,由于硬件实现代价过高,通常不采用LRU替换策略,而是采用各种类LRU的策略,MRU替换算法即是其中的一种。相关研究主要采用抽象解释技术分析基于LRU替换策略的Cache。但是对于MRU替换策略,由于其替换行为较LRU更加复杂,因此难以使用抽象解释技术进行分析。基于上述背景,本文提出一种针对MRU替换策略的Cache分析技术。该技术突破了抽象解释技术的分析框架,提出了一种基于“路径探索(Path Exploration)"的程序结构分析方法,并在这一新的框架之上,深入挖掘MRU替换策略的特性,针对程序循环体的不同特性,给出了相应的判定指令命中与失效的理论。我们在McAiT这一时间分析工具中实现了本文所提出的分析方法,采用WCET分析领域公认的测试程序集中的程序进行了实验。实验结果表明,本文所提出的方法能够有效的分析在MRU替换策略下程序指令在Cache中的命中情况,实验观测到的最高分析精度的提高达到62%。本文的研究面向实际系统中的Cache替换策略,对于实际应用具有重要意义。同时,本文所提出的分析框架具有一定的通用性,亦可扩展并应用于其他Cache替换策略的分析。
【图文】：

程序执行时间,基本概念,执行时间,程序

程序执行时间的基本概念Fig.1.1Basicconceptsofexecutiontimesofprograms

组相联映射,全相联映射

东北大学领士学位论文第2章相关技术第三种为组相联映射，如图2.4所示。首先Cache分成若干个组，每组包含若干块，然后主存按照Cache容量分区，每个区再根据Cache的分组情况同样的分成如干组，每组中包含的块数与Cache中每组块数一致。前面介绍过，组相联映射为直接映射和全相联映射的折中，主要表现在根据前面介绍的分组情况，组间采用直接映射，而组内采用全相联映射。这就结合了直接映射和全相联映射各自的优点，且在一定程度上避免了各自的缺点。主存
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TP333

【参考文献】