计算机系统结构（2月10日）

多核Cache一致性协议

Cache Coherence问题提出：在多核和多处理系统中，多个Cache对应的copy内容应该一致

memory中的copy和cache中的copy应该是一致的

每个core有一个cache，多个cache共用一个memory

多个cache不一致的原因：

1、共享可写数据的不一致性（sharing of writable data）

2、进程迁移的不一致

包含共享变量x的进程原来在core1上运行，并对x进行了修改（但采取写回策略，所以暂时没有修改Memory），由于某种原因迁移到core2，修改过的x‘仍在core1的cache中，core2运行时从Memory中得到x，这个x其实是“过时”的，所以造成了不一致。

core2中运行的进程对x进行了修改，采取写通过策略，所以把memory中的x页修改为x’，由于某种原因，该进程迁移到core1，但core1的cache中仍为x，所以造成不一致

3、IO操作（绕过Cache的IO操作）

两种设计Cache一致性协议策略

1、写无效（write invalidate）

任一core写它的私有cache时，它都使所有其它的Cache中的副本失效

对Write-through,它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）

对write-back，它使memory中的副本也失效（最终只有一个cache中的副本是有效的）

2、写更新（write update）

任一处理器写它的私有Cache时，它都立即更新所有其它的Cache中的副本

对Write-through，它也更新主存储器中的副本

对Write-back，对存储器中副本的更新延迟到这个Cache被置换的时刻

从开销方面来说，写更新开销更大

写无效的问题：主要开销在两个方面：1、作废各Cache副本的开销；2、由作废引起缺失造成的开销，即处理机需要访问已经作废的数据时将引起Cache的缺失

如果一个core经常对某个块连续写，且Core间对共享块的竞争较小，这时写无效策略维护一致性的开销是很小的。如发生严重竞争，即Core之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比较大时，这种颠簸现象更为严重

写更新的问题：开销比较大

监听总线协议（Snoopy protocol）：通过总线监听机制实现cache与共享存储之间的一致性

适用性分析：适用于具有广播能力的总线结构多Core系统，允许每个Core监听其它Core的存储器访问情况。只适用于小规模的多Core系统

写一次（write-once）协议：写无效监听一致性协议，将写通过和写回策略结合。为了减少总线流量，高速缓存块的第一次写用写通过方法，产生一份正确的主存储器副本，并使其它的Cache中的副本无效，之后就采用写回方法更新Cache与主存储器

写通过：core将cache中的内容修改了，同时也将memory中这个副本也改了

1、一致性协议的内容：（1）Cache可能出现的状态集合；（2）共享主存的状态；（3）为维护一致性而引起的状态转换

2、每份Cache中的副本可能出现的四种状态：

（1）有效（valid state）：与主存储器副本一致的Cache副本，即该副本未经修改，所以这个副本不是唯一的副本

（2）保留（reserved state）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本一致

（3）重写（dirty state）：Cache副本不止一次被修改过，由于不再采用写通过方法，所以这个Cache副本是唯一的副本。与存储器和其他的Cache副本都不一致。主存储器中的副本也是无效的

（4）无效（invalid state）：与存储器或其他的Cache副本不一致，或在Cache中找不到

3、局部命令（Local commands）

（1）P-Read：本地处理机读自己的Cache副本

（2）P-Write：本地处理机写自己的Cache副本

4、一致性命令

（1）Read-blk：从另一Cache读一份有效的副本

（2）Write-inv：在写命中时在总线上广播一个无效命令

（3）Read-inv：在写缺失时在总线上广播一个无效命令

5、Write-Once一致性协议状态转移图

其中四种状态的含义如下：

Dirty：modified more than once，the only copy in the system

Invalid:inconsistent copy

Reserved:after written once, the only copy consistent with memory

valid:A copy consistent with the memory copy

有效状态，P-read，core去cache中读内容，仍然有效状态

有效状态，P-Write，第一次写，cache和主存内容一致，都被修改，状态变成reserved

再写一次，P-Write,写命中，cache变化，主存内容不变，状态变成dirty

再写一次，P-Write，写命中，cache变化，主存内容不变，状态仍然是dirty

cache中某一个block的状态

6、Write-Once一致性协议状态转移表

command current state next state status action

P-Read 有效 有效 Read-hit 必是局部进行，不影响有效状态

P-Write 有效 保留 Write-hit 第一次写命中，用写通过法。同时修改本地和主存副本，并广播Write-inv使所有副本失效

P-Write 保留 重写 Write-hit 第二次写命中，用写回法。但不修改主存的副本

P-Write 重写 重写 write-hit 第二次以后更多的写命中，用写回法，无状态改变

P-Write 无效 保留 Write-miss 写缺失时，则从主存或远程Cache送来副本。并广播Read-inv使所有其它副本无效

8、其它的一些问题

Core要向Cache写数据，如果write miss，表示该数据块不在Cache中或者该数据块处于无效状态，那么需要把正确的数据从memory或其它的Cache中取过来，然后再写操作

为什么不能直接写？（1）可能该数据块根本不在Cache中，所以需要从其它地方调入；（2）已在Cache中，但数据不正确，这时如果直接写入数据，整个数据块可能还是不正确的。例如，数据不正确的原因是100号单元数据已修改，如果要写入一个数据到101单元，这时不能直接写，否则100号单元还是错的

Cache Coherence问题概要：

多核或多处理机系统

共享存储器

Cache块的状态，即cache block状态

访问的数据是最新的，不是“过时”的内容

基于目录的Cache一致性协议：

目录的一般性问题：

Cache一致性协议的开销分析：

（1）采用写无效协议：无效后，当其它Core再读该副本时，出现Read miss，要有开销

（2）采用写更新协议：需要更新所有Cache和memory中的副本，所以开销大，有些Core对更新后的数据可能不会使用

基于目录的一致性协议的基本思想：

当Core个数增加时，一般不用总线结构，而采用多级互连网络。多级互连网络实现广播功能代价很大。

为什么需要广播功能？把一致性命令，如write-inv，read-inv等命令要发送给所有的cache

能不能只发送给存放该副本的Cache？——基于目录的协议的基本思想

3、目录的结构

（1）目录里放什么——有关Cache副本驻留在哪里的信息：所有共享数据块的所有Cache副本的地址表

（2）每个目录项（每个数据结构）包含若干个指向这个块（每个数据块有个目录项）的Cache副本地址的指针以及一个重写位（用来说明是否有一个Cache允许把有关的数据写入）

（3）基于目录的Cache一致性协议是依靠一个目录来记录系统之中哪些处理机的Cache中有指定存储块的副本。当一台处理机希望写某个共享块时，通过目录向该块的副本的那些处理机“点对点”的发无效信号，使所有其它的副本无效

4、目录的方式

（1）集中目录方式（中心目录）

1976年Tang提出。用一个中心目录存放所有Cache目录的副本，它能提供为保证一致性所需要的所有信息

缺点：容量非常大，必须采用联想方法来检查，冲突多，检索时间长

（2）分布式目录方式

5、三种目录

全映射（full map）目录：存放与全局存储器中每个块有关的数据。系统中的每个Cache可以同时存储任何数据块的副本，即每个目录项包含N个指针（N是Core数目）

有限（limited）目录：每个目录项有固定数目的指针（小于N）

链式（chained）目录：将目录分布到各个Cache（其余同全映射目录）

4、目录所占空间

假设存储器大小和Core个数N成正比，即个数增加时，存储器的模块数也增加，所以数据块的个数也和N成正比

另外目录项的大小也和Core数N成正比，所以目录的总所占空间和N平方成正比

即：目录项数×项大小 = O（N平方），太大不便于扩展

有限目录：解决目录过大的问题。任意一个数据块在Cache中同时存在的副本数量有一定限制，那么目录大小的增加不会超过一个常熟。

如果多Core系统中的Core具有局部性，即在任何给定的时间间隔内，只有一小部分Core访问某个给定的存储器字，那么有限目录足以应付这个小的工作Core组了

链式目录：

用目录指针链来跟踪共享数据副本。两种方法：单链法与双链法

数据块共享副本的数目并无限制

所占的空间及可扩展性同有限目录

目录占用的存储容量：指针的尺寸以Core数目的对数关系增长（这和有限目录相同）log（2）N，每个Cache块的指针数目与Core个数无关

解决Cache一致性的其它办法：

（1）不允许有私有Cache：Shared Cache方法

（2）可写的共享数据不存放在Cache中

三种Cache一致性策略

（1）采用Write-Through策略的Cache

数据块的两种状态：有效和无效（指本地Core相应数据块的状态，并非整个Cache的状态）

一致性的四种操作：Rr和Wr：其它Core对该数据块（指在其它CoreCache中的数据块）的读写；Rl和Wl：是本地Core对该数据块的读写

假设数据是有效的，先Rl命令，读命中，数据还处于有效状态；Wl命令，写命中，有效状态；Rr命令，没影响，仍然有效状态；Wr命令，收到无效命令，更新为无效状态

如果数据是无效的，先Rl命令，读缺失，从正确的地方读入数据，数据变成有效状态；Wl命令，写缺失，从正确的地方读入数据，数据变成有效状态；Rr命令，不影响，仍然无效状态

Cache的数据块为无效时，其它Core的任何操作都不会影响本地Cache的这种无效状态；只有在本地Core读或者写了数据块中的某个数据，即对Cache执行了Read或Write命令时，该数据块的状态才会成为”有效“

Cache的数据块为”有效“时：本地Core的读写操作，不会影响该状态；其它Core对存有相同内容的数据块读，不会影响该状态；其它Core对存有相同内容的数据块执行了写操作，该数据块状态变成无效

（2）采用Write-Back策略的Cache

数据块的三种状态

RO（只读）状态：表示整个系统中不止一个副本正确（例如一个在Cache中，一个在Memory中）

读-写状态：表示整个系统中，只有这个副本是正确的，其它都“过时”（即无效），这说明这个Cache的数据块至少被写过一次，但memory中的内容还没有被修改

无效状态：“过时”数据

一致性四种操作：Rr和Wr：其它Core对该数据块（指在其它CoreCache中的数据块）的读写；Rl和Wl：是本地Core对该数据块的读写

处于RO状态：本地读，远程读不会改变状态；本地写，使RO->R-W(这时只有一个数据块正确)；远程写，使RO->无效

处于读写状态：本地读，命中；本地写，命中；远程读，不命中，将数据从这个cache中读到远处cache，系统中不止一个副本正确；远程写，无效，将数据从这个cache中读到远处cache，再写，数据变成无效

本地读、写不会改变状态

远程读：这时只有这个Cache的数据块是正确的，所以要有“写回”动作（即把内容写回Memory），另外还需要把正确的数据传递给远程读的Core的相应的Cache

两个Cache的状态->RO

远程写：把本地Core的数据块传递给远程Core，远程Core对数据块进行写操作，远程Core对应的Cache状态变为RO，而本地的Cache变为无效状态

处于无效状态：Rr和Wr，与此cache无关，还是保持无效状态；Rl，不命中，正确的数据从旁边cache或主存拿过来，变成RO状态；Wl，不命中，正确的数据从旁边cache或主存拿过来，写后，变成W-R状态

采用Write-Once策略的Cache

Write-Through和Write-Back的缺点：Write-Through策略的弱点是每次都要修改memory，所以总线流量增大；Write-Back策略的弱点是Cache写了一次之后，Memory中的内容不一致

Write-Once的基本思想：把Write-Through和Write-Back两者的优点结合在一起：减少总线流量

Cache的第一次写采用Write-Through策略（有一个以上的副本正确）；Cache而后的写采用Write-Back策略（只有一份副本正确）。

为了区分是否是第一次写，把“读-写”状态分成两个状态：Reserved和Dirty

数据块的四种状态：

有效状态（Valid）：相当于Write-Back里的“只读”，从共享存储器中读入的并与存储器副本一致的Cache数据块

无效状态（Invalid）：在Cache中找不到或Cache中的数据块内容与共享存储器中的内容不一致的Cache数据块

保留状态（Reserved）：数据从共享存储器读入Cache只被写过一次。Cache中的副本与共享存储器中的副本是一致的，并且它是正确的副本

重写状态（Dirty）：Cache中的数据块不止一次被写过，此时共享存储器中的数据块也不是正确的数据块，唯一正确的数据块在Cache中

如果处于有效状态，Rl和Rr，命中，还是有效状态；Wl，命中，保留；Wr，接收无效命令，无效状态

本地读Rl，不影响状态

本地写Wl（第一次写），采用Write-Through策略，这时要发无效命令给其它Cache中相应的副本，并修改memory。有效变保留

远程写Wr（不管是第几次写），远程CPU会发无效命令：有效变无效

远程读Rr：不影响状态

如果处于保留状态：Rl，命中，不影响状态；Wl，命中，第二次写了，保留->重写状态；Wr，不命中，变成无效；Rr，不命中，传正确的数据过去，有效状态

本地读Rl，不影响状态

远程读Rr：这时Cache中只有处于保留状态的数据块是正确的，所以把该数据块送到远程Core的Cache中（远程Cache中该数据块变为有效），本数据块状态已变为有效

本地写Wl：第二次及以后的写，采取Write-Back策略，不修改Memory，状态由Reserved变为Dirty（这时只有一个副本有效），发无效命令给其它Cache的对应的副本，使Memory中的副本也无效

远程写Wr：远程Core会发无效命令，使状态由Reserved变为Invalid

如果处于“重写”状态：Rl和Wl，还是重写状态；Wr，不命中，接收无效命令；Rr，传正确的数据过去，有效状态

本地读Rl：不影响状态

本地写Wl：不影响状态

远程读Rr：这时只有这个Cache的数据块是正确的，所以把该数据块发送给远程的Cache，远程Cache的数据块和本Cache中的数据块都变得有效

远程写Wr：远程Core写后，发无效命令使状态由重写变成无效