Fork me on GitHub

yangLieee
0%

缓存一致性协议

发表于 更新于 分类于 ， Valine：
本文字数： 3.2k 阅读时长 ≈ 3 分钟
对缓存一致性协议进行深度探索并对MESI协议做具体分析

导语 - cache、主存与CPU的通信

image

如图所示，私有Cache是每个处理器核心所特有的比如L1、L2，共享 Cache是所有处理器核心的共享缓存比如L3，而整体Cache与主存的数据交互是要通过总线进行的。当两个核加载了主存的同一块缓存副本，其中一个核进行了数据的更改，是否要写入主存？是否要通知给其它CPU核心进行修改？因此对于多核CPU来讲，缓存在提高效率的同时也带来了缓存一致性的问题，而这个问题是需要进行解决的

核心需求

缓存一致性核心核心需要解决的问题就是：将本CPU更新的数据有效的传播到其它CPU本地缓存中

进一步可以总结成需要遵从两个特性

  1. 写传播：CPU Core的对内存的写操作，其它CPU Core可见
  2. 事务串行化：其它CPU Core看到的内存的写操作的顺序是一致的

写传播可以保证修改的数据能够传播给其它CPU，而事物串行化则保证数据在其它CPU内的正确性。比如CPU有3个Core，Core1将x修改为3，Core2将数据修改为5，两个事务需要同步到Core3同时Core1 Core2互相同步，如果不保证串行，最终的数据很大概率是错误的

基础知识

总线嗅探

嗅探一致性协议

总线除了能在一个主模块和一个从模块之间传输数据，还支持一个主模块对多个从模块写入数据，这种操作就是广播。

写传播的原则就是当某个 CPU 核心更新了 Cache 中的数据，要把该事件广播通知到其他核心，最常⻅实现的方式是总线嗅探(Bus Snooping)。当某个CPU Core的缓存行有更新时，需要将所有的读写操作广播到所有 CPU Core，而虽然总线上其它CPU Core的私有缓存不一定有对应的缓存行，但也要时刻监视或侦听总线，以验证它是否具有所请求数据块的副本，如果存在使对应的缓存副本失效或更新。使用广播的方式看似一视同仁，实际这样做大大增加了总线的负担。

Directory-based 机制

基于目录的缓存一致性协议

针对总线嗅探的缺点，Directory-based 机制采点对点的传播，基于目录机制总线事件只会传给自己感兴趣的CPU。这是因为所有缓存行的信息，都被记录在 directory 中。比如会记录每个缓存行当前都在那些核的缓存中，直接将缓存行修改的消息发送到那些核。这么做的也有个缺点是每次总线的传输都到 directory 做一次检查，产生耗时。

总线仲裁

总线的独占性要求同一时刻最多只有一个主模块占用总线，天然地会将所有核心对内存的读写操作串行化。如果多个核心同时发起总线事务，此时总线仲裁单元会对竞争做出仲裁，未获胜的事务只能等待获胜的事务处理完成后才能执行。对于写缓存来讲，多核并发的写事件会通过总线仲裁机制转换成串行化的写事件序列

缓存写策略

  • 写分配 Write Allocate：要写入的数据不在缓存中，需要将该数据对应的内存块读入缓存；
  • 写不分配 Write Not Allocate：要写入的数据不在缓存中，无需将该数据对应的内存块读入缓存，而是直接写入主存；
  • 写穿 Write Through：写入缓存到的数据立马传播到主存；
  • 写回 Write Back：写入缓存的数据不会立马传播到主存，而是该缓存块被替换时才更新；
  • 写更新 Write Update：每次缓存写入新值，发起一次总线请求，通知其它CPU如果拥有该缓存块的副本就更新为新的值（需要传新的值）
  • 写无效 Write Invalid：每次缓存写入新值，发起一次总线请求，通知其它CPU如果拥有该缓存块副本置为无效状态，如果未来需要在来要新的值（不需要传新的值）

缓存一致性协议种类

该表格翻译自 Snooping vs. Directory Based Coherency

名字 协议类型 内存写策略 应用
Write Once 写无效 第一次写之后写回 First snoopy protocol
Synapse N+1 写无效 写回 1st cache-coherent MPs
Berkeley 写无效 写回 伯克利 SPUR
Illinois 写无效 写回 SGI Power and Challenge
“Firefly” 写广播（写更新) 写回私有，写穿共享 SPARCCenter 2000
MESI 写无效 写回 奔腾，PowerPC

MESI协议

简介

通过缓存一致性协议的种类核应用场景来看，MESI应用在Intel奔腾处理器和PowerPC上，可以说有着很广泛的应用了。

MESI是四个单词的首字母缩写（Modified，Exclusive，Shared， Invalid），这四个单词代表了四种状态。因此可以缓存行可以用2bit来唯一表征这四种状态的某一种状态。

  • M：Modified，被修改的（也可以称为Dirty 脏的）。当前CPU对应的该缓存行数据被修改，拥有最新数据（private, != Memory）
  • E：Exclusive，独享的。该缓存行只存在于当前CPU中，并且数据有效（干净）(private, =Memory))
  • S：Shared，共享的。该缓存行也存在于其它CPU中，并且数据有效（干净）(shared, =Memory)
  • I：Invalid，无效的。当前CPU内的该缓存行数据失效(NULL)

状态机

本部分基于进行重新梳理

来自处理器的请求

  • PrRd：处理器请求读一个缓存块
  • PrWt ：处理器请求写一个缓存块

image

  • M：唯一且数据！=memory（最新数据）。读写依然是最新数据（！= memory）

  • E：唯一且数据=memory。读不影响状态，写则与主存数据不一致置M

  • S：共享且数据=memory。读不影响状态，写则将拥有最新数据置M，同时产生总线事务通知其它处理器要写该缓存

  • I：无效的，一定Cache Miss。读首先将数据加载进缓存，产生BusRd的总线事务，内存控制器响应请求，同时如果发现其它处理器也拥有该缓存块副本则置S，如果没有置E；写则产生BusRdx的总线事务，由于拥有最新数据状态置M

来自总线（其它处理器）的请求

  • BusRd：总线侦听到其它处理器请求读一个缓存块

  • BusRdX：总线侦听到其它处理器请求写一个自己没有缓存副本的缓存块

  • BusUpgr：总线侦听到其它处理器请求写本地缓存（该处理器拥有的缓存块）

  • Flush：总线侦听到其它处理器请求写回一个缓存块到主存（cache to memory）

  • FlushOpt：总线侦听到其它处理器请求将一个缓存块通过总线的方式发送另外一个处理器（cache to cache）

    image

  • M：唯一且数据！=memory（最新数据）。 BusRd说明其它处理器要读，则需要写传播将数据写到主存，因为其它处理器读所以数据=memory且共享置状态S；当BusRdx或BusUpgr说明其它处理器要写，这两种情况无论发起请求的处理器有没有缓存一定不是最新的所以一定产生Flush的总线事务，并且其它处理器写完就不是最新的了置I

  • E：唯一且数据=memory。BusRd说明其它处理器要读，我的数据已经是最新的了所以产生FlushOpt总线事务，将该缓存块传走并置状态S；其它处理器写最终结果一定是我的私有缓存无效置I，但是如果发起总线事务的处理器没有该缓存我需要产生FlushOpt的总线事务将数据传输，否则不产生总线事务

  • S：共享且数据=memory。BusRd说明其它处理器要读，我的数据是最新的了所以产生FlushOpt总线事务，将该缓存块传走保持S状态；其它处理器写最终结果一定是我的私有缓存无效置I，但是如果发起总线事务的处理器没有该缓存我需要产生FlushOpt的总线事务将数据传输，否则不产生总线事务

  • I：无效的。各种读写情况都不会影响，继续保持状态

参考资料