CMP体系结构的L2 Cache替换算法研究

论文摘要

近40年来,处理器与存储器访问速度之间存在着巨大的差距导致内存墙问题变得越来越严重,成为影响系统性能最主要的瓶颈之一。现代计算机体系结构中广泛采用Cache来缓解两者之间的速度差距。在典型的CMP（Chip Multi-Processor）体系结构中,多个处理器核共享二级Cache,提高了二级Cache利用率并且能避免复制存储器硬件资源。但处理器核的分支错误预测导致错误路径上的加载缺失向共享的二级Cache中写入无用数据,造成二级Cache的污染,降低了其它核对二级Cache空间的占用率,增加了二级Cache缺失率,引起存储资源线程分配的不均衡,甚至导致线程饥饿。因此Cache的替换算法是保证效率的关键。如何在尽可能小的开销下,提高Cache的命中率,使处理器获得尽可能高的性能,成为当前Cache研究的一个重要课题。本论文详细研究了常见的CMP中Cache资源分配及其共享Cache的替换策略。通过对伪LRU算法进行详细分析,改进了伪LRU算法,提出了FPLRU算法,详细设计和实现了分支信息缓冲器（BIB）,通过BIB来记录预测路径的相关信息,从而尽早的将错误路径数据从二级Cache中替换出去,增加了利用数据局部性的可能。基准测试程序实验结果表明FPLRU算法与伪LRU算法相比Cache失效率有较为明显的降低。CMP结构中共享L2 Cache,当多个线程运行时,由于资源竞争导致Cache失效增加和系统性能下降。为了研究L2 Cache中线程的变化情况,提出了一种预测L2 Cache失效的Shared-Cache模拟技术,主要利用循环序列和栈处理技术分析预测L2 Cache的强制性Cache失效、共享数据的Cache容量失效和私有数据的Cache容量失效。利用实验验证了模型的有效性,结果表明该模型能够准确预测L2 Cache的失效。另外,本论文对SimpleScalar模拟器及CMP-SIM模拟器的Cache模拟及实现机制做了大量的分析及研究工作,用CMP-SIM模拟器及基准测试程序进行实验。最后,对上述算法进行了详细的评估、分析。

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 问题的提出及研究意义
• 1.1.1 问题的提出
• 1.1.2 研究的意义
• 1.2 国内外研究现状
• 1.2.1 CMP 体系结构发展的现状
• 1.2.2 Cache 技术发展现状
• 1.3 本文研究的目的和研究内容
• 1.3.1 本文研究的目的
• 1.3.2 本文研究的主要内容
• 2 多核处理器的 Cache 研究
• 2.1 Cache 的层次结构
• 2.2 Cache 替换策略的重要性
• 2.3 提高Cache 性能的方法
• 2.3.1 减少缺失代价
• 2.3.2 减少命中时间
• 2.3.3 降低缺失率
• 2.4 Cache 替换策略
• 2.4.1 单核心处理器Cache 调度算法
• 2.4.2 多核心Cache 调度算法和管理策略
• 2.5 Cache Fair 调度算法
• 2.6 本章小结
• 3 FPLRU 替换算法及其仿真结果
• 3.1 比较对PLRU
• 3.2 分支信息缓冲器BIB
• 3.3 FPLRU 替换算法的结构
• 3.3.1 处理器内核
• 3.3.2 二级Cache
• 3.3.3 分支预测信息缓冲器BIB
• 3.3.4 FPLRU 单元
• 3.4 FPLRU 的替换流程
• 3.5 实验工具和测试程序
• 3.5.1 SimpleScalar 及CMP-SIM 模拟器
• 3.5.2 CMP-SIM 结构
• 3.5.3 CMP-SIM 的Cache 管理策略
• 3.5.4 基准测试程序
• 3.6 FPLRU 算法仿真及结果
• 3.6.1 对L2 Cache 命中率的影响
• 3.6.2 Cache 性能分析
• 3.7 本章小结
• 4 Shared-Cache 对共享 L2 Cache 行为的分析
• 4.1 栈处理技术
• 4.2 循环序列技术
• 4.3 分析策略
• 4.3.1 计算强制失效
• 4.3.2 计算私有数据容量失效
• 4.3.3 计算共享数据容量失效
• 4.4 Shared-Cache 实验
• 4.4.1 dgemm 实验结果
• 4.4.2 块dgemm 实验结果
• 4.4.3 稀疏矩阵向量乘法实验结果
• 4.5 本章小结
• 5 结束语
• 5.1 主要工作
• 5.2 后续研究工作
• 致谢
• 参考文献
• 附录