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

论文摘要

实时系统对任务的执行时间有着苛刻的要求,因此需要保证系统在最坏情况下也能够满足时间需求,这就需要知道任务最坏情况执行时间（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替换策略的分析。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究目标与意义
• 1.3 国内外研究现状
• 1.4 论文组织结构
• 第2章 相关技术
• 2.1 WCET分析技术
• 2.1.1 程序路径分析
• 2.1.2 微体系结构分析
• 2.1.3 WCET计算
• 2.2 Cache分析
• 2.2.1 Cache简介
• 2.2.2 Cache替换策略
• 2.2.3 静态Cache分析
• 2.3 McAiT时间分析工具
• 2.4 本章小结
• 第3章 MRU替换策略分析
• 3.1 MRU替换策略
• 3.2 已有的MRU分析定理
• 3.3 传统分析方法存在的问题
• 3.4 面向MRU替换策略的指令访问特性分析
• 3.5 基于路径探索的分析方法
• 3.5.1 计算循环体最长路径长度
• 3.5.2 循环体公共结点的识别
• 3.5.3 复杂循环结构的分析
• 3.5.4 指令的Cache访问特性分类
• 3.6 WCET计算
• 3.7 本章小结
• 第4章 基于路径探索分析方法的实现
• 4.1 路径探索分析的总体流程
• 4.2 循环提取的实现
• 4.2.1 循环头结点识别
• 4.2.2 提取的实现
• 4.3 路径分析的实现
• 4.4 公共结点识别的实现
• 4.5 指令分析的实现
• 4.5.1 指令分类
• 4.5.2 计算基本块执行时间
• 4.6 本章小结
• 第5章 实验结果与分析
• 5.1 参数配置
• 5.2 实验结果
• 5.3 结果分析
• 5.4 本章小结
• 第6章 总结与展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 致谢
• 科研情况