多核Cache替换策略模型研究

论文摘要

随着半导体工艺技术的进步,片上集成多个处理器已经成为可能。与单核处理器相比,多核处理器（CMP, Chip Multi-Processor）由于其在系统吞吐率、功耗效率、扩展性等方面的优势,已成为主流体系结构。多核下,应用访存行为多样、片外访问带宽有限,“存储墙”问题变得更加严重。片上存储系统特别是最后一级Cache（Last Level Cache,LLC）作为缓解“存储墙”的重要技术手段,其管理机制已成为影响多核处理器性能的关键因素之一。Cache替换策略的解析模型是Cache管理优化中的重要课题,与使用模拟器模拟的方法相比,解析模型具有计算速度快、可预测多种访存特点下替换策略的性能、可以针对不同应用特点进行相应的优化、可定量分析替换策略中各因素之间作用关系等优势,对于CMP片上存储系统的管理与设计有着十分重要的理论指导意义。本课题针对目前多核Cache管理机制研究中动态插入策略应用广泛却缺乏相应理论模型支撑的问题而展开,主要取得以下研究成果:1建立了Cache动态插入策略性能评价模型—DIPM（Dynamic Insertion Policy Model）。多核下,LRU策略对LLC逐渐失效,动态插入策略在LLC设计中应用广泛,但存在着插入位置选取缺乏理论指导、性能改善有限等问题。针对此问题,本文提出了动态插入策略性能评价模型DIPM。DIPM以应用的循环序列分布为输入,采用Markov链对数据块在Cache中的行为进行建模,可预测多种动态插入策略下应用的Cache失效率,进而选择最优的动态插入策略以指导Cache优化。2提出三种DIPM模型计算加速方法,使模型具备可计算性。目前已有Cache替换策略模型计算复杂性都为指数级,为实现模型的快速计算,本文证明了动态插入策略的命中率定理,并将其应用至模型加速中;然后对模型的状态空间树进行了分析,使用动态规划思想对其进行计算加速;整体失效率计算中采用了3-Max策略对模型进行了加速。通过以上加速技术,模型的计算复杂度由指数级降至多项式级。3采用Simics模拟器在SPEC2006测试程序集上对DIPM模型准确性进行了评价并对模型误差进行了分析,结果表明,模型误差较小,平均误差为-0.4%,最大误差为6.99%。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景
• 1.1.1 集成电路进入纳米时代
• 1.1.2 微处理器进入多核时代
• 1.1.3 “存储墙”问题日益突出
• 1.2 研究意义及主要工作
• 1.2.1 Cache 替换策略模型的研究意义
• 1.2.2 主要研究内容及创新
• 1.3 论文结构
• 第二章 多核Cache 替换策略研究
• 2.1 多核Cache 组织结构
• 2.1.1 Cache 基本概念
• 2.1.2 多核处理器Cache 组织结构
• 2.2 多核Cache 替换策略研究
• 2.2.1 替换策略的细分
• 2.2.2 多核LLC 管理问题
• 2.2.3 多核LLC 替换策略研究
• 2.2.4 目前研究中存在的不足
• 2.3 替换策略模型研究
• 2.3.1 LRU 模型
• 2.3.2 Analytical 模型
• 2.3.3 Stochastic 模型
• 2.3.4 模型比较
• 2.4 小结
• 第三章 Cache 动态插入策略模型
• 3.1 模型基本结构
• 3.1.1 动态插入策略
• 3.1.2 DIPM 的优化目标
• 3.1.3 DIPM 模型结构
• 3.2 输入访存序列分布的计算
• 3.3 单循环序列失效率计算
• 3.3.1 Markov 链基本概念
• 3.3.2 提升流序列失效率计算
• 3.3.3 插入流序列失效率计算
• 3.4 状态转移概率的计算
• 3.4.1 首次访存概率
• 3.4.2 首次访存命中概率
• 3.4.3 非首次访存命中概率
• 3.5 整体失效率的计算
• 3.5.1 一步迭代整体失效率计算
• 3.5.2 使用迭代法求出整体失效率
• 3.6 小结
• 第四章 模型计算加速技术
• 4.1 模型复杂度分析
• 4.1.1 输入序列分布估计的计算复杂性
• 4.1.2 单循环序列失效率计算的复杂性
• 4.1.3 整体重用距离命中率计算的复杂性
• 4.1.4 迭代算法的计算复杂性
• 4.2 单序列失效率计算加速
• 4.2.1 循环序列命中率分析及加速
• 4.2.2 动态规划加速
• 4.3 整体失效率计算加速
• 4.4 截断误差
• 4.5 小结
• 第五章 模型评价
• 5.1 模型评价方法
• 5.1.1 评价平台
• 5.1.2 评价指标及评价流程
• 5.2 模型评价
• 5.3 模型误差分析
• 5.3.1 输入流分布的误差分析
• 5.3.2 提升流与插入流模型误差分析
• 5.3.3 整体误差分析
• 5.4 动态插入策略的评价
• 5.5 小结
• 第六章结束语
• 6.1 工作总结
• 6.2 工作展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果