目录设计
本章将介绍 huancun 中目录的设计。本章中所指的“目录”是广义的,包含元数据和 Tag。
huancun 是基于目录结构的 Non-inclusive Cache,在设计过程中受到了 NCID1 的启发。多级 Cache 之间,数据是 Non-inclusive 的,而目录则是 Inclusive 的。在结构组织上,huancun 将上层数据的目录与本地数据的目录分开存储,两者结构类似。目录使用 SRAM 搭建,以 Set 为索引,每一个 Set 中有 Way 路数据。
本地数据目录中每一项保存了如下的信息:
- state:保存该数据块的权限(Tip/Trunk/Branch/Invalid 中的一种)
- dirty:指示该数据块是否脏的
- clientStates:保存了该数据块在上层的权限情况(仅在该块非 Invalid 下有意义)
- prefetch:指示该数据块是否是被预取的
上层数据目录中每一项保存了如下的信息:
- state:保存该上层数据块的权限
- alias:保存该上层数据块的虚地址末位(即 alias bit,详见Cache 别名问题)
目录读取
当 MSHR Alloc 模块将一个请求分配进入 MSHR 时,它也会同时向目录发起读请求。并行读取上层与本地的元数据与 Tag,根据 Tag 比对判断是否命中,依命中情况将相应路的元数据传递到对应的 MSHR 中。
目录命中时,传递的路即为命中的路;目录未命中时,传递的路是根据替换算法得到的路。替换算法可灵活配置,南湖版本本地数据目录使用 PLRU 替换算法,上层数据目录使用随机替换算法。
目录写入
当 MHSR 事务处理接近尾声时,通常会需要写目录以更新状态、Tag 等信息。目录有 4 个写请求端口,分别接收本地元数据、上层元数据、本地 Tag 和上层 Tag 的写入。写请求的优先级高于读请求。
连接关系上,所有 MSHR 的上述 4 种写请求分开仲裁到目录中。其中,仲裁优先级关系被精心设计以避免发生请求嵌套错误或者死锁。
常见问题与设计考量
目录中已经有了上层元数据,为什么本地元数据中还会存 clientStates?
- 当一个请求,比如 Acquire BLOCK_A,在本地目录中 Miss 时,目录会根据替换算法选择一路的信息传递到 MSHR,此时这一路可能并不是无效的,而是有一个数据块 BLOCK_B。为了完成此 Acquire 请求,我们需要知道 BLOCK_B 在上层的状态信息。为了避免二次读目录,我们会在本地元数据中额外存一份 clientStates。
目录是否会出现读写竞争冒险?
- 我们的 MSHR 是按照 Set 阻塞的,且仅当 MSHR 释放后才会让新请求进入并读取目录,因此不会出现读写竞争冒险。
-
Zhao, Li, et al. "NCID: a non-inclusive cache, inclusive directory architecture for flexible and efficient cache hierarchies." Proceedings of the 7th ACM international conference on Computing frontiers. 2010. ↩