xixi's blog

life is so beautiful!

0%

Cache Coherence Protocols

Posted on In , ,
cache 一致性协议简介

Baseline System Model

coherence_baseline

每个 cache block 有两个 coherence 状态:

  1. I(nvalid): 在 LLC 中表示所有的 cache 对于该 block 都是 I.
  2. V(alid): 在 LLC 中表示有一个 cache 对于该 block 的状态是 V
  3. $IV^D$ (瞬时状态): 状态 I 转换为 状态 V 的过程中的等待数据响应的瞬时状态

bus messages:

  1. Get: 请求一个 cache block
  2. DataResp: 传输 block 的数据
  3. Put: 将 block 写回到 memory controller

cache controller 的行为:

  1. 发生 load/store miss 时， 触发一次 Get transaction: 发送一个 Get message 并等待响应的 DataResp message(该 transaction 是原子的，等待响应过程中不可有其他 transaction)
  2. Evict Block 时，发送 Put message

simple_protocols

Cache controller specification:

States Core Events BusEvents
Message for Own Transactions Message for Other Cores' Transactions
Load / Store Evict Block Own-Get DataResp for Own-Get Own-Put Other-Get DataResp for Other-Get Other-Put
I Issue Get / IV^D
IV^D Stall Load and Store Stall Evict Copy data into cache ,perform Load or Store / V
V Perform Load or Store Issue Put / I Send DataResp / I

Memory controller specification:

States BusEvents
Get Put
I Send data block in DataResp message to requestor / V
V Update data block in memory / I
  • 优点: 简单
  • 缺点: 不够高效

Cache Coherence Protocols 设计空间

选择因素：

  1. stable states 稳定状态: 和其余因素, protocols 本身的实现独立
  2. transaction : 和特定的 protocol 独立
  3. events
  4. transitions

stable states 和 transaction 与具体的 protocols 独立，而 events 和 transitions 则高度依赖于 coherence protocols

States

单核系统:
只需要两个状态： valid, invalid (对于 write-back cache, 还需要 dirty 标记是否是脏块)

多核系统，有四个需要被编码的特征：

  1. Validity: valid block 并且拥有该 block 最新的值，可读 ，在 exclusive 时还可写
  2. Dirtiness: 同单核系统一致, block 被写入新数据，而下级 Cache 保留的是写入之前的数据时为 dirty
  3. Exclusivity: 当 block 为系统中唯一的私有 cache 的 block 副本 (其他同级 cache 没有该 block)时，称该 block exclusive.
  4. Ownership: coherence controller 为一个 block 的 owner 当该 controller 负责响应针对该 block 的请求
    • 在大多数 protocols 中，一个给定的 block 只有一个 owner
    • owner 中的 block 不会由于冲突被替换出 cache

Cache Block States

Stable States 稳定状态

大多数 coherence protocols 使用的 stable states 都是 MOESI 状态的子集，最基础的状态为 MSI 状态。

M(odified):
block 处于 valid, exclusive, owned, potentially dirty等状态, block 可能被读写， 当前 cache 拥有该 block 唯一 valid 副本(exclusive), cache 必须响应对该 block 的请求(owned), LLC 中关于该 block 的数据也可能已过时(potentially dirty)。

O(wned):
block 处于 valid, owned, potentially dirty等状态, 但是 not exclusive, 当前 cache 拥有该 block 的只读副本，其他 cache 可能也有只读副本，但他们不是 owner，cache 必须响应对该 block 的请求(owned), LLC 中关于该 block 的数据也可能已过时(potentially dirty)。

E(xclusive):
block 处于 valid, exclusive, clean等状态, block 可能被读写， 当前 cache 拥有该 block 唯一 valid 只读副本(exclusive), LLC 中关于该 block 的数据也是最新的(clean)。

S(hared):
block valid,但是 not exclusive, not owned, not dirty, 当前 cache 拥有该 block 的只读副本（其他 cache 可能也有）

I(nvalid):
block invalid. 当前 cache 要么不包含该 block ，要么包含该 block 的过时的数据（不可读写）

moesi_state

在具体的系统实现中，每个 cache line 都需要增加相应的 field bits 以维护 coherence state

MOESI 状态第一次提出:
P. Sweazey and A. J. Smith. A class of compatible cache consistency protocols and their support by the IEEE Futurebus. In Proc. of the 13th Annual International Symposium on Computer Architecture, pp. 414–423, June 1986. DOI: 10.1145/17356.17404. 97, 98

Transient States 瞬时状态

从一个 stable state 转换到另一个 stable state 的过程中会存在 transient state 瞬时状态，记为 $XY^Z$ 表示状态在从 X 状态转换为 Y 状态的过程中直到事件 Z 发生转换结束。

在具体的系统实现中，也需要相应的 field bits 以维护这些 transient states ，但是往往通过 MSHRs 或者类似的结构来追踪瞬时状态

LLC/Memory Block States

有两种约定方式：

  1. LLC/Memory Block State 是 Cache Block State 的聚合
    • 如果所有 cache 中该 block 都处于 I 状态， 那么该块在 LLC/Memory 中的状态也为 I
    • 如果有一个 cache 中该 block 处于 S 状态， 那么该块在 LLC/Memory 中的状态为 S
    • 如果只有一个 cache 中存在该 block 且处于 M 状态， 那么该块在 LLC/Memory 中的状态为 M
  2. LLC/Memory Block State 对应 memory controller 对 block 的访问权限
    • 如果所有 cache 中该 block 都处于 I 状态， 那么该块在 LLC/Memory 中的状态为 O
    • 如果有一个 cache 中该 block 处于 S 状态， 那么该块在 LLC/Memory 中的状态为 O
    • 如果只有一个 cache 中存在该 block 且处于 M 状态或者 O 状态， 那么该块在 LLC/Memory 中的状态为 I

对于单个多核芯片下的 inclusive LLC ，并不需要显式地指定 coherence state ，如果 block 不在 LLC 中，隐式状态为 I. 但对于多个多核芯片，则需要显示指定 LLC 的 coherence states.

多核芯片出现以前对于 memory block state 的维护:

  1. Augment Each Block of Memory with State Bits
    • 为每个 cache block 增加额外的 bits 以维护 coherence states
    • 优点：通用且直观
    • 缺点：
      • 带来一定的存储开销 (可以通过维护更大的 block 粒度比如 512 bits 来减少存储开销)
      • 每次获取 coherence state 都需要访问一次内存，延时较大
      • 所有的状态转换都需要内存 (DRAM) 进行一次 “读-修改-写” 会影响 DRAM 的功耗和带宽
  2. Add Single State Bit per Block at Memory
    • 仅仅使用两个状态 valid and invalid (1 bit) 来维护 coherence state
  3. Zero-bit logical OR
    • 通过所有 cache 对于某个 block 的 coherence state 聚合起来表示 memory 对于该 block 的状态

Transactions 状态转换事件

大部分 protocols 采用的是相同的 transactions

Common Transactions from Cache Controller:

Transaction Goal of Requestor
GetShared (GetS) Obtain block in Shared (read-only) state
GetModified (GetM) Obtain block in Modified (read-only) state
Upgrade (Upg) Upgrade block state from read-only (Shared or Owned) to read-write (Modi
PutShared (PutS) Evict block in Shared state
PutExclusive (PutE) Evict block in Exclusive state
PutOwned (PutO) Evict block in Owned state
PutModified (PutM) Evict block in Modified state

Common core requests to Cache Controller:

Event Response of (Typical) Cache Controller
Load cache hit 则使用来自 cache 的数据响应; 否则生成 GetS transaction
Store cache hit in state E / M, 将数据写入 cache; 否则生成 GetM / Upg transaction
Atomic read-modify-write cache hit in state E / M , 则原子地执行 RMW 操作; 否则生成 GetM / Upg transaction
Instruction fetch cache hit (in I-cache), 使用来自 cache 的指令响应; 否则生成 GetS transaction
Read-only prefetch cache hit, 忽略; 否则可能有选择地生成 GetS transaction
Read-Write prefetch cache hit in state M, 忽略; 否则可能有选择地生成 GetM / Upg transaction
Replacement 取决于 block 的状态, 生成 PutS / PutE / PutO / PutM transaction

Protocols Design

coherence protocols 主要有两大类:

  1. Snooping protocol
    • cache controller 通过向所有其他 coherence controller 广播请求来生成针对某一个 block 的请求
    • 通过共享总线互联网络实现广播，要求总线上请求满足 total order
    • 逻辑简单，但 not scalable
  2. Directory protocol
    • cache controller 通过将请求单播给某一个 block 所属的 memory controller 来生成针对该 block 的请求
    • memory controller 维护一个目录来管理识别所有 block 的 owner 和 sharers
    • scalable 但请求延时较长，会发送额外的 message##
  3. Hybrid Designs
    • P. Conway and B. Hughes. The AMD Opteron northbridge architecture. IEEE Micro, 27(2):10–21, March/April 2007. DOI: 10.1109/mm.2007.43. 105
    • M. M. K. Martin, D. J. Sorin, M. D. Hill, and D. A. Wood. Bandwidth adaptive snooping. In Proc. of the 8th IEEE Symposium on High-Performance Computer Architecture, pp. 251262, January 2002. DOI: 10.1109/hpca.2002.995715. 105

根据 core 如何写入 block, 也可以分为两类:

  1. Invalidate protocol
    • 一个 core 写入一个 block 时，生成 transaction 将其他所有核响应的 block 都invalidate
    • 实现更简单
  2. Update protocol
    • 一个 core 写入一个 block 时，生成 transaction 将新值更新到其他所有核的 block 中
    • 其他核读取新值的延时会降低，不需要再重新请求 block
    • 会消耗大量的带宽 (update message 要比 invalidate message 要大)
    • 实现更加困难（写原子性的保证更难实现）
  3. Hybrid Designs
    • A. Raynaud, Z. Zhang, and J. Torrellas. Distance-adaptive update protocols for scalable shared-memory multiprocessors. In Proc. of the 2nd IEEE Symposium on High-Performance Computer Architecture, February 1996. DOI: 10.1109/hpca.1996.501197. 105