多核并行体系结构-缓存一致性

缓存一致性简单介绍

缓存一致性的设计目标: 保证同一个数据在每个处理器中的私有缓存副本是相同的

基本的策略及关联性:

对于缓存的读, 不需要提供什么额外的一致性策略, 仅仅区分读命中和读不命中就好了, 而读不命中的策略即包含在了写策略中(需要对缓存进行更新)

缓存一致性策略讨论的主要是如何实现写传播策略和发送一致性消息使得各个缓存保持一致性

写策略

发送一致性消息

在各个缓存一致性协议的设计中, 均需要发送一致性消息让其他缓存感知到变化, 一致性消息的发送可以分为发送到所有缓存和发送到特定的缓存.

发送到所有缓存的,称为广播/侦听式协议

发送到特定缓存的, 称为目录式协议

基本的多处理器单元互联方式

基本的互联方式包含如下三种:

• 共享缓存

• 对称多处理器

• 分布式共享存储

• 共享缓存中不需要缓存一致性的支持, 但是对应的代价是处理器和缓存必须部署在非常近的距离之内, 并且互联网络必须提供很高的带宽

• 在实际应用中, 不同的层次可以由不同的组织方式互联, 比如一个「多个多核芯片」的系统, 多核芯片的内部可能的L2和L3缓存层可以采用共享缓存或者对称多处理器方式, 而在每个芯片之间可以采用DSM结构互联

总线的一些概念

从逻辑上分类, 总线有三种类型:

• 命令总线
• 数据总线
• 地址总线

从抽象层次看, 总线就是将所有处理器连接在一起的一组连线, 一个处理器与其他处理器通信时, 它先将地址, 命令和数据放在总线上, 然后其他处理器必须侦听总线, 检查是否传输了与之相关的数据.

总线事务的三个阶段

每个总线事务都需要经历三个阶段:

• 第一个阶段称为**“仲裁”, 这个阶段用来选择并授权一个端口使用总线, 总线仲裁的作用是避免来自不同处理器的请求在总线上发生碰撞**
• 第二个阶段称为**“命令传输”**, 是请求端口收到一个总线授权信号时, 其可以将目标地址放在地址总线上
• 第三个阶段称为**“数据传输”**, 是对第二个阶段的目标地址进行操作

扩展的总线一致性控制器

与单处理器系统中的总线和缓存相比, 基于总线的多处理器系统扩展了总线事务和缓存状态.

如图所示, 和单处理器不同之处在于:

• 每个缓存块的标签阵列部分增加了额外的位, 用于表示新的缓存状态
• 一致性控制器被添加到 「处理器侧 」和「 存储器侧」
  • 未决事务表记录者当前未完成的总线事务
  • 总线侦听器侦听每一个总线事务, 当侦听到总线事务时, 检索缓存的标签阵列, 查找是否有数据块与该总线事务有关, 然后进行输出数据块或者更改数据块状态等操作

基于总线的多处理器缓存一致性问题

1 | 写直达的缓存一致性协议

该方式为最简单的缓存一致性协议, 基于 写直达 + 写无效 + 写不分配 缓存构建

在此方案中, 缓存块状态包括:

缓存块状态	解释
Valid (V)	缓存块有效且干净 (与主存相同)
Invalid (I)	缓存块无效

由于在写直达中, 所有的写操作都是直接写入主存, 所以缓存块并没有"脏状态"

这里引入几个操作

处理器的操作:

处理器的操作	说明
PrRd	处理器读缓存块
PrWr	处理器写缓存块

总线侦听的操作:

总线侦听的操作	说明
BusRd	侦听到其他处理器 (主存 -> cache) 事件
BudWr	侦听到其他处理器 (处理器 -> 主存) 事件

其中左边表示处理器的请求 / 产生的总线侦听事件, 右边表示处理器响应总线侦听事件 / 产生的总线侦听事件

缺点

• 写直达缓存中, 每次写缓存都会触发BusWr从而占用总线带宽, 因为对缓存块的写入存在时间和空间的局部性, 在写回缓存如果出现多次缓存写入只需要占用一次总线带宽使其他缓存失效即可

2 | 写回的MSI协议

使用写回相比写直达的优势就是会大幅度减少总线的带宽开销

之后的部分总结内容均与上面类似, 首先是缓存块的状态包含:

缓存块状态	解释
Modified (M)	缓存块有效且(可能)和主存中数据不同, 并且该处理器有独占权
Shared (S)	缓存块有效且与其他处理器共享, 并且是干净的(和主存一致)
Invalid (I)	缓存块无效

处理器的操作	说明
PrRd	处理器读缓存块
PrWr	处理器写缓存块

总线侦听的操作:

总线侦听的操作	说明
BusRd	侦听到其他处理器 (主存 -> cache) 事件
BusRdX	侦听到其他处理器 (处理器 -> cache) 事件 (或者称为"读独占")
Flush	侦听到其他处理器 (cache -> 主存) 事件

关于Flush事务: 表示将缓存块放在总线上, 然后:

• 处理器侧(发出BusRd或者BusRdX的处理器应该接收该块并更新自己的缓存
• 主存侧应该更新该块对应的主存块

这时候可能就有人要问了, 如果是BusRdX事务, 为啥也需要Flush, 因为发出BusRdX即表示该处理器(发出者)已经重写了该块了, 那么不是直接将响应者由M状态改变为I就可以了吗?

答案:

不过该答案是否意味着: 处理器修改缓存块并不是以一整块为单位的, 而是可以修改和读取其中的一部分字节?

优点(相比于VI协议)

• 对写入带宽的需求很小, 如果一个带宽被重复写入多次, 不同于VI协议的每次都触发BusWr, 只会产生一个BusRdx, 剩下的写操作将在独占状态(M)下进行, 不会产生总线事务

缺点

• 如果有一个处理器希望读入一些数据块并对他们进行写入, 当这些数据块不存在于其他处理器缓存中时, 对于每一个读 - 写的操作序列, 将会触发两个总线事务:

  1. 读: 通过BusRd将块变为S状态 (对应左图I -> S)
  2. 写: 通过BusRdX来将块变为独占(使其他缓存失效) (对应左图 S -> M)

  注意BusRdx在此环境下是没有作用的, 因为这些数据块不存在与其他处理器缓存, 故写的时候其实并不需要发出独占事件, 但是其他处理器其实并不知晓这个前提条件.

  然而致命之处在于, 该场景是十分常见的, 因为多线程其实并不会共享很多的数据, 所以大部分缓存只保存在一个缓存块上, 因此大多数的BusRdX请求变得没有必要

一个潜在的一致性问题

在MSI一致性协议中, 很容易就可以从状态图中发现一个问题:

主存很有可能在块被Flush到主存之前就向其他缓存提供了主存当前存储的旧值

比如一个处理器1请求一块数据, 该数据被其他缓存独占且并未刷新到主存, 这时候应该先由PrRd触发总线读事务BusRd, 当拥有该缓存(处于M状态)的处理器2收到该事务后执行Flush将独占的数据写回主存, 然后由主存再将数据提供给处理器1

我们期望的顺序为

sequenceDiagram
	participant p1 as 处理器1 (Invalid)
	participant m as 主存
	participant p2 as 处理器2 (Modified)
	p1 ->> m: 请求数据
	p2 ->> m: FLush自己的数据
	m -->> p1: 提供最新的数据

然而这种期望如何保证正确的执行顺序呢, (书中给出了两种可以考虑采用的方案)

1. 在内存控制器答复块之前, 比处理器足够多的时间让它完成对总线的侦听的响应, 比如内存控制器已经从主存中拿到了一个块, 可以在确定没有缓存Flush之前将该块存在一个表里
2. 采用一种成为全侦听响应的方式, 引入一个特殊的"侦听完成"总线

一个对MSI协议在总线事务上的升级

注意到MSI协议中在内存控制器的角度来看, 其没有办法辨别发出BusRdX的控制器是拥有该缓存块了还是并没有需要从主存中去取

因此可以引入一个新的总线事务(操作/请求): BusUpgr

• 如果缓存已经有有了该块(S -> M), 则只需要更新权限, 不需要主存响应, 此时发出BusUpgr
• 如果缓存没有该块(I -> M), 则需要主存或者其他缓存提供, 此时发出BusRdX

3 | 写回的MESI协议

针对与MSI协议的缺点: 不论该块是否在一个缓存块上, MSI协议在读 - 写时都会触发两个总线事务

因此MESI协议加入了E状态(Exclusive)来区分缓存块是干净且唯一的还是干净且在多个缓存上拥有拷贝的

缓存块状态	解释
Modified (M)	缓存块有效且(可能)和主存中数据不同, 并且该处理器有独占权
Shared (S)	缓存块有效且与其他处理器共享, 并且是干净的(和主存一致)
Invalid (I)	缓存块无效
Exclusive (E)	缓存块干净有效且唯一

处理器的操作	说明
PrRd	处理器读缓存块
PrWr	处理器写缓存块

总线侦听的操作	说明
BusRd	侦听到其他处理器 (主存 -> cache) 事件
BusRdX	侦听到其他处理器 (处理器 -> cache) 事件 (该块已经被缓存)
BusUpgr	侦听到其他处理器 (处理器 -> cache) 事件 (该块还未被缓存)
Flush	侦听到其他处理器 (cache -> 主存) 事件 (从缓存到主存)
FlushOpt	侦听到其他处理器(cache -> cache) 事件 (从一个缓存到另一个缓存)

FlushOpt的存在是为了节约写入主存的操作的开销

注意: 缓存一致性控制器为了知道加载进缓存的块是E状态还是S状态, 增加了一个"C总线", 用来表示缓存块拷贝是否存在, 当缓存块拷贝存在时, 总线是高电平, 否则总线是低电平并且缓存块唯一

状态转移图: (还是基于写分配 + 写无效)

优点(相比于MSI协议)

提升了MSI协议的性能, 解决了MSI遇到的缓存块不存在拷贝时候的多事务开销

缺点

当一个缓存块被多个处理器连续地读写时, 每一个读操作都会触发干预, 需要拥有者Flush缓存块, 并且更新到主存其实是不必要的, 为了保持主存的干净(与缓存一致), 主存的更新操作过于频繁, 会消耗过多的带宽

因此我们期望能允许多个缓存之间共享脏块来避免对主存的频繁更新, 这就引出了下面的MOESI协议