Last-Level Cache in Cache Hierarchy

• 访存往往是系统瓶颈
• 多核处理器会给访存系统带来更大压力：在芯片引脚数固定的情况下，需要传输的数据量急剧增多

访存系统设计的目标：最小化片外访存数

访存系统效率的影响因素：片上 caches 的访问延时和 hit rate

LLC 设计的趋势：

• 占据处理器芯片一半的面积
• 采用多 bank 设计，分散在各个芯片之间
• 访问时延取决于需要在片间传输的距离
• LLC 策略需要减少长距离的通信（可以使用开销较低的片上网络）

cache hierarchy 的主要分类：

1. shared vs. private
2. centralized vs. distributed
3. uniform vs. non-uniform access

根据 cache level 的不同，有的 level 采用 private 和 uniform access 设计，有的 level 采用 shared 和 non-uniform access 设计

cache hierarchy 的发展趋势：从两级 (L1, L2) 扩展到三级 (L1, L2, L3/LLC) ，且 LLC 的 hit rate, latency, complexity 都具有一定的优化空间

Shared vs. Private Cache

以 inclusive cache 为例

Shared LLC

Shared bus 实现（对应 snooping-based coherence protocol）

以 2 级 cache 系统为例

• 当核在 L1 Cache miss 时，将该请求发送到共享总线上，L2 Cache 会将请求从总线上取出并且进行必要的 lookup
• 每个存储块在 L2 Cache 中没有其他副本，但在 L1 中可能被缓存到不同的核的 L1 cache 中
• 如果 L1Dcache 采用 write-back 策略,
  当 core 0 发生 L1 miss，并将请求发送到总线时，其他 core 会检查自己的 L1 cache 中是否有对应请求块的副本
  • 如果 core 1 以 modified 状态持有该请求块，则 core 1 必须将请求块数据响应到总线
  • 如果没有 core 以 modified 状态持有该请求块，则 L2 cache 必须提供请求块(由 L2 cache 控制监听总线判断)
  • 如果请求是一次写请求，其他持有该请求块副本(非 modified 状态)的 L1 cache 需要将块置位 invalid 状态
• 如果 L1Dcache 采用 write-through / write-update 策略,
  • 所有的 L1 cache miss 都只能由 L2 cache 来处理
    • 导致显著的总线通信开销和能耗
• 适用于 核数不太多 的场景( $\le16$ )

Scalable network 实现（对应 directory-based coherence protocol）

以 2 级 cache 系统为例

• 每个 L2 block 对应一个目录，每个目录追踪当前 block 的副本存在于哪些 L1 cache 当中
• core 发生 L1 miss 会向 L2 cache 发送请求， L2 cache 根据目录追踪到当前拥有副本的其他 L1 cache，并向这些 L1 cache 发送 invalidate 信号以及获取数据的最新副本并更新
• 可扩展性强，可以扩展到更多核的情况

---

优点：

1. 总体 cache 空间的利用率较高
   • 数据存储空间在多核之间可以动态分配
2. L2 cache 的空间利用率高， hit rate 也会上升
   • 当数据被多核共享时， L2 cache 中只有一个数据副本
3. coherence miss 处理延时较短
   • 当数据被多核共享并且出现 coherence miss 时，必须遍历 cache hierarchy 直到遇到 coherence 接口或 shared cache

缺点：

1. 不同 core 的工作负载之间可能会互相影响，影响 miss rate
2. 大的 shared L2 cache 的平均访问延时较长
3. 一个 core 在访问被多核共享的数据时会导致很多竞争周期开销

Private LLC

以 2 级 cache 系统为例

• L1 miss 将由 private L2 cache 处理

Shared bus 实现（对应 snooping-based coherence protocol）

• L2 cache miss 时向总线发送请求，其他 core 的 private L2 cache 会监听总线
• 如果没有其他的 private L2 cache 响应，则请求会被发送下一级存储（L3 或主存）
• 延迟开销更大
  • 请求被发送到总线上之前会先在 private L2 cache 中 lookup
  • 总线监听时需要搜索的 tags 数量变多导致监听时间更长
  • 读取来自另一个 private L2 cache 的数据将花费更长的时间

Scalable network 实现（对应 directory-based coherence protocol）

• L2 cache miss 时向目录(分布式或集中式)发送请求
  • 目录必须追踪片上缓存的所有 blocks ，并且复制所有 private L2 caches 的 tags
  • 在保证 L2 cache inclusive 的情况下，L2 tags 包含了 L1 tags ，所以不需要复制 L1 tags
  • shared LLC 相当于将目录和每个 block 唯一的副本关联到一起，所以不需要保存 L2cache 的 tags

---

优点：

1. 不同核的工作负载之间将不会互相影响各自的 L2 cache
2. private L2 cache 比 shared L2 cache 小很多，平均访问时间也变短
3. 访问 private L2 cache 不需要遍历 coherence 接口（对于非共享数据的访问有性能提升）

缺点：

1. L2 cache 的空间利用率低
   • 多核共享的数据块将在多个核的 private L2 cache 中存在副本
2. L2 cache 的存储资源在各个核中相当于被静态分配
   • 由于不同核的负载的访存需求不同，可能进一步导致利用率低
3. coherence 接口将下降到更低的 cache 级别

Combination of shared and private LLC

private LLC 和 shared LLC 也可以结合起来

以 16-core 的 2 级 cache 系统为例

• 每 4 个核组成一个 cluster 共享一个 private LLC
• 每个 cluster 内部的 4 个核之间使用 snooping-based coherence protocol
• 4 个 cluster 的 private L2 之间使用 snooping-based coherence protocol

研究不同的多线程 workload 对 shared or private LLC 影响的工作：

1. A. Jaleel, M. Mattina, and B. Jacob. Last Level Cache (LLC) Performance of Data Mining Workloads on a CMP – A Case Study of Parallel Bioinformatics Workloads.
2. C. Bienia, S. Kumar, and K. Li. PARSEC vs. SPLASH-2: A Quantitative Comparison of Two Multithreaded Benchmark Suites on Chip-Multiprocessors.
3. B. Beckmann, M. Marty, and D. Wood. ASR: Adaptive Selective Replication for CMP Caches.
4. N. Hardavellas, M. Ferdman, B. Falsafi, and A. Ailamaki. Reactive NUCA: Near-Optimal Block Placement And Replication In Distributed Caches.

Centralized vs. Distributed LLC

Centralized LLC 和 Distributed LLC 主要针对 Shared LLC ，但 private LLC 也可采用

由于 L2 Cache 较大，可以采用分 bank 的设计来降低走线延时，由 L2 Cache 内的互连网络将请求传送到对应的 bank 上。

Centralized LLC

定义：LLC 在芯片上占据连续区域

互联网络的设计：

1. L2 cache 的互连网络和核间的互连网络分开
   • 每个核的请求需要通过集中式的 L2 控制器再通过互联网络传送到 L2 bank
2. L2 cache 的互连网络可以和核间的互连网络合并到一起:
   • 每个核的请求可以直接传递到相应的 L2 bank 中
   • 但每个 L2 Bank 需要添加相应的 snooping 控制逻辑（相当于将集中式的 L2 控制器为每个 bank 复制了一份）

使用 snooping-based coherence protocol 实现的 Centralized LLC:

使用 directory-based coherence protocol 实现的 Centralized LLC:

• 优点：
  1. 简化了 bank 间的数据搬移
  2. 简化了 bank 间以及和下一级存储间的互联
• 缺点：不适用于核数较多的设计
  • 结温和互联网络(可扩展性和线长)的限制

Distributed LLC

定义：LLC 的每个 bank 和一个核或者一组核在物理布局上紧耦合在一起

典型布局：L2 的每个 bank 和每个核(以及 L1 cache) 布局到一起，称为一个 tile ，由片上网络连接所有的 tile

分 tile 的 Distributed LLC 的 2 级 cache 系统典型布局:

• L1 miss 时，请求会通过片上网络路由到具有相应数据块的 L2 bank 所在的 tile
• 优点：设计和验证具有可扩展性
  • 可以设计单个 tile ，制造时实例化面积预算下尽可能多的 tile
• 缺点：L2 bank 间以及和下一级存储之间的数据移动代价较大

private LLC cache 的物理布局本身就类似于 distributed shared LLC cache ，都是一个 tile 包含一个 LLC bank ，区别在于 LLC 如何管理和组织数据（LLC cache 空间是共享还是私有）

Uniform vs. Non-Uniform LLC

Uniform Cache Access (UCA)

• cache 访问所有 block 的延时都是相同的，都是最坏情况下的延时
• 当核内流水线需要知道 cache hit latency 时，可以简化流水线指令调度逻辑

UCA 分 bank 设计采用 H-tree 拓扑 ：

• 每一个 bank 从 cache 控制器看都是等价的，因此使得每一个 bank 的访问时间都是相同的
• 每个请求都是从 cache 控制器发出到指定的 block

Non-Uniform Cache Access (NUCA)

鼻祖：Kim
C. Kim, D. Burger, and S. Keckler. An Adaptive, Non-Uniform Cache Structure for WireDominated On-Chip Caches. In Proceedings of ASPLOS, 2002.

• cache 访问不同 block 的延时不同
• 在分 Bank 的设计中，针对不同 Bank 的访问延时不同

架构可行性：

1. 如果核内流水线不会基于 L2 cache 访问时间调度流水线，那 L2 cache 访问时间不同就是可接受的
2. 采用 网格状拓扑结构 连接 cache 控制器和各个 bank
   • bank 的延时是其大小和需要路由请求数量的函数
   • 网格上的请求模式很不规律，需要复杂的机制支持路由和流控制
   • 需要复杂的片上网络来处理 core 和 cache bank 之间的仲裁
   • 在分 tile 架构中，不同 cache block 的延时取决于网络距离

Physical Design

以一个核心的连接为例：

两种物理实现方式：

1. 每个 cache bank之间以及和 cache 控制器之间采用专用的通道
   • 每次访问冲突更低，路由开销更低
   • 专用通道对金属布线的要求太高，以至于不可行
   • 不具有可扩展性
2. 采用网格拓扑的片上网络
   • 确保金属布线开销可以接受
   • 提供相对较高的带宽和较低的冲突
   • 具有可扩展性

Logical Policies

对于数据的管理，需要解决的问题：

1. Mapping: 一个数据块可能存放的位置
2. Search: 定位一个数据块需要的机制
3. Movement: 改变一个数据块位置需要的机制

Mappnig

策略1: Static-NUCA or S-NUCA
cache 的sets 放在不同的 bank 中，一个 set 的所有 way 放在同一个 bank

• block 地址和相应的 cache index 域足以定位到 set 所在的 bank
• block 到 bank 的映射唯一
• 不需要用于搜索数据块的机制
• 不需要在 bank 之间移动数据

策略2: Dynamic-NUCA or D-NUCA
cache 的 set 和 way 放在不同的 bank 中

• 必须定义相应的策略确定在访问该块时块的位置
• 需要在不同的 way 之间移动数据块以最小化平均访问时间
• 需要一种搜索机制来快速定位可能位于 W 个 bank 中的某个块

Search

针对 D-NUCA

1. incremental: 以渐近的方式搜索
   1. 首先查找最近或最可能的 bank
   2. 如果找不到，则继续找下一个最近或最可能的 bank
2. multicast: 将请求发给所有的 bank, 同时进行搜索
   • 在不导致更多网络竞争的情况下，可以提高性能
   • 显著增加功耗
3. incremental + multicast
   1. 对最可能的 N 个 bank 同时搜索
   2. 如果找不到，继续对接下来最可能的 N 个 bank 同时搜索
4. Smart Search: 每个 block 的部分 tag 存储在 cache 控制器中，查找前首先根据这些 tag 定位到某些 bank (缩小搜索范围)，然后对这些 bank 进行搜索
   • 单核性能较好（所有 block 的替换都通过 cache 控制器）
   • 多核扩展性较差（这些标签需要在每个核的 cache 控制器中冗余维护）

在 D-NUCA 实现高效的搜索依旧是一个问题！

Movement

目的：使频繁访问的数据块移动到更加靠近 cache 控制器的 bank 中

Generational Promotion:

• cache miss 时，数据块会被放到最远的 bank 中
• 后续该块每次 hit 时，和相邻 bank 交换位置，逐渐靠近 cache 控制器

---

• NUCA cache 比 相同大小的 UCA cache 和多级 cache 性能更优
• D-NUCA cache 比 S-NUCA 的性能高 10% 左右 (引入智能搜索后，17%)
• Futurn Research: 结合 S-NUCA 和 D-NUCA

Exclusive/Non-Inclusive vs. Inclusive LLC

Inclusive Hierarchy

定义：
如果 L1-L2 层是 inclusive, 则 L1 的每一个 block 在 L2 中都有一个副本

• 当一个 block 被踢出 L2 时，L1 中对应的 block 也要被踢出
• 多核共享 L2 时，所有核的 L1 中相应的 block 都要被踢出

优势：

• 当 L1 miss 时，可以很容易定位到数据块：要么在 L2 中，要么在 L2 指向的某个 L1 的 modified block
• 当 L2 miss 时，请求可以直接发送给下一级存储

缺点：浪费空间（所有 L1 blocks 在 L2 中都有冗余存储）

Exclusive / Non-Inclusive Hierarchy

Exclusive 定义：一个数据块只能存在于 L1 或者 L2 ，不能同时存在于二者

Non-Inclusive 定义：不保证 L1 中的数据块在 L2 中有副本

优点：整体 caches 空间利用率高（几乎没有 cache block 重复）

缺点：数据搜索比较复杂：

• L1 miss 时，需要搜索其他 L1 caches 和 L2 cache
• 对于 snooping-based coherence 而言，不会显著增加开销，因为本身就会广播搜索
• 同 snooping, 可扩展性较差

---

write policy: (write-through vs. write-back)

• Inclusive Hierarchy 都可以兼容这两种策略
• write-through 性能更好，但对互联带宽和功耗预算要求较高
• write-back 更加适用于 Exclusive / Non-Inclusive Hierarchy.