CC-NUMA多机系统Cache一致性研究

论文摘要

高速缓存一致的非对称访存系统（CC-NUMA）是当前被广泛应用的多机系统之一。与传统的MIMD系统一样, Cache一致性问题也是CC-NUMA系统必须首先解决的问题。因为其对系统性能和可扩展性等方面都有重要的影响。本文介绍并分析了当前国内外的CC-NUMA系统在解决Cache一致性问题上所采用的几种协议以及其在系统性能和可扩展性方面所存在的不足之处。针对这些不足,提出了一种应用于CC-NUMA系统的基于两级目录协议的目录-数据Cache结构。具体而言,即是在CC-NUMA的目录存储器（第二级目录）上增加一个目录Cache（第一级目录）,其中第一级目录使用有限（Limited）目录协议,第二级目录使用全映射（full- map）目录协议。文中称此为两级目录协议。同时通过对目录Cache进行字扩展的方式,在共享数据存储器层上增加了一个数据Cache层,文中称此Cache结构为基于两级目录协议的目录-数据Cache结构。另外,为了避免出现目录项溢出问题,又设计了一种名为共享加权LRU的Cache替换算法。然后从系统性能以及可扩展性方面,分析比较了两级目录与全映射目录和有限映射目录在空间复杂度的优劣。证明两级目录在空间复杂度较有限映射增加很小的代价下,其性能接近或超过了全映射目录。同时又有效避免了制约有限目录性能的目录项溢出问题。最后使用通用的测试程序对共享加权LRU算法在Cache命中率方面,与经典LRU进行了对比测试。证明共享加权LRU算法在代价很小的前提下,保证了高共享数据处于Cache中,进一步降低了发生目录项溢出的概率。在此基础上,本文主要针对两级目录结构的设计思想,采用了硬件描述语言（VHDL）对其进行了逻辑实现和模拟仿真。首先,我们对基于两级目录的目录-数据Cache结构从功能上对其进行了模块划分,分配了每个模块所要完成的功能。其次,在认真分析模块与模块之间关联关系的基础上,详细描述了我们在设计与实现过程中的关键技术。第三,对所划分的模块采用硬件描述语言VHDL进行具体的设计与实验。第四,通过目录-数据Cache系统的性能分析实验,对基于两级目录的目录-数据体系的功能和整体性能进行了初步的模拟和测试。模拟和测试结果表明,应用于CC-NUMA系统的目录-数据Cache结构,有效地克服了系统性能以及可扩展性（scalability）与目录存储开销之间的矛盾,且能很好地解决Cache数据一致性的问题。而逻辑综合结果表明目录-数据Cache结构的实现复杂度低,硬件开销也相对较小,能够较好的满足CC-NUMA系统的需要。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 研究的来源及研究的意义
• 1.1.1 研究的来源
• 1.1.2 研究的意义
• 1.2 国内外研究现状
• 1.2.1 MIMD 系统的发展现状
• 1.2.2 典型CC-NUMA 系统
• 1.3 本文研究的目的和研究内容
• 1.3.1 本文研究的目的
• 1.3.2 本文研究的主要内容
• 1.3.3 论文的组织与结构
• 2 典型 MIMD 结构和 Cache 一致性协议
• 2.1 引言
• 2.2 MIMD 结构及分类
• 2.2.1 多计算机多个非共享存储器地址空间结构
• 2.2.2 多处理器单一共享存储器地址空间结构
• 2.3 CC-NUMA 结构的特点
• 2.3.1 CC-NUMA 简介
• 2.3.2 CC-NUMA 和NCC-NUMA, COMA, SC-NUMA 之间的差异
• 2.4 Cache 一致性协议简介
• 2.4.1 Cache 一致性问题的由来
• 2.4.2 写直达策略与写回策略
• 2.4.3 写失效协议与写更新协议
• 2.4.4 监听协议与目录协议
• 2.5 常见目录一致性协议的可扩展性研究
• 2.5.1 一致性协议对可扩展性的影响
• 2.5.2 全映射（full map）目录
• 2.5.3 有限（limited）目录
• 2.5.4 链式（chained）目录
• 2.6 本章小结
• 3 基于目录 Cache 的两级目录结构与共享加权 LRU 算法
• 3.1 两级目录结构思想的产生及其基本结构
• 3.1.1 两级目录结构思想的提出
• 3.1.2 两级目录结构的基本结构
• 3.2 两级目录结构的存储开销分析
• 3.3 基于两级目录的目录-数据 Cache 结构
• 3.3.1 目录-数据Cache 结构的提出和基本思想
• 3.3.2 四路组关联的目录-数据Cache 结构
• 3.4 共享加权 LRU 的 Cache 替换策略
• 3.4.1 共享加权LRU 的基本思想
• 3.4.2 共享加权LRU 的硬件实现
• 3.4.3 共享加权LRU 的性能分析及其对扩展性的影响
• 3.4.4 共享加权LRU 的Cache 命中率测试
• 3.5 本章小结
• 4 基于两级目录结构的CC-NUMA 结点间的一致性操作
• 4.1 访问远程数据而引起的一致性操作
• 4.2 用于节点间一致性通信的特殊命令字
• 4.2.1 远程结点对宿主结点的请求命令字
• 4.2.2 宿主结点对远程结点的响应命令字
• 4.2.3 宿主结点对远程共享结点的请求命令字
• 4.2.4 远程共享结点对宿主结点的响应命令字
• 4.3 宿主结点存储器以及远端高速缓存行的状态转换关系
• 4.3.1 宿主结点存储器目录项的状态转换关系
• 4.3.2 宿主结点存储器目录项的状态转换关系
• 4.4 Cache 一致性操作的具体操作举例
• 4.4.1 对污染的远程高速缓存行的读操作
• 4.4.2 对远程高速缓存行的写操作
• 4.5 本章小结
• 5 目录-数据 Cache 的 VHDL 硬件实现
• 5.1 目录-数据 Cache 的设计思想
• 5.2 目录-数据 Cache 的模块设计
• 5.3 目录-数据 Cache 的功能仿真测试
• 5.4 目录-数据 Cache 的 FPGA 逻辑综合
• 5.5 本章小结
• 6 结束语
• 6.1 本文工作回顾
• 6.2 后续研究工作的展望
• 致谢
• 参考文献
• 附录