多核对操作系统的影响Cache一致性学习教案

《多核对操作系统的影响Cache一致性学习教案》由会员分享，可在线阅读，更多相关《多核对操作系统的影响Cache一致性学习教案（102页珍藏版）》请在金锄头文库上搜索。

1、会计学1多核对操作系统多核对操作系统(co zu x tn)的影响的影响Cache一致性一致性第一页，共102页。2outlinen nCache Coherence问题n nCache Coherence的提出n n多个Cache不一致的原因n n两种设计Cache一致性协议(xiy)策略n n监听总线协议(xiy)n n基于目录的Cache一致性协议(xiy)n n三种Cache一致性策略第1页/共101页第二页，共102页。3Cache Coherence问问题题(wnt)lCache Coherence问题的提出l在多核和多处理器系统中，多个Cache对应的copy内容应该(ynggi

2、)一致：MemoryCachecoreCachecoreCachecore这几个(j )copy应该一致第2页/共101页第三页，共102页。4多个多个CacheCache不一致不一致(yzh)(yzh)的原因的原因n n共享可写数据的不一致性n n进程迁移(qiny)的不一致性n nI/O操作（绕过Cache的I/O操作）第3页/共101页第四页，共102页。5l共享可写数据(shj)的不一致性（sharing of writable data）core1core2更新(gngxn)前xxx核Cachesharedmemorycore1core2写通过(tnggu)xxxcore1core2

3、写回xxxCache和内存时刻保持一致第4页/共101页第五页，共102页。6l进程(jnchng)迁移的不一致性core1core2迁移(qiny)前xx核Cachecore1core2写通过(tnggu)xxxcore1core2写回xxx第5页/共101页第六页，共102页。7lI/O操作(cozu)（绕过Cache的I/O操作(cozu)）core1core2xx存储器core1core2写通过(tnggu)xxcore1core2写回xxxxxxxI/O存储器输入(shr)存储器输出c1c2总线第6页/共101页第七页，共102页。8两种设计两种设计CacheCache一致性一致性协

4、议协议(xiy)(xiy)策略策略n n写无效（写无效（写无效（写无效（writeinvalidatewriteinvalidatewriteinvalidatewriteinvalidate）n n任一任一任一任一corecorecorecore写它的私有写它的私有写它的私有写它的私有CacheCacheCacheCache时，它都使所有其它的时，它都使所有其它的时，它都使所有其它的时，它都使所有其它的CacheCacheCacheCache中的副本失效。中的副本失效。中的副本失效。中的副本失效。n n对对对对Write-throughWrite-throughWrite-throughWr

5、ite-through，它也更新，它也更新，它也更新，它也更新memorymemorymemorymemory中的副本（最终中的副本（最终中的副本（最终中的副本（最终(zuzhn)(zuzhn)(zuzhn)(zuzhn)是一个是一个是一个是一个CacheCacheCacheCache中的副本和中的副本和中的副本和中的副本和memorymemorymemorymemory中的副本是中的副本是中的副本是中的副本是有效的）。有效的）。有效的）。有效的）。n n对对对对Write-backWrite-backWrite-backWrite-back，它使，它使，它使，它使memorymemoryme

6、morymemory中的副本也失效（最终中的副本也失效（最终中的副本也失效（最终中的副本也失效（最终(zu(zu(zu(zuzhn)zhn)zhn)zhn)只有一个只有一个只有一个只有一个CacheCacheCacheCache中的副本是有效的）。中的副本是有效的）。中的副本是有效的）。中的副本是有效的）。第7页/共101页第八页，共102页。9两种设计两种设计(shj)Cache(shj)Cache一致性一致性协议策略协议策略n n写更新（写更新（写更新（写更新（writeupdatewriteupdatewriteupdatewriteupdate）n n任一处理器写它的私有任一处理器写它

7、的私有任一处理器写它的私有任一处理器写它的私有CacheCacheCacheCache时，它都立即更新所有其它时，它都立即更新所有其它时，它都立即更新所有其它时，它都立即更新所有其它的的的的CacheCacheCacheCache中的副本中的副本中的副本中的副本(fbn)(fbn)(fbn)(fbn)。n n对对对对Write-throughWrite-throughWrite-throughWrite-through，它也更新主存储器中的副本，它也更新主存储器中的副本，它也更新主存储器中的副本，它也更新主存储器中的副本(fbn)(fbn)(fbn)(fbn)。n n对对对对Write-bac

8、kWrite-backWrite-backWrite-back，对存储器中副本，对存储器中副本，对存储器中副本，对存储器中副本(fbn)(fbn)(fbn)(fbn)的更新延迟到这的更新延迟到这的更新延迟到这的更新延迟到这个个个个CacheCacheCacheCache被置换的时刻。被置换的时刻。被置换的时刻。被置换的时刻。第8页/共101页第九页，共102页。10 下图表示数据块x在共享存储器和三个核的Cache中的副本一致(yzh)的情形。x共享存储器CacheP1xP2xxP3总线(zn xin)核第9页/共101页第十页，共102页。11l下图表示core1进行写无效(wxio)操作后

9、的情形。l写通过：xI表示(biosh)无效core1Icore2xIcore3共享存储器Cache总线(zn xin)核第10页/共101页第十一页，共102页。12l写回：xI表示(biosh)无效core1Icore2IIcore3共享存储器Cache总线(zn xin)核第11页/共101页第十二页，共102页。13l下图表示core1进行写更新操作后的情形(qng xing)（写通过）。xI表示(biosh)无效core1xcore2xxcore3共享存储器Cache总线(zn xin)核第12页/共101页第十三页，共102页。14l写无效的问题写无效的问题l主要开销在两个方面：主

10、要开销在两个方面：l（1）作废）作废(zu fi)各各Cache副本的副本的开销；开销；l（2）由作废）由作废(zu fi)引起缺失造成引起缺失造成的开销，即处理机需要访问已经作的开销，即处理机需要访问已经作废废(zu fi)的数据时将引起的数据时将引起Cache的的缺失。缺失。第13页/共101页第十四页，共102页。15l写无效后果：写无效后果：l如果一个如果一个Core经常对某个块连续写，经常对某个块连续写，且且Core间对共享块的竞争较小，这间对共享块的竞争较小，这时写无效策略维护一致性的开销是时写无效策略维护一致性的开销是很小的。很小的。l如发生严重竞争，即如发生严重竞争，即Core

11、之间对某之间对某个地址的共享数据竞争，将产生个地址的共享数据竞争，将产生(chnshng)较多的作废，引起更多较多的作废，引起更多的作废缺失。结果是共享数据在各的作废缺失。结果是共享数据在各Cache间倒来倒去，产生间倒来倒去，产生(chnshng)颠簸现象，当缓存块比颠簸现象，当缓存块比较大时，这种颠簸现象更为严重。较大时，这种颠簸现象更为严重。第14页/共101页第十五页，共102页。16l写更新写更新(gngxn)的问题的问题l由于更新由于更新(gngxn)时，所有的副时，所有的副本均需要更新本均需要更新(gngxn)，开销很，开销很大。大。第15页/共101页第十六页，共102页。17

12、outlinen nCache Coherence问题n nCache Coherence的提出n n多个Cache不一致(yzh)的原因n n两种设计Cache一致(yzh)性协议策略n n监听总线协议n n写一次协议n n基于目录的Cache一致(yzh)性协议n n三种Cache一致(yzh)性策略第16页/共101页第十七页，共102页。18监听监听(jin tn)总线协议总线协议(Snoopy protocol)l通过总线监听机制实现Cache和共享存储器之间的一致性。l适用性分析：l适用于具有广播能力的总线结构多Core系统，允许(ynx)每个Core监听其它Core的存储器访问情

13、况。l只适用于小规模的多Core系统。第17页/共101页第十八页，共102页。19l写一次写一次(write-once)协议协议l写无效监听一致性协议，将写通过写无效监听一致性协议，将写通过(tnggu)和写回策略结合。和写回策略结合。l为了减少总线流量，高速缓存块的第为了减少总线流量，高速缓存块的第一次写用写通过一次写用写通过(tnggu)方法，产方法，产生一份正确的主存储器副本，并使其生一份正确的主存储器副本，并使其它的它的Cache中的副本无效，之后就采中的副本无效，之后就采用写回方法更新用写回方法更新Cache与主存储器。与主存储器。第18页/共101页第十九页，共102页。20l一

14、致性协议的内容包括一致性协议的内容包括l l（1）Cache可能出现可能出现(chxin)的的状态集合状态集合l（2）共享主存的状态）共享主存的状态l（3）为维护一致性而引起的状态转）为维护一致性而引起的状态转换。换。第19页/共101页第二十页，共102页。21l每份Cache中的副本可能出现的四种状态 l（1）有效（valid state）：与主存储器副本一致的Cache副本，即该副本未经修改，所以这个(zh ge)Cache副本不是唯一的副本。l（2）保留（reserved state）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本一致。l

15、（3）重写（dirty state）：Cache副本不止一次被修改过，由于不再采用写通过方法，所以这个(zh ge)Cache副本是唯一的副本。与存储器和其它的Cache副本都不一致。主存储器中的副本也是无效的。l（4）无效（invalid state）与存储器或其它的Cache副本不一致，或在Cache中找不到。第20页/共101页第二十一页，共102页。22l局部命令（Local commands） l（1）P-Read：本地(bnd)处理机读自己的Cache副本。l（2）P-Write：本地(bnd)处理机写自己的Cache副本。第21页/共101页第二十二页，共102页。23l一致性命

16、令一致性命令l（1）Read-blk：从另一：从另一Cache读一读一份有效份有效(yuxio)的副本。的副本。l（2）Write-inv：在写命中时在总线：在写命中时在总线上广播一个无效命令。上广播一个无效命令。l（3）Read-inv：在写缺失时在总线：在写缺失时在总线上广播一个无效命令。上广播一个无效命令。第22页/共101页第二十三页，共102页。24lDirty: modified more than once, the only copy in the system;lInvalid: inconsistent copy;lReserved: after written once,

17、 the only copy consistent with memory;lValid: A copy consistent with the memory copy.lWrite-Once一致性协议状态转移图l其中(qzhng)，四种状态的含义如下：第23页/共101页第二十四页，共102页。25InvalidValidDirtyReservedRead-inv(4)P-Write(1)P-Write(hit:local still dirty)P-Write(hit:local, not memoryupdate, local copy becomes dirty)P-Write(hit

18、:local,updatememory copy,broadcastwrite-inv to all cache,local copybecomesreserved)Read-blk(3)Read-inv(4)P-Read(2)Read-blk(3)Read-inv(4)/Write-inv(5)P-Read(hit:alwayslocal,no statetransition)第24页/共101页第二十五页，共102页。26P-Write(1)(1)P-Write(miss: take a dirty copy from a remote cache, or from memory; sen

19、d Read-inv to invalidate all copies; update local copy into a dirty one).InvalidValidDirtyReserved第25页/共101页第二十六页，共102页。27InvalidValidDirtyReserved(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 co

20、pies become valid).P-Read(2)第26页/共101页第二十七页，共102页。28InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)第27页/共101页第二十八页，共102页。29InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)第28页/共101页第二十九

21、页，共102页。30InvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)第29页/共101页第三十页，共102页。31lWrite-Once一致性协议(xiy)状态转移表必是局部进行(jnxng)，不影响有效状态第一次写命中(mngzhng)，用写通过法。同时修改本地和主存副本并广播Write-inv使所有副本失效commandcurrentstatenextsta

22、testatusP-Read有效有效Read-hitP-Write有效保留Write-hitaction第二次写命中，用写回法。但不修改主存的副本P-Write保留重写Write-hit第30页/共101页第三十一页，共102页。32写缺失(qu sh)时，则从主存或远程Cache送来副本。并广播Read-inv使所有其它(qt)副本无效。commandcurrentstatenextstatestatusP-Write无效(wxio)保留 Write-missactionl（续表）第二次以后更多的写命中，用写回法。无状态改变。P-Write重写重写Write-hit第31页/共101页第三十

23、二页，共102页。33写缺失时，则从主存或远程(yunchng)Cache送来副本。并广播(gungb)Read-inv使所有其它副本无效。commandcurrentstatenextstatestatusP-Write 无效(wxio)保留Write-missactionl（续表）第二次以后更多的写命中，用写回法。无状态改变。P-Write重写重写Write-hit第32页/共101页第三十三页，共102页。34commandcurrentstatenextstatestatusactionl（续表）读缺失时,如远程(yunchng)Cache中没有重写副本，则主存中一定有一份正确的副本，

24、供给发请求的Cache。如远程的Cache有重写的副本，则它禁止主存操作，并将副本发给(f i)请求的Cache，两种情况均使发请求的Cache得到的副本为有效。P-Read无效(wxio)有效Read-miss第33页/共101页第三十四页，共102页。35远程Cache读此副本(fbn)，读后两份副本(fbn)均有效Read-blk保留(boli)或重写有效(yuxio)commandcurrentstatenextstatestatusactionl（续表）写缺失时，远程Cache读一个块，并修改它，并使所有其它Cache的副本无效。Read-inv除无效外的其它状态无效第34页/共10

25、1页第三十五页，共102页。36写命中时，一远程Cache修改其本地副本，并使数据(shj)块的其它副本无效Write-inv有效(yuxio)无效(wxio)commandcurrentstatenextstatestatusactionl（续表）如果副本处于重写状态，必须通过块替换写回主存，否则不产生替换操作Write-inv有效无效替代第35页/共101页第三十六页，共102页。37l一个具体的例子一个具体的例子l如下如下(rxi)图的系统：图的系统：MemoryC1Core1C2Core2C3Core3第36页/共101页第三十七页，共102页。38l读的情况：l（1）如果C1为Val

26、id，读C1，则Read hit，状态不变。l（2）如果C1为Reserved，读C1，则Read hit，状态不变。l（3）如果C1为Dirty，读C1，则Read hit，状态不变。l（4）如果C1为Invalid，C2和C3没有东西，则读C1时Read miss，这时只有memory中有正确的副本，把它取到C1，C1改为Valid（P-Read负责(fz)实现状态的改变）。第37页/共101页第三十八页，共102页。39l （5）如果(rgu)C1为Invalid，C2为Dirty，则读C1时Read miss，这时只有C2中的内容是正确的，要发Read-blk信号把副本从C2读到C1，

27、同时修改memory，把C1，C2都改为Valid（程序状态转移图中P-Read(2)使C1Valid，Read-blk(3)使C2 Valid）。l （6）如果(rgu)C1为Invalid，C2为Reserved，则读C1时Read miss，这时发Read-blk信号把 C2C1，C1，C2都改为Valid，其中Read-blk(3)负责把C2由ReservedValid，P-Read(2)负责把C1由InvalidValid。第38页/共101页第三十九页，共102页。40l写的情况：l （1）如果C1为Valid，写C1，则Write hit，发P-write修改C1内容(nirng

28、)，修改memory，发Write-inv(4)给所有Cache，C1变成Reserved状态。l （2）如果C1为Reserved，写C1，则Write hit，发P-write修改C1内容(nirng)，不修改memory，C1状态变为Dirty。l （3）如果C1为Dirty，写C1，则Write hit，发P-write修改C1内容(nirng)，不修改memory，状态仍为Dirty。第39页/共101页第四十页，共102页。41l （4）如果C1为Invalid，C2，C3没有东西，这时memory中有这个(zh ge)地址的数据副本，从memory中读取该副本到C1，再把要写的内

29、容写入C1，这时C1和memory内容不一致，把C1的状态变为Dirty。l （5）如果C1为Invalid，C2为Dirty，这时memory中内容和C2中的内容不一致，把 C2C1，再把要写的内容写入C1，C1Dirty，发Read-inv使其它所有Cache的副本变成无效状态。第40页/共101页第四十一页，共102页。42l （6）如果C1为Invalid，C2为Reserved，这时memory中的内容(nirng)和C2内容(nirng)一致，把C2C1，再把要写的内容(nirng)写入C1，这时C1与memory内容(nirng)不一致，使C1Dirty，发Read-inv使其它

30、所有Cache的副本变成无效状态。第41页/共101页第四十二页，共102页。43lC1的三种(sn zhn)状态的图示:xxcore1xcore2xcore3C1C2C3memoryvalidC1中的副本(fbn)和memory中一致第42页/共101页第四十三页，共102页。44xxcore1Icore2Icore3C1C2C3memoryReservedInvalidC1中的副本和memory中一致(yzh)，都正确第43页/共101页第四十四页，共102页。45xxcore1Icore2Icore3C1C2C3memoryDirtyInvalidC1中的副本和memory不一致，只有(

31、zhyu)C1中的副本正确第44页/共101页第四十五页，共102页。46l其它的一些问题其它的一些问题l Core要向要向Cache写数据，如果写数据，如果write miss，表示该，表示该数据块不在数据块不在Cache中或者该数据快处于无效状态，那么中或者该数据快处于无效状态，那么需要把正确需要把正确(zhngqu)的数据从的数据从memory或其它的或其它的Cache中取过来，然后再写操作。中取过来，然后再写操作。 第45页/共101页第四十六页，共102页。47l 为什么不能直接写？l（1）可能该数据(shj)块根本不在Cache中，所以需要从其它地方调入。l（2）已在Cache中，

32、但数据(shj)不正确，这时如果直接写入数据(shj)，整个数据(shj)块可能还是不正确的。例如，数据(shj)不正确的原因是100号单元数据(shj)已修改，如果要写入一个数据(shj)到101单元，这时不能直接写，否则100号单元还是错的。第46页/共101页第四十七页，共102页。48l Cache Coherence问题概要(giyo)：l多核或多处理机系统l共享存储器lCache块的状态l访问的数据是最新的，不是“过时”的内容第47页/共101页第四十八页，共102页。49lCache Coherence问题l监听总线协议l基于目录的Cache一致性协议l目录的一般性问题l全映射(

33、yngsh)目录l有限目录l链式目录l三种Cache一致性策略第48页/共101页第四十九页，共102页。50基于基于(jy)目录的目录的Cache一致性协议一致性协议l 目录的一般性问题l 一致性协议的开销分析l（1）采用写无效协议l无效后，当其它(qt)Core再读该副本时，出现Read miss，要有开销l（2）采用写更新协议l需要更新所有Cache和memory中的副本，所以开销大，有些Core对更新后的数据可能不会使用。第49页/共101页第五十页，共102页。51l 2. 基于目录的一致性协议的基本思想l当Core个数增加时，一般不用总线结构，而采用多级互连网络。多级互连网络实现广

34、播功能代价很大。l为什么需要(xyo)广播功能？把一致性命令，如Write-inv，Read-inv等命令要发送给所有的Cache。l能不能只发送给存放该副本的Cache?l基于目录的协议的基本思想第50页/共101页第五十一页，共102页。52l 3. 目录的结构目录的结构l（1）目录里放什么）目录里放什么有关有关Cache副本驻副本驻留在哪里的信息：所有共享数据块的所有留在哪里的信息：所有共享数据块的所有Cache副本的地址副本的地址(dzh)表。表。l（2）每个目录项（每个数据结构）包含若）每个目录项（每个数据结构）包含若干个指向这个块（每个数据块有个目录项）的干个指向这个块（每个数据块

35、有个目录项）的Cache副本地址副本地址(dzh)的指针以及一个重写位的指针以及一个重写位（用来说明是否有一个（用来说明是否有一个Cache允许把有关的数允许把有关的数据写入）。据写入）。l（3）基于目录的）基于目录的Cache一致性协议是依靠一一致性协议是依靠一个目录来记录系统之中哪些处理机的个目录来记录系统之中哪些处理机的Cache中中有指定存储块的副本。当一台处理机希望写某有指定存储块的副本。当一台处理机希望写某个共享块时，通过目录向有该块的副本的那些个共享块时，通过目录向有该块的副本的那些处理机处理机“点对点点对点”的发无效信号，使所有其它的的发无效信号，使所有其它的副本无效。副本无效

36、。第51页/共101页第五十二页，共102页。53l 4. 目录的方式l（1）集中目录方式（中心目录）l1976年Tang提出。l用一个中心目录存放所有Cache目录的副本，它能提供为保证(bozhng)一致性所需要的所有信息。l缺点：l容量非常大，必须采用联想方法来检查，冲突多，检索时间长。第52页/共101页第五十三页，共102页。54l（2）分布式目录l1978年Censier和Feautrier提出。l每个存储模块维护各自的目录，目录中记录着每个存储块的当前信息。当前信息指明哪些(nxi)Cache有该存储块的副本。l如下页的图：第53页/共101页第五十四页，共102页。55D1M1

37、D2M2DmMmD1M1D2M2DmMm互连网络(wnglu)第54页/共101页第五十五页，共102页。56l如果(rgu)C2读miss，这时C1中有Dirty的副本，则把它写回memory，内存再给C2一个副本，变成Valid。l如果(rgu)C1写命中，它告诉memory控制器，控制器发无效命令给在D1的当前向量中有记录的所有Cache。第55页/共101页第五十六页，共102页。57l 5. 三种目录l全映射（full map）目录：存放与全局(qunj)存储器中每个块有关的数据。系统中的每个Cache可以同时存储任何数据块的副本，即每个目录项包含N个指针（N是Core数目）。l有限

38、（limited）目录：每个目录项有固定数目的指针（小于N）。l链式（chained）目录：将目录分布到各个Cache（其余同全映射目录）。第56页/共101页第五十七页，共102页。58l全映射目录l 1.目录项结构l 目录项中有N个Core位（对应N台Core）和一个(y )重写位，如下图所示：目录(ml)项：重写位（1位）Core位（N位）l Core位表示(biosh)相应Core的Cache block的状态（存在或不存在）。l 有一个也只有一个Core位为“1”，那么该Core可以对该块进行写操作。第57页/共101页第五十八页，共102页。59l Cache的每个块有两个状态位：

39、l有效位l有效块是否(sh fu)允许写有效(yuxio)1位l Cache的状态位应该(ynggi)和目录项的状态一致。1位允许写目录项：重写位（1位）Core位（N位）Cache状态位：第58页/共101页第五十九页，共102页。60l2.目录的三种情况l我们来看三个Core（三个Cache）的例子(l zi)。l（1）C1，C2，C3都没有单元X的副本Shared Memoryx:c000dataC1Core1C2Core2C3Core3第59页/共101页第六十页，共102页。61l（2）C1，C2，C3同时请求X单元的副本，这时目录项中的三个指针（Core位）被置一，表示这些Cach

40、e中已有数据(shj)副本。l 目录项的重写位被置为未写（c）状态，表示无一Core允许写入该数据(shj)块。Shared Memoryx:c111datax:Core1x:Core2x:Core3C1C2C3第60页/共101页第六十一页，共102页。62l（3）C3请求对该块的写允许权时出现第（3）种情形(qng xing)，重写被置成D状态，且有一个指针指向C3的数据块。Shared Memoryx:D001dataCore1Core2 x:Core3C1C2C3data第61页/共101页第六十二页，共102页。63l3.第二种情况第三种情况的过程l P3向C3发出写请求时：l（1）

41、C3检测出包含单元X的块是有效的，但Cache中的块允许位状态表示不允许Core对该块进行写操作。l（2）C3向包含单元X的存储器模块发出写请求，并暂停P3工作。l（3）该存储器模块发出一个无效(wxio)请求给C1和C2（根据目录项的内容发几个无效(wxio)信号）第62页/共101页第六十三页，共102页。64l（4）C1和C2收到无效请求后，把相应位置1，表示含单元(dnyun)X的块已无效，并发送一个回答信号给请求的存储器模块。l（5）存储器模块收到回答信号后，将重写位置1，清除指向C1、C2的指针，发出允许信号给C3。l（6）C3收到写允许信号后，修改Cache的状态并激活Core3

42、。第63页/共101页第六十四页，共102页。65l4. 目录所占空间l 假设存储器大小和Core个数N成正比，即个数增加时，存储器的模块数也增加，所以数据块的个数也和N成正比。l 另外(ln wi)目录项的大小也和Core数N成正比，所以目录的总所占空间和N2成正比。l 即：l目录项数*项大小 = O ( N2)l 太大不便于扩展。第64页/共101页第六十五页，共102页。66l有限目录l 解决目录过大的问题。l任意一个数据块在Cache中同时(tngsh)存在的副本数量有一定限制，那么目录大小的增加不会超过一个常数。第65页/共101页第六十六页，共102页。67l符号表示法：l Dir

43、iXl i:指针的数量。lX是NB，表示没有广播功能的方案。l DirNNB表示没有广播功能的全映射方式l DiriNB（i N）：使用i个指针的没有广播功能的有限(yuxin)目录协议方式。l 除了多于i个Cache请求读一个特定的数据块的情况外，有限(yuxin)目录协议与全映射协议类似。第66页/共101页第六十七页，共102页。68l 有限目录中指针不是每个Core一位，而是针对Core的二进制标识符进行编码，所以指针占log2N位存储器。l 在全映射方式(fngsh)中，每个Core对应一个指针，所以N个Core一共用了N位，而有限目录中只用log2N位，设N =16，则log216

44、 = 4。l 如果允许两个指针，则需要8位。l 所以目录的存储容量为O（Nlog2N），比全映射容易扩充。第67页/共101页第六十八页，共102页。69l 如果多Core系统中的Core具有局部性，即在任何给定的时间间隔内，只有一小部分Core访问某个给定的存储器字，那么有限目录足以应付这个(zh ge)小的工作Core组了。第68页/共101页第六十九页，共102页。70l链式目录l 用目录指针链来跟踪(gnzng)共享数据副本。l 两种方法，单链法与双链法。l 数据块共享副本的数目并无限制。l 所占的空间及可扩展性同有限目录。l 它的工作原理如下过程所示。第69页/共101页第七十页，共

45、102页。71l（1）P1要读单元X，则memory发送一份副本给C1，同时送给C1一个链结束(jish)指针（CT：Chain Termination），存储器也保存指向C1的指针。Shared Memoryx:cdataCore1Core2Core3C1C2C3x:CTdata第70页/共101页第七十一页，共102页。72l（2）当P2要读单元X时，存储器送一份副本(fbn)给C2，同时送给C2一个指向C1的指针，存储器保存指向C2的指针。Shared Memoryx:cdataCore1Core2Core3C1C2C3x:CTdatax:data第71页/共101页第七十二页，共102

46、页。73l（3）重复以上步骤，所有Cache都得到单元X的副本。l（4）如果Core3要对单元X进行写操作，它必须(bx)沿着链发送一个数据无效信息。为了保证顺序一致性，在有链结束指针的Core回答无效信号之前，存储器模块不给Core3写允许权。l 无效命令从一个Cache到一个Cache顺序进行，不象snoopy协议那样同时发送给所有Cache。第72页/共101页第七十三页，共102页。74l（5）替换。假设C1到CN都有单元X的副本，还假设单元X和单元Y都映射到同一个高速缓存块（直接映射法）。如果Corei要读单元Y，它首先必须把X所在的块从Cache中去掉，这可以采用两种方法：l1）沿

47、着链发一个消息使Ci+1的指针指向(zh xin)Ci-1，这样使Ci从链中去掉（这时Ci中存放Y了）。l 2）使Ci+1到CN中的单元X无效（这时Ci中存放Y了）。第73页/共101页第七十四页，共102页。75l目录占用的存储容量(cn ch rn lin)：l指针的尺寸以Core数目的对数关系增长（这和有限目录相同）log2N，每个Cache块的指针数目与Core个数无关。l第74页/共101页第七十五页，共102页。76l解决Cache一致性的其它办法(bnf)：l（1）不允许有私有 Cache：Shared Cache方案l（2）可写的共享数据不存放在Cache中l第75页/共101

48、页第七十六页，共102页。77lCache Coherence问题(wnt)l监听总线协议l基于目录的Cache一致性协议l三种Cache一致性策略l采用Write-Through策略的Cachel采用Write-Bach策略的Cachel采用Write-Once策略的Cache第76页/共101页第七十七页，共102页。78三种三种(sn zhn)Cache一致性策略一致性策略l采用Write-Through策略的Cachel 数据块的两种状态：l有效和无效(wxio)（指本地Core相应数据块的状态，并非整个Cache的状态。)l 一致性的四种操作：lRr和Wr：其它Core对该数据块（指

49、在其它CoreCache中的数据块）的读写lRl和Wl：是本地Core对该数据块的读写l状态转移图如下：第77页/共101页第七十八页，共102页。79有效(yuxio)无效(wxio)RrWlRlRl, WlWrRr, Wr第78页/共101页第七十九页，共102页。80lCache的数据块为无效时：l 其它Core的任何操作都不会影响本地Cache的这种无效状态；l 只有在本地Core读或者(huzh)写了数据块中的某个数据，即对Cache执行了Read或Write命令时，该数据块的状态才会成为“有效”。第79页/共101页第八十页，共102页。81l Cache的数据块为“有效”时：l

50、本地Core的读、写操作(cozu)，不会影响该状态；l 其它Core对存有相同内容的数据块读，不会影响该状态；l 其它Core对存有相同内容的数据块执行了写操作(cozu)，该数据块状态变成无效。第80页/共101页第八十一页，共102页。82l采用Write-Back策略的Cachel 1.数据块的三种状态l RO (只读）状态：表示整个系统中不止一个副本正确（例如一个在Cache中，一个在memory中）。l 读-写状态：表示整个系统中，只有这个副本是正确的，其它都“过时”（即无效），这说明(shumng)这个 Cache的数据块至少被写过一次，但memory中的内容还没有被修改。l 无

51、效状态：“过时”数据。第81页/共101页第八十二页，共102页。83l2. 一致性的四种操作：l Rr和Wr：其它Core对该数据块（指在其它Core的Cache中的数据块）的读写l Rl和Wl：是本地Core对该数据块的读写l状态(zhungti)转移图如下：第82页/共101页第八十三页，共102页。84l3. 处于RO状态l 本地读，远程读不会改变状态l 本地写，使ROR-W（这时只有一个(y )数据块正确）l 远程写，使RO无效无效(wxio)ROWlWrRl, RrW-R第83页/共101页第八十四页，共102页。85l4. 处于(chy)读-写状态无效(wxio)RORrWrRl

52、,WlW-R第84页/共101页第八十五页，共102页。86l 本地读、写不会改变状态(zhungti)l 远程读：这时只有这个 Cache的数据块是正确的，所以要有“写回”动作（即把内容写回Memory），另外还需要把正确的数据传递给远程读的Core相应的Cache。l两个Cache的状态(zhungti)ROl 远程写：把本地Core的数据块传递给远程Core，远程Core对数据块进行写操作，远程Core对应的Cache状态(zhungti)变为RO，而本地的Cache变为无效状态(zhungti)。第85页/共101页第八十六页，共102页。87l5. 处于(chy)无效状态无效(wxi

53、o)ROWlRr,WrW-RRl第86页/共101页第八十七页，共102页。88l 本地读：无效ROl 本地写：无效WR（同时使其它拥有相同内容的数据块的Cache中相应的数据块的状态变成无效）l 远程(yunchng)写、远程(yunchng)读：不影响状态的改变第87页/共101页第八十八页，共102页。89l采用Write-Once策略(cl)的Cachel 1. Write-Through和Write-Back的缺点l Write-Through策略(cl)的弱点是每次都要修改memory，所以总线流量增大；l Write-Back策略(cl)的弱点是Cache写了一次后，Memory

54、中的内容不一致。第88页/共101页第八十九页，共102页。90l2. Write-Once的基本思想l 把Write-Through和Write-Back两者的优点结合在一起：减少总线流量。l Cache的第一次写采用Write-Through策略（有一个以上的副本正确）；l Cache而后的写采用Write-Back策略（只有一份副本正确）。l 为了区分是否是第一次写，把“读-写”状态分成(fn chn)两个状态：Reserved和Drity。第89页/共101页第九十页，共102页。91l3. 数据块的四种状态l 有效(yuxio)状态（Valid）：相当于Write-Back里的“只读

55、”，从共享存储器中读入的并与存储器副本一致的Cache数据块。l 无效状态（Invalid）：在Cache中找不到或Cache中的数据块内容与共享存储器中的内容不一致的Cache数据块。第90页/共101页第九十一页，共102页。92l 保留状态（Reserved）：数据从共享存储器读入Cache只被写过一次。Cache中的副本(fbn)与共享存储器中的副本(fbn)是一致的，并且它是正确的副本(fbn)。l 重写状态（Dirty）：Cache中的数据块不止一次被写过，此时共享存储器中的数据块也不是正确的数据块，唯一正确的数据块在Cache中。第91页/共101页第九十二页，共102页。93l

56、4. 如果处于“有效(yuxio)”状态有效(yuxio)保留(boli)WrRl, Rr无效Wl重写第92页/共101页第九十三页，共102页。94l（1）本地读Rl，不影响状态。l（2）本地写Wl（第一次写），采用Write-Through策略，这时要发无效命令给其它Cache中相应的副本，并修改memory。l有效保留(boli)l（3）远程写Wr（不管是第几次写），远程CPU会发无效命令：有效无效l（4）远程读Rr：不影响状态。第93页/共101页第九十四页，共102页。95l5. 如果(rgu)处于“保留”状态有效(yuxio)保留(boli)WrRl无效Rr重写Wl第94页/共10

57、1页第九十五页，共102页。96l（1）本地读Rl，不影响状态(zhungti)。l（2）远程读Rr：这时Cache中只有处于保留状态(zhungti)的数据块是正确的，所以把该数据块送到远程Core的Cache中（远程Cache中该数据块变为有效），本数据块状态(zhungti)已变为有效。l （3）本地写Wl：第二次及以后的写，采取Write-Back策略，不修改Memory，状态(zhungti)由Reserved变为Dirty（这时只有一个副本有效），发无效命令给其它Cache的对应的副本，使Memory中的副本也无效。l（4）远程写Wr：远程Core会发无效命令，使状态(zhungt

58、i)由Reserved变为Invalid。第95页/共101页第九十六页，共102页。97l6. 如果(rgu)处于“重写”状态有效(yuxio)保留(boli)WrRr无效Rl，Wl重写第96页/共101页第九十七页，共102页。98l（1）本地读Rl：不影响状态。l（2）本地写Wl：不影响状态。l（3）远程读Rr：这时只有这个Cache的数据块是正确的，所以(suy)把该数据块发送给远程的Cache，远程Cache的数据块和本Cache中的数据块都变得有效。l（4）远程写Wr：远程Core写后，发无效命令使状态由重写无效。第97页/共101页第九十八页，共102页。99l7. 如果(rgu

59、)处于“无效”状态有效(yuxio)保留(boli)RlWr, Rr无效Wl重写第98页/共101页第九十九页，共102页。100l（1）本地(bnd)读Rl：这时产生Read-Miss，设法找到有效的数据块调入Cache：l 如果系统存在处于有效，保留或重写状态的相应数据块，则将其调入本地(bnd)Cachel 如果系统中不存在处于有效、保留或重写状态的相应数据块，则说明共享存储器中的数据块是正确的，直接从共享存储器读入即可。l 读入后相应数据块进入“有效”状态。第99页/共101页第一百页，共102页。101l（2）远程读Rr：状态(zhungti)不变l（3）本地写Wl：一定是Write

60、-Miss，系统首先把正确的内容调入Cache，然后写Cache，因为是第一次写，所以Write-Through策略，同时写memory，将本地Cache状态(zhungti)置为“保留”，同时将系统中其它相应的数据块置为“无效”l（4）远程写Wr：状态(zhungti)不变第100页/共101页第一百零一页，共102页。内容(nirng)总结会计学。（2）Write-inv：在写命中时在总线(zn xin)上广播一个无效命令。（3）Read-inv：在写缺失时在总线(zn xin)上广播一个无效命令。重写位（1位）。重写位（1位）。Core位（N位）。我们来看三个Core（三个Cache）的例子。3.第二种情况第三种情况的过程。两种方法，单链法与双链法。假设C1到CN都有单元X的副本，还假设单元X和单元Y都映射到同一个高速缓存块（直接映射法）。本地读，远程读不会改变状态第一百零二页，共102页。