[5]Cache一致性

1、北京科技大学计算机系李建江参考课件：清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授第五章 Cache Coherence5.1 Cache Coherence问题5.1.1 Cache Coherence的提出5.1.2 多个Cache不一致的原因5.1.3 两种设计Cache一致性协议策略5.2 监听总线协议5.3 基于目录的Cache一致性协议5.4 三种Cache一致性策略5.1 Cache Coherence问题 5.1.1 Cache Coherence问题的提出 在多处理器系统中，多个Cache中，对应的copy内容应该一致，如下图：MemoryCachePCachePC

2、acheP这几个copy应该一致5.1.2 多个Cache不一致的原因 1.共享可写数据的不一致性（sharing of writable data）P1P2更新前xxx处理机CachesharedmemoryP1P2写通过xxxP1P2写回xxx2.进程迁移的不一致性P1P2迁移前xx处理机CacheP1P2写通过xxxP1P2写回xxxsharedmemory上图中： 右图为：包含共享变量x的进程原来在P1上运行，并对x进行了修改（但采取写回策略，所以暂时没有修改Memory），由于某种原因迁移到P2，修改过的x仍在P1的Cache中，P2运行时从Memory中得到x（因为缺失），这个x其

3、实是“过时”的，所以造成了不一致。 中间图为：P2中运行的进程对x进行了修改，采取写通过策略，所以把Memory中的x也修改为x，由于某种原因该进程迁移到P1，但P1的Cache中仍为x，所以造成不一致。3. I/O操作（绕过Cache的I/O操作）P1P2xx存储器P1P2写通过xxP1P2写回xxxxxxxI/O存储器输入存储器输出c1c2总线上图中： 中间图为：当I/O处理机将一个新的数据x写入主存储器时，绕过采用写通过策略的cache，则C1和共享存储器之间产生了不一致。 右图为：直接从主存储器输出数据时（绕过Cache），采用写回策略的高速缓存产生不一致性。5.1.3 两种设计Cac

4、he一致性协议策略 1.写无效（write invalidate） 任一处理器写它的私有Cache时，它都使所有其它的Cache中的副本失效。 对Write-through，它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）。 对Write-back，它使memory中的副本也失效（最终只有一个Cache中的副本是有效的）。2.写更新（write update） 任一处理器写它的私有Cache时，它都立即更新所有其它的Cache中的副本。 对Write-through，它也更新主存储器中的副本。 对Write-back，对存储器中副本的更新延迟到这个Ca

5、che被置换的时刻。3. 示意图 下图表示数据块x在共享存储器和三台处理机的Cache中的副本一致的情形。x共享存储器CacheP1xP2xxP3总线处理机 下图表示P1进行写无效操作后的情形。写通过：xI表示无效P1IP2xIP3写回：xI表示无效P1IP2IIP3 下图表示P1进行写更新操作后的情形（写通过）。xI表示无效P1xP2xxP34.写无效的问题主要开销在两个方面： （1）作废各Cache副本的开销； （2）由作废引起缺失造成的开销，即处理机需要访问已经作废的数据时将引起Cache的缺失。 后果： 如果一个处理机经常对某个块连续写，且各处理处理机间对共享块的竞争较小，这时写无效策

6、略维护一致性的开销是很小的。如发生严重竞争，即处理机之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比较大时，这种颠簸现象更为严重。5. 写更新的问题 由于更新时，所有的副本均需要更新，开销很大。第五章 Cache Coherence5.1 Cache Coherence问题5.2 监听总线协议5.2.1 写一次协议5.3 基于目录的Cache一致性协议5.4 三种Cache一致性策略5.2 监听总线协议(Snoopy protocol) 通过总线监听机制实现Cache和共享存储器之间的一致性。适用性分析： 适用

7、于具有广播能力的总线结构多机系统，允许每台处理机监听其它处理机的存储器访问情况。 只适用于小规模的多处理机系统。5.2.1 写一次(write-once)协议 写无效监听一致性协议，将写通过和写回策略结合。 为了减少总线流量，高速缓存块的第一次写用写通过方法，产生一份正确的主存储器副本，并使其它的Cache中的副本无效，之后就采用写回方法更新Cache与主存储器。1. 一致性协议的内容 一致性协议包括： （1）Cache可能出现的状态集合 （2）共享主存的状态 （3）为维护一致性而引起的状态转换。2. 每份Cache中的副本可能出现的四种状态 （1）有效（valid state）：与主存储器副

8、本一致的Cache副本，即该副本未经修改，所以这个Cache副本不是唯一的副本。 （2）保留（reserved state）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本一致。 （3）重写（dirty state）：Cache副本不止一次被修改过，由于不再采用写通过方法，所以这个Cache副本是唯一的副本。与存储器和其它的Cache副本都不一致。主存储器中的副本也是无效的。 （4）无效（invalid state）与存储器或其它的Cache副本不一致，或在Cache中找不到。3. 局部命令（Local commands） （1）P-Read：本地

9、处理机读自己的Cache副本。 （2）P-Write：本地处理机写自己的Cache副本。4. 一致性命令 （1）Read-blk：从另一Cache读一份有效的副本。 （2）Write-inv：在写命中时在总线上广播一个无效命令。 （3）Read-inv：在写缺失时在总线上广播一个无效命令。 Dirty: modified more than once, the only copy in the system; Invalid: inconsistent copy; Reserved: after written once, the only copy consistent with memor

10、y; Valid: A copy consistent with the memory copy.5. Write-Once一致性协议状态转移图其中，四种状态的含义如下：InvalidValidDirtyReservedRead-inv(4)P-Write(1)P-Write(hit:local still dirty)P-Write(hit:local, not memoryupdate, local copy becomes dirty)P-Write(hit:local,updatememory copy,broadcastwrite-inv to all cache,local cop

11、ybecomesreserved)Read-blk(3)Read-inv(4)P-Read(2)Read-blk(3)Read-inv(4)/Write-inv(5)P-Read(hit:alwayslocal,no statetransition)下一节(用鼠标点击连线来察看详细信息）P-Write(1)(1)P-Write(miss: take a dirty copy from a remote cache, or from memory; send Read-invto invalidate all copies; update local copy into a dirty one)

12、.InvalidValidDirtyReserved下一节InvalidValidDirtyReserved(2)P-Read(miss: if no dirty copy exists, memory supplies a validcopy, otherwise, the cache inhibits memory and supplies a copyand updates memory. Both copies become valid).P-Read(2)下一节InvalidValidDirtyReserved(3)Read-blk(read from remote processo

13、rs, the localcopy become valid).Read-blk(3)下一节InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)下一节InvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)下一节I

14、nvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)下一节InvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).(5)Write-inv(A remote cac

15、he updates its local copy during a write-hits and invalidates all other copies).Read-inv(4)/Write-inv(5)下一节 (1)P-Write(miss: take a dirty copy from a remote cache which then updates memory, or from memory; send Read-inv to invalidate all copies; update local copy into a dirty one). (2)P-Read(miss: i

16、f no dirty copy exists, memory supplies a valid copy, otherwise, the cache inhibits memory and supplies a copy and updates memory. Both copies become valid). (3)Read-blk(read from remote processors, the local copy become valid). (4)Read-inv(A remote cache reads a block during a write-miss, updates i

17、t and invalidates all other copies). (5)Write-inv(A remote cache updates its local copy during a write-hits and invalidates all other copies).6. Write-Once一致性协议状态转移表必是局部进行，不影响有效状态第一次写命中，用写通过法。同时修改本地和主存副本并广播Write-inv使所有副本失效commandcurrentstatenextstatestatusP-Read有效有效Read-hitP-Write有效保留Write-hitaction

18、第二次写命中，用写回法。但不修改主存的副本P-Write保留重写Write-hit写缺失时，则从主存或远程Cache送来副本。并广播Read-inv使所有其它副本无效。commandcurrentstatenextstatestatusP-Write无效保留 Write-missaction（续表）第二次以后更多的写命中，用写回法。无状态改变。P-Write重写重写Write-hitcommandcurrentstatenextstatestatusaction（续表）读缺失时,如远程Cache中没有重写副本，则主存中一定有一份正确的副本，供给发请求的Cache。如远程的Cache有重写的副本

19、，则它禁止主存操作，并将副本发给请求的Cache，两种情况均使发请求的Cache得到的副本为有效。P-Read无效有效 Read-miss远程Cache读此副本，读后两份副本均有效Read-blk保留或重写有效commandcurrentstatenextstatestatusaction（续表）写缺失时，远程Cache读一个块，并修改它，并使所有其它Cache的副本无效。Read-inv除无效外的其它状态无效写命中时，一远程Cache修改其本地副本，并使数据块的其它副本无效Write-inv有效无效commandcurrentstatenextstatestatusaction（续表）如果副

20、本处于重写状态，必须通过块替换写回主存，否则不产生替换操作Write-inv有效无效替代7.其它的一些问题 CPU要向Cache写数据，如果write miss，表示该数据块不在Cache中或者该数据快处于无效状态，那么需要把正确的数据从memory或其它的Cache中取过来，然后再写操作。 为什么不能直接写？ （1）可能该数据块根本不在Cache中，所以需要从其它地方调入。 （2）已在Cache中，但数据不正确，这时如果直接写入数据，整个数据块可能还是不正确的。例如，数据不正确的原因是100号单元数据已修改，如果要写入一个数据到101单元，这时不能直接写，否则100号单元还是错的。 Cach

21、e Coherence问题概要：多处理机系统共享存储器Cache块的状态访问的数据是最新的，不是“过时”的内容第五章 Cache Coherence5.1 Cache Coherence问题5.2 监听总线协议5.3 基于目录的Cache一致性协议5.3.1 目录的一般性问题5.3.2 全映射目录5.3.3 有限目录5.3.4 链式目录5.4 三种Cache一致性策略5.2 基于目录的Cache一致性协议5.2.1 目录的一般性问题 1.Cache一致性协议的开销分析 （1）采用写无效协议无效后，当其它处理机再读该副本时，出现Read miss，要有开销 （2）采用写更新协议需要更新所有Cac

22、he和memory中的副本，所以开销大，有些处理机对更新后的数据可能不会使用。 2. 基于目录的一致性协议的基本思想 当处理机台数增加时，一般不用总线结构，而采用多级互联网络。多级互连网络实现广播功能代价很大。 为什么需要广播功能？把一致性命令，如Write-inv，Read-inv等命令要发送给所有的Cache。 能不能只发送给存放该副本的Cache?基于目录的协议的基本思想 3. 目录的结构 （1）目录里放什么有关Cache副本驻留在哪里的信息：所有共享数据块的所有Cache副本的地址表。 （2）每个目录项（每个数据结构）包含若干个指向这个块（每个数据块有个目录项）的Cache副本地址的指

23、针以及一个重写位（用来说明是否有一个Cache允许把有关的数据写入）。 （3）基于目录的Cache一致性协议是依靠一个目录来记录系统之中哪些处理机的Cache中有指定存储块的副本。当一台处理机希望写某个共享块时，通过目录向有该块的副本的那些处理机“点对点”的发无效信号，使所有其它的副本无效。 4. 目录的方式（1）集中目录方式（中心目录）1976年Tang提出。用一个中心目录存放所有Cache目录的副本，它能提供为保证一致性所需要的所有信息。 缺点：容量非常大，必须采用联想方法来检查，冲突多，检索时间长。（2）分布式目录1978年Censier和Feautrier提出。每个存储模块维护各自的目

24、录，目录中记录着每个存储块的当前信息。当前信息指明哪些Cache有该存储块的副本。如下面的图：D1M1D2M2DmMmP1C1P2C2PmCm互连网络 如果C2读miss，这时C1中有Dirty的副本，则把它写回memory，内存再给C2一个副本，变成Valid。 如果C1写命中，它告诉memory控制器，控制器发无效命令给在D1的当前向量中有记录的所有Cache。 5. 三种目录 全映射（full map）目录：存放与全局存储器中每个块有关的数据。系统中的每个Cache可以同时存储任何数据块的副本，即每个目录项包含N个指针（N是处理机数目）。 有限（limited）目录：每个目录项有固定数目

25、的指针（小于N）。 链式（chained）目录：将目录分布到各个Cache（其余同全映射目录）。5.2.2 全映射目录 1.目录项结构 目录项中有N个处理机位（对应N台处理机）和一个重写位，如下图所示：目录项：重写位（1位）处理机位（N位） 处理机位表示相应处理机的Cache block的状态（存在或不存在）。 有一个也只有一个处理机位为“1”，那么该处理机可以对该块进行写操作。 Cache的每个块有两个状态位：有效位有效块是否允许写有效1位 Cache的状态位应该和目录项的状态一致。1位允许写目录项：重写位（1位）处理机位（N位）Cache状态位：2.目录的三种情况我们来看三台处理机（三个C

26、ache）的例子。（1）C1，C2，C3都没有单元X的副本 目录项的重写位被置为未写（c）状态，表示无一处理机允许写入该数据块。Shared Memoryx:c000dataC1P1C2P2C3P3（2）C1，C2，C3同时请求X单元的副本，这时目录项中的三个指针（处理机位）被置一，表示这些Cache中已有数据副本。 目录项的重写位被置为未写（c）状态，表示无一处理机允许写入该数据块。Shared Memoryx:c111datax:P1x:P2x:P3C1C2C3（3）C3请求对该块的写允许权时出现第（3）种情形，重写被置成D状态，且有一个指针指向C3的数据块。Shared Memoryx:

27、D001dataP1P2 x:P3C1C2C3data3.第二种情况第三种情况的过程 P3向C3发出写请求时：（1）C3检测出包含单元X的块是有效的，但Cache中的块允许位状态表示不允许处理机对该块进行写操作。（2）C3向包含单元X的存储器模块发出写请求，并暂停P3工作。（3）该存储器模块发出一个无效请求给C1和C2（根据目录项的内容发几个无效信号）（4）C1和C2收到无效请求后，把相应位置0，表示含单元X的块已无效，并发送一个回答信号给请求的存储器模块。（5）存储器模块收到回答信号后，将重写位置1，清除指向C1、C2的指针，发出允许信号给C3。（6）C3收到写允许信号后，修改Cache的状

28、态并激活处理机P3。4. 目录所占空间 假设存储器大小和处理机台数N成正比，即台数增加时，存储器的模块数也增加，所以数据块的个数也和N成正比。 另外目录项的大小也和处理机台数N成正比，所以目录的总所占空间和N2成正比。 即：目录项数*项大小 = O ( N2) 太大不便于扩展。5.2.3 有限目录 解决目录过大的问题。任意一个数据块在Cache中同时存在的副本数量有一定限制，那么目录大小的增加不会超过一个常数。符号表示法： DiriX i:指针的数量。X是NB，表示没有广播功能的方案。 DirNNB表示没有广播功能的全映射方式 DiriNB（i N）：使用i个指针的没有广播功能的有限目录协议方

29、式。 除了多于i个Cache请求读一个特定的数据块的情况外，有限目录协议与全映射协议类似。 有限目录中指针不是每台处理机一位，而是针对处理机的二进制标识符进行编码，所以指针占log2N位存储器。 在全映射方式中，每个处理机对应一个指针，所以N台处理机一共用了N位，而有限目录中只用log2N位，设N =16，则log216 = 4。 如果允许两个指针，则需要8位。 所以目录的存储容量为O（Nlog2N），比全映射容易扩充。 如果多处理机系统中的处理机具有局部性，即在任何给定的时间间隔内，只有一小部分处理机访问某个给定的存储器字，那么有限目录足以应付这个小的工作处理机组了。5.2.4 链式目录 用

30、目录指针链来跟踪共享数据副本。 两种方法，单链法与双链法。 数据块共享副本的数目并无限制。 所占的空间及可扩展性同有限目录。 它的工作原理如下过程所示。（1）P1要读单元X，则memory发送一份副本给C1，同时送给C1一个链结束指针（CT：Chain Termination），存储器也保存指向C1的指针。Shared Memoryx:cdataP1P2P3C1C2C3x:CTdata（2）当P2要读单元X时，存储器送一份副本给C2，同时送给C2一个指向C1的指针，存储器保存指向C2的指针。Shared Memoryx:cdataP1P2P3C1C2C3x:CTdatax:data（3）重复以

31、上步骤，所有Cache都得到单元X的副本。（4）如果P3要对单元X进行写操作，它必须沿着链发送一个数据无效信息。为了保证顺序一致性，在有链结束指针的处理机回答无效信号之前，存储器模块不给P3写允许权。 无效命令从一个Cache到一个Cache顺序进行，不象snoopy协议那样同时发送给所有Cache。（5）替换。假设C1到CN都有单元X的副本，还假设单元X和单元Y都映射到同一个高速缓存块（直接映射法）。如果处理机Pi要读单元Y，它首先必须把X所在的块从Cache中去掉，这可以采用两种方法： 1）沿着链发一个消息使Ci+1的指针指向Ci-1，这样使Ci从链中去掉（这时Ci中存放Y了）。 2）使C

32、i+1到CN中的单元X无效（这时Ci中存放Y了）。目录占用的存储容量：指针的尺寸以处理机数目的对数关系增长（这和有限目录相同）log2N，每个Cache块的指针数目与处理机个数无关。解决Cache一致性的其它办法：（1）不允许有私有 Cache：Shared Cache方案（2）可写的共享数据不存放在Cache中第五章 Cache Coherence5.1 Cache Coherence问题5.2 监听总线协议5.3 基于目录的Cache一致性协议5.4 三种Cache一致性策略 5.4.1 采用Write-Through策略的Cache 5.4.2 采用Write-Bach策略的Cache

33、5.4.3 采用Write-Once策略的Cache5.4 三种Cache一致性策略5.4.1 采用Write-Through策略的Cache 数据块的两种状态：有效和无效（指本地处理机相应数据块的状态，并非整个Cache的状态。) 一致性的四种操作： Rr和Wr：其它处理机对该数据块（指在其它处理机Cache中的数据块）的读写 Rl和Wl：是本地处理机对该数据块的读写状态转移图如下：有效无效RrWlRlRl, WlWrRr, WrCache的数据块为无效时： 其它处理机的任何操作都不会影响本地Cache的这种无效状态； 只有在本地处理机读或者写了数据块中的某个数据，即对Cache执行了Rea

34、d或Write命令时，该数据块的状态才会成为“有效”。 Cache的数据块为“有效”时： 本地处理机的读、写操作，不会影响该状态； 其它处理机对存有相同内容的数据块读，不会影响该状态； 其它处理机对存有相同内容的数据块执行了写操作，该数据块状态变成无效。5.4.2 采用Write-Back策略的Cache 1.数据块的三种状态 RO (只读）状态：表示整个系统中不止一个副本正确（例如一个在Cache中，一个在memory中）。 读-写状态：表示整个系统中，只有这个副本是正确的，其它都“过时”（即无效），这说明这个 Cache的数据块至少被写过一次，但memory中的内容还没有被修改。 无效状态

35、：“过时”数据。2. 一致性的四种操作： Rr和Wr：其它处理机对该数据块（指在其它处理机Cache中的数据块）的读写 Rl和Wl：是本地处理机对该数据块的读写状态转移图如下：3. 处于RO状态 本地读，远程读不会改变状态 本地写，使ROR-W（这时只有一个数据块正确） 远程写，使RO无效无效ROWlWrRl, RrW-R4. 处于读-写状态无效RORrWrRl,WlW-R 本地读、写不会改变状态 远程读：这时只有这个 Cache的数据块是正确的，所以要有“写回”动作（即把内容写回Memory），另外还需要把正确的数据传递给远程读的处理机相应的Cache。两个Cache的状态RO 远程写：把本

36、地处理机的数据块传递给远程处理机，远程处理机对数据块进行写操作，远程处理机对应的Cache状态变为RO，而本地的Cache变为无效状态。5. 处于无效状态无效ROWlRr,WrW-RRl 本地读：无效RO 本地写：无效WR（同时使其它拥有相同内容的数据块的Cache中相应的数据块的状态变成无效） 远程写、远程读：不影响状态的改变5.4.3 采用Write-Once策略的Cache 1. Write-Through和Write-Back的缺点 Write-Through策略的弱点是每次都要修改memory，所以总线流量增大； Write-Back策略的弱点是Cache写了一次后，Memory中的内容不一致。2. Write-Once的基本思想 把Write-Through和Write-Back两者的优点结合在一起：减少总线流量。 Cache的第一次写采用Write-Through策略（有一个以上的副本正确）； Cache而后的写采用Write-Back策略（只有一份副本正确）。 为了区分是否是第一次写，把“读-写”状态分成两个状态：Reserved和Drity。3. 数据块