[5] Cache一致性

高等计算机体系结构北京科技大学计算机系李建江参考课件：清华大学计算机科学与技术系高性能计算研究所郑纬民教授第五章CacheCoherence5.1CacheCoherence问题5.1.1CacheCoherence的提出5.1.2多个Cache不一致的原因5.1.3两种设计Cache一致性协议策略5.2监听总线协议5.3基于目录的Cache一致性协议5.4三种Cache一致性策略5.1CacheCoherence问题5.1.1CacheCoherence问题的提出在多处理器系统中，多个Cache中，对应的copy内容应该一致，如下图：MemoryCachePCacheP……CacheP这几个copy应该一致5.1.2多个Cache不一致的原因1.共享可写数据的不一致性（sharingofwritabledata）P1P2更新前xxx处理机CachesharedmemoryP1P2写通过x’xx’P1P2写回x’xx2.进程迁移的不一致性P1P2迁移前xx处理机CacheP1P2写通过xx’x’P1P2写回x’xxsharedmemory上图中：右图为：包含共享变量x的进程原来在P1上运行，并对x进行了修改（但采取写回策略，所以暂时没有修改Memory），由于某种原因迁移到P2，修改过的x’仍在P1的Cache中，P2运行时从Memory中得到x（因为缺失），这个x其实是“过时”的，所以造成了不一致。中间图为：P2中运行的进程对x进行了修改，采取写通过策略，所以把Memory中的x也修改为x’，由于某种原因该进程迁移到P1，但P1的Cache中仍为x，所以造成不一致。3.I/O操作（绕过Cache的I/O操作）P1P2xx存储器P1P2写通过xxP1P2写回x’xxx’x’xxI/O存储器输入存储器输出c1c2总线上图中：中间图为：当I/O处理机将一个新的数据x’写入主存储器时，绕过采用写通过策略的cache，则C1和共享存储器之间产生了不一致。右图为：直接从主存储器输出数据时（绕过Cache），采用写回策略的高速缓存产生不一致性。5.1.3两种设计Cache一致性协议策略1.写无效（writeinvalidate）任一处理器写它的私有Cache时，它都使所有其它的Cache中的副本失效。对Write-through，它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）。对Write-back，它使memory中的副本也失效（最终只有一个Cache中的副本是有效的）。2.写更新（writeupdate）任一处理器写它的私有Cache时，它都立即更新所有其它的Cache中的副本。对Write-through，它也更新主存储器中的副本。对Write-back，对存储器中副本的更新延迟到这个Cache被置换的时刻。3.示意图下图表示数据块x在共享存储器和三台处理机的Cache中的副本一致的情形。x共享存储器CacheP1xP2xxP3…………总线处理机下图表示P1进行写无效操作后的情形。写通过：x’I表示无效P1IP2x’IP3…………写回：x’I表示无效P1IP2IIP3…………下图表示P1进行写更新操作后的情形（写通过）。x’I表示无效P1x’P2x’x’P3…………4.写无效的问题主要开销在两个方面：（1）作废各Cache副本的开销；（2）由作废引起缺失造成的开销，即处理机需要访问已经作废的数据时将引起Cache的缺失。后果：如果一个处理机经常对某个块连续写，且各处理处理机间对共享块的竞争较小，这时写无效策略维护一致性的开销是很小的。如发生严重竞争，即处理机之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比较大时，这种颠簸现象更为严重。5.写更新的问题由于更新时，所有的副本均需要更新，开销很大。第五章CacheCoherence5.1CacheCoherence问题5.2监听总线协议5.2.1写一次协议5.3基于目录的Cache一致性协议5.4三种Cache一致性策略5.2监听总线协议(Snoopyprotocol)通过总线监听机制实现Cache和共享存储器之间的一致性。适用性分析：适用于具有广播能力的总线结构多机系统，允许每台处理机监听其它处理机的存储器访问情况。只适用于小规模的多处理机系统。5.2.1写一次(write-once)协议写无效监听一致性协议，将写通过和写回策略结合。为了减少总线流量，高速缓存块的第一次写用写通过方法，产生一份正确的主存储器副本，并使其它的Cache中的副本无效，之后就采用写回方法更新Cache与主存储器。1.一致性协议的内容一致性协议包括：（1）Cache可能出现的状态集合（2）共享主存的状态（3）为维护一致性而引起的状态转换。2.每份Cache中的副本可能出现的四种状态（1）有效（validstate）：与主存储器副本一致的Cache副本，即该副本未经修改，所以这个Cache副本不是唯一的副本。（2）保留（reservedstate）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本一致。（3）重写（dirtystate）：Cache副本不止一次被修改过，由于不再采用写通过方法，所以这个Cache副本是唯一的副本。与存储器和其它的Cache副本都不一致。主存储器中的副本也是无效的。（4）无效（invalidstate）与存储器或其它的Cache副本不一致，或在Cache中找不到。3.局部命令（Localcommands）（1）P-Read：本地处理机读自己的Cache副本。（2）P-Write：本地处理机写自己的Cache副本。4.一致性命令（1）Read-blk：从另一Cache读一份有效的副本。（2）Write-inv：在写命中时在总线上广播一个无效命令。（3）Read-inv：在写缺失时在总线上广播一个无效命令。Dirty:modifiedmorethanonce,theonlycopyinthesystem;Invalid:inconsistentcopy;Reserved:afterwrittenonce,theonlycopyconsistentwithmemory;Valid:Acopyconsistentwiththememorycopy.5.Write-Once一致性协议状态转移图其中，四种状态的含义如下：InvalidValidDirtyReservedRead-inv(4)P-Write(1)P-Write(hit:localstilldirty)P-Write(hit:local,notmemoryupdate,localcopybecomesdirty)P-Write(hit:local,updatememorycopy,broadcastwrite-invtoallcache,localcopybecomesreserved)Read-blk(3)Read-inv(4)P-Read(2)Read-blk(3)Read-inv(4)/Write-inv(5)P-Read(hit:alwayslocal,nostatetransition)下一节(用鼠标点击连线来察看详细信息）P-Write(1)(1)P-Write(miss:takeadirtycopyfromaremotecache,orfrommemory;sendRead-invtoinvalidateallcopies;updatelocalcopyintoadirtyone).InvalidValidDirtyReserved下一节InvalidValidDirtyReserved(2)P-Read(miss:ifnodirtycopyexists,memorysuppliesavalidcopy,otherwise,thecacheinhibitsmemoryandsuppliesacopyandupdatesmemory.Bothcopiesbecomevalid).P-Read(2)下一节InvalidValidDirtyReserved(3)Read-blk(readfromremoteprocessors,thelocalcopybecomevalid).Read-blk(3)下一节InvalidValidDirtyReserved(3)Read-blk(readfromremoteprocessors,thelocalcopybecomevalid).Read-blk(3)下一节InvalidValidDirtyReserved(4)Read-inv(Aremotecachereadsablockduringawrite-miss,updatesitandinvalidatesallothercopies).Read-inv(4)下一节InvalidValidDirtyReserved(4)Read-inv(Aremotecachereadsablockduringawrite-miss,updatesitandinvalidatesallothercopies).Read-inv(4)下一节InvalidValidDirtyReserved(4)Read-inv(Aremotecachereadsablockduringawrite-miss,updatesitandinvalidatesallothercopies).(5)Write-inv(Aremotecacheupdatesitslocalcopyduringawrite-hitsandinvalidatesallothercopies).Read-inv(4)/Write-inv(5)下一节(1)P-Write(miss:takeadirtycopyfromaremotecachewhichthenupdatesmemory,orfrommemory;sendRead-invtoinvalidateallcopies;updatelocalcopyintoadirtyone).(2)P-Read(miss:ifnodirtycopyexists,memorysuppliesavalidcopy,otherwise,thecacheinhibitsmemoryandsuppliesacopyandupdatesmemory.Bothcopiesbecomevalid).(3)Read-blk(readfromremoteprocessors,thelocalcopybecomevalid).(4)Read-inv(Aremotecachereadsablockduringawrite-miss,updatesitandinvalidatesallothercopies).(5)Write-inv(Aremotecacheupdatesitslocalcopyduringawrite-hitsandinvalidatesallothercopies).6.Write-Once一致性协议状态转移表必是局部进行，不影响有效状态第一次写命中，用写通过法。同时修改本地和主存副本并广播Write-inv使所有副本失效commandcurrentstatenextstatestatusP-Read有效有效Read-hitP-Write有效保留Write-hitaction第二次写命中，用写回法。但不修改主存的副本P-Write保留重写Write-hit写缺失时，则从主存或远程Cache送来副本。并广播Read-inv使所有其它副本无效。commandcurrentstatenextstatestatusP-Write无效保留Write-missaction（续表）第二次以后更多的写命中，用写回法。无状态改变。P-Write重写重写Write-hitcommandcur