20多核Cache一致性

多核、多处理机体系结构中的Cache一致性1.1CacheCoherence问题1.1.1CacheCoherence的提出1.1.2多个Cache不一致的原因1.1.3两种设计Cache一致性协议策略1.2监听总线协议1.3基于目录的Cache一致性协议1.4三种Cache一致性策略1.1CacheCoherence问题1.1.1CacheCoherence问题的提出在多核和多处理器系统中，多个Cache对应的copy内容应该一致，如下图：MemoryCachecoreCachecore……Cachecore这几个copy应该一致1.1.2多个Cache不一致的原因1.共享可写数据的不一致性（sharingofwritabledata）core1core2更新前xxx核Cachesharedmemorycore1core2写通过x’xx’core1core2写回x’xx2.进程迁移的不一致性core1core2迁移前xx核Cachecore1core2写通过xx’x’core1core2写回x’xx上图中：右图为：包含共享变量x的进程原来在core1上运行，并对x进行了修改（但采取写回策略，所以暂时没有修改Memory），由于某种原因迁移到core2，修改过的x’仍在core1的Cache中，core2运行时从Memory中得到x，这个x其实是“过时”的，所以造成了不一致。中间图为：core2中运行的进程对x进行了修改，采取写通过策略，所以把Memory中的x也修改为x’，由于某种原因该进程迁移到core1，但core1的Cache中仍为x，所以造成不一致。3.I/O操作（绕过Cache的I/O操作）core1core2xx存储器core1core2写通过xxcore1core2写回x’xxx’x’xxI/O存储器输入存储器输出c1c2总线上图中：中间图为：当I/O处理机将一个新的数据x’写入主存储器时，绕过采用写通过策略的cache，则C1和共享存储器之间产生了不一致。右图为：直接从主存储器输出数据时（绕过Cache），与采用写回策略的高速缓存产生不一致性。1.1.3两种设计Cache一致性协议策略1.写无效（writeinvalidate）任一core写它的私有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…………总线核下图表示core1进行写无效操作后的情形。写通过：x’I表示无效core1Icore2x’Icore3…………写回：x’I表示无效core1Icore2IIcore3…………下图表示core1进行写更新操作后的情形（写通过）。x’I表示无效core1x’core2x’x’core3…………4.写无效的问题主要开销在两个方面：（1）作废各Cache副本的开销；（2）由作废引起缺失造成的开销，即处理机需要访问已经作废的数据时将引起Cache的缺失。后果：如果一个Core经常对某个块连续写，且Core间对共享块的竞争较小，这时写无效策略维护一致性的开销是很小的。如发生严重竞争，即Core之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比较大时，这种颠簸现象更为严重。5.写更新的问题由于更新时，所有的副本均需要更新，开销很大。1.1CacheCoherence问题1.2监听总线协议1.2.1写一次协议1.3基于目录的Cache一致性协议1.4三种Cache一致性策略1.2监听总线协议(Snoopyprotocol)通过总线监听机制实现Cache和共享存储器之间的一致性。适用性分析：适用于具有广播能力的总线结构多Core系统，允许每个Core监听其它Core的存储器访问情况。只适用于小规模的多Core系统。1.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：在写缺失时在总线上广播一个无效命令。5.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-hitcommandcurrentstatenextstatestatusaction（续表）读缺失时,如远程Cache中没有重写副本，则主存中一定有一份正确的副本，供给发请求的Cache。如远程的Cache有重写的副本，则它禁止主存操作，并将副本发给请求的Cache，两种情况均使发请求的Cache得到的副本为有效。P-Read无效有效Read-miss远程Cache读此副本，读后两份副本均有效Read-blk保留或重写有效commandcurrentstatenextstatestatusaction（续表）写缺失时，远程Cache读一个块，并修改它，并使所有其它Cache的副本无效。Read-inv除无效外的其它状态无效写命中时，一远程Cache修改其本地副本，并使数据块的其它副本无效Write-inv有效无效commandcurrentstatenextstatestatusaction（续表）如果副本处于重写状态，必须通过块替换写回主存，否则不产生替换操作Write-inv有效无效替代6.一个具体的例子如下图的系统：MemoryC1Core1C2Core2C3Core3读的情况：（1）如果C1为Valid，读C1，则Readhit，状态不变。（2）如果C1为Reserved，读C1，则Readhit，状态不变。（3）如果C1为Dirty，读C1，则Readhit，状态不变。（4）如果C1为Invalid，C2和C3没有东西，则读C1时Readmiss，这时只有memory中有正确的副本，把它取到C1，C1改为Valid（P-Read负责实现状态的改变）。（5）如果C1为Invalid，C2为Dirty，则读C1时Readmiss，这时只有C2中的内容是正确的，要发Read-blk信号把副本从C2读到C1，同时修改memory，把C1，C2都改为Valid（程序状态转移图中P-Read(2)使C1Valid，Read-blk(3)使C2Valid）。（6）如果C1为Invalid，C2为Reserved，则读C1时Readmiss，这时发Read-blk信号把C2C1，C1，C2都改为Valid，其中Read-blk(3)负责把C2由ReservedValid，P-Read(2)负责把C1由InvalidValid。写的情况：（1）如果C1为Valid，写C1，则Writehit，发P-write修改C1内容，修改memory，发Write-inv(4)给所有Cache，C1变成Reserved状态。（2）如果C1为Reserved，写C1，则Writehit，发P-write修改C1内容，不修改memory，C1状态变为Dirty。（3）如果C1为Dirty，写C1，则Writehit，发P-write修改C1内容，不修改memory，状态仍为Dirty。（4）如果C1为Invalid，C2，C3没有东西，这时memory中有这个地址的数据副本，从memory中读取该副本到C1，再把要写的内容写入C1，这时C1和memory内容不一致，把C1的状态变为Dirty。（5）如果C1为Invalid，C2为Dirty，这时memory中内容和C2中的内容不一致，把C2C1，再把要写的内容写入C1，C1Dirty，发Read-inv使其它所有Cache的副本变成无效状态。（6）如果C1为Invalid，C2为Reserved，这时memory中的内容和C2内容一致，把C2C1，再把要写的内容写入C1，这时C1与memory内容不一致，使C1Dirty，发Read-inv使其它所有Cache的副本变成无效状态。C1的三种状态的图示:xxcore1xcore2xcore3C1C2C3memoryvalidC1中的副本和memory中一致x’x’core1Icore2Icore3C1C2C3memoryReservedInvalidC1中的副本和memory中一致，都正确x’x’’core1Icore2Icore3C1C2C3memoryDirtyInvalidC1中的副本和memory不一致，只有C1中的副本正确7.其它的一些问题Core要向Cache写数据，如果writemiss，表示该数据块不在Cache中或者该数据块处于无效状态，那么需要把正确的数据从memory或其它的Cache中取过来，然后再写操作。为什么不能直接写？（1）可能该数据块根本不在Cache中，所以需要从其它地方调入。（2）已在Cache中，但数据不正确，这时如果直接写入数据，整个数据块可能还是不正确的。例如，数据不正确的原因是100号单元数据已修改，如果要写入一个数据到101单元，这时不能直接写，否则100号单元还是错的。CacheCoherence问题概要：多核或多处理机系统共享存储器Cache块的状态访问的数据是最新的，不是“过时”的内容1.1CacheCoherence问题1.2监听总线协议1.3基于目录的Cache一致性协议1.3.1目录的一般性问题1.3.