[5] cache一致性

《[5] cache一致性》由会员分享，可在线阅读，更多相关《[5] cache一致性（98页珍藏版）》请在金锄头文库上搜索。

1、高等计算机体系结构,北京科技大学计算机系 李建江 参考课件：清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授,第五章 Cache Coherence,5.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内容应该一致，如下

2、图：,Memory,Cache,P,Cache,P,Cache,P,这几个copy 应该一致,5.1.2 多个Cache不一致的原因 1.共享可写数据的不一致性（sharing of writable data）,P1,P2,更新前,x,x,x,处理机,Cache,shared memory,P1,P2,写通过,x,x,x,P1,P2,写回,x,x,x,2.进程迁移的不一致性,P1,P2,迁移前,x,x,处理机,Cache,P1,P2,写通过,x,x,x,P1,P2,写回,x,x,x,shared memory,上图中： 右图为：包含共享变量x的进程原来在P1上运行，并对x进行了修改（但采取写

3、回策略，所以暂时没有修改Memory），由于某种原因迁移到P2，修改过的x仍在P1的Cache中，P2运行时从Memory中得到x（因为缺失），这个x其实是“过时”的，所以造成了不一致。 中间图为：P2中运行的进程对x进行了修改，采取写通过策略，所以把Memory中的x也修改为x，由于某种原因该进程迁移到P1，但P1的Cache中仍为x，所以造成不一致。,3. I/O操作（绕过Cache的I/O操作）,P1,P2,x,x,存储器,P1,P2,写通过,x,x,P1,P2,写回,x,x,x,x,x,x,x,I/O,存储器,输入,存储器,输出,c1,c2,总线,上图中： 中间图为：当I/O处理机将一

4、个新的数据x写入主存储器时，绕过采用写通过策略的cache，则C1和共享存储器之间产生了不一致。 右图为：直接从主存储器输出数据时（绕过Cache），采用写回策略的高速缓存产生不一致性。,5.1.3 两种设计Cache一致性协议策略 1.写无效（write invalidate） 任一处理器写它的私有Cache时，它都使所有其它的Cache中的副本失效。 对Write-through，它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）。 对Write-back，它使memory中的副本也失效（最终只有一个Cache中的副本是有效的）。,2.写更新（wri

5、te update） 任一处理器写它的私有Cache时，它都立即更新所有其它的Cache中的副本。 对Write-through，它也更新主存储器中的副本。 对Write-back，对存储器中副本的更新延迟到这个Cache被置换的时刻。,3. 示意图 下图表示数据块x在共享存储器和三台处理机的Cache中的副本一致的情形。,x,共享存储器,Cache,P1,x,P2,x,x,P3,总线,处理机,下图表示P1进行写无效操作后的情形。 写通过：,x,I表示无效,P1,I,P2,x,I,P3,写回：,x,I表示无效,P1,I,P2,I,I,P3,下图表示P1进行写更新操作后的情形（写通过）。,x,I

6、表示无效,P1,x,P2,x,x,P3,4.写无效的问题 主要开销在两个方面： （1）作废各Cache副本的开销； （2）由作废引起缺失造成的开销，即处理机需要访问已经作废的数据时将引起Cache的缺失。,后果： 如果一个处理机经常对某个块连续写，且各处理处理机间对共享块的竞争较小，这时写无效策略维护一致性的开销是很小的。如发生严重竞争，即处理机之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比较大时，这种颠簸现象更为严重。,5. 写更新的问题 由于更新时，所有的副本均需要更新，开销很大。,第五章 Cache C

7、oherence,5.1 Cache Coherence问题 5.2 监听总线协议 5.2.1 写一次协议 5.3 基于目录的Cache一致性协议 5.4 三种Cache一致性策略,5.2 监听总线协议(Snoopy protocol),通过总线监听机制实现Cache和共享存储器之间的一致性。 适用性分析： 适用于具有广播能力的总线结构多机系统，允许每台处理机监听其它处理机的存储器访问情况。 只适用于小规模的多处理机系统。,5.2.1 写一次(write-once)协议 写无效监听一致性协议，将写通过和写回策略结合。 为了减少总线流量，高速缓存块的第一次写用写通过方法，产生一份正确的主存储器副

8、本，并使其它的Cache中的副本无效，之后就采用写回方法更新Cache与主存储器。,1. 一致性协议的内容 一致性协议包括： （1）Cache可能出现的状态集合 （2）共享主存的状态 （3）为维护一致性而引起的状态转换。,2. 每份Cache中的副本可能出现的四种状态 （1）有效（valid state）：与主存储器副本一致的Cache副本，即该副本未经修改，所以这个Cache副本不是唯一的副本。 （2）保留（reserved state）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本一致。,（3）重写（dirty state）：Cache副本不

9、止一次被修改过，由于不再采用写通过方法，所以这个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：在写缺失时在总线上广播

10、一个无效命令。,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.,5. Write-Once一致性协议状态转移图 其中，四种状态的含义如下：,Invalid,Valid,Dirty,Reserved,Read-inv (4),P-Write(

11、1),P-Write (hit:local still dirty),P-Write (hit:local, not memory update, local copy becomes dirty),P-Write (hit:local,update memory copy, broadcast write-inv to all cache, local copy becomes reserved),Read-blk(3),Read-inv(4),P-Read(2),Read-blk (3),Read-inv(4)/Write-inv(5),P-Read (hit:always local,

12、no state transition),下 一 节,(用鼠标点击连线来察看详细信息）,Invalid,Valid,Dirty,Reserved,下 一 节,Invalid,Valid,Dirty,Reserved,下 一 节,Invalid,Valid,Dirty,Reserved,下 一 节,Invalid,Valid,Dirty,Reserved,下 一 节,Invalid,Valid,Dirty,Reserved,下 一 节,Invalid,Valid,Dirty,Reserved,下 一 节,Invalid,Valid,Dirty,Reserved,下 一 节,(1)P-Write(

13、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: if no dirty copy exists, memory supplies a valid copy, otherwise, the cache inhibits memory and supplies a copy and upda

14、tes 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 it and invalidates all other copies). (5)Write-inv(A remote cache updates its local copy during a write-hits and invalid

15、ates all other copies).,6. Write-Once一致性协议状态转移表,必是局部进行， 不影响有效状态,第一次写命中，用 写通过法。同时修,改本地和主存副本 并广播Write-inv 使所有副本失效,command,current state,next state,status,P-Read,有效,有效,Read-hit,P-Write,有效,保留,Write-hit,action,第二次写命中，用 写回法。但不修改,主存的副本,P-Write,保留,重写,Write-hit,写缺失时，则从主存 或远程Cache送来副本,。并广播Read-inv 使所有其它副本无效。,command,current state,next state,status,P-Write,无效,保留,Write-miss,action,（续表）,第二次以后更多的 写命中，用写回法。,无状态改变。,P-Write,重写,重写,Write-hit,command,current state,next state,status,action,（续表）,读缺失时,如远程Cache 中没有重写副本，则主,存中一定有一