多核對(duì)操作系統(tǒng)的影響Cache一致性PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1多核對(duì)操作系統(tǒng)的影響多核對(duì)操作系統(tǒng)的影響Cache一致性一致性2第1頁(yè)/共101頁(yè)3lCache Coherence問(wèn)題的提出l在多核和多處理器系統(tǒng)中，多個(gè)Cache對(duì)應(yīng)的copy內(nèi)容應(yīng)該一致：MemoryCachecoreCachecoreCachecore這幾個(gè)copy應(yīng)該一致第2頁(yè)/共101頁(yè)4第3頁(yè)/共101頁(yè)5l共享可寫數(shù)據(jù)的不一致性（sharing of writable data）core1core2更新前xxx核Cachesharedmemorycore1core2寫通過(guò)xxxcore1core2寫回xxxCache和內(nèi)存時(shí)刻保持一致第4頁(yè)/共101頁(yè)6l進(jìn)程遷移的不一

2、致性core1core2遷移前xx核Cachecore1core2寫通過(guò)xxxcore1core2寫回xxx第5頁(yè)/共101頁(yè)7lI/O操作（繞過(guò)Cache的I/O操作）core1core2xx存儲(chǔ)器core1core2寫通過(guò)xxcore1core2寫回xxxxxxxI/O存儲(chǔ)器輸入存儲(chǔ)器輸出c1c2總線第6頁(yè)/共101頁(yè)8第7頁(yè)/共101頁(yè)9第8頁(yè)/共101頁(yè)10 下圖表示數(shù)據(jù)塊x在共享存儲(chǔ)器和三個(gè)核的Cache中的副本一致的情形。x共享存儲(chǔ)器CacheP1xP2xxP3總線核第9頁(yè)/共101頁(yè)11l下圖表示core1進(jìn)行寫無(wú)效操作后的情形。l寫通過(guò)：xI表示無(wú)效core1Icore2xIc

3、ore3共享存儲(chǔ)器Cache總線核第10頁(yè)/共101頁(yè)12l寫回：xI表示無(wú)效core1Icore2IIcore3共享存儲(chǔ)器Cache總線核第11頁(yè)/共101頁(yè)13l下圖表示core1進(jìn)行寫更新操作后的情形（寫通過(guò)）。xI表示無(wú)效core1xcore2xxcore3共享存儲(chǔ)器Cache總線核第12頁(yè)/共101頁(yè)14l寫無(wú)效的問(wèn)題寫無(wú)效的問(wèn)題l主要開銷在兩個(gè)方面：（1）作廢各Cache副本的開銷；（2）由作廢引起缺失造成的開銷，即處理機(jī)需要訪問(wèn)已經(jīng)作廢的數(shù)據(jù)時(shí)將引起Cache的缺失。第13頁(yè)/共101頁(yè)15l寫無(wú)效后果：寫無(wú)效后果：l如果一個(gè)Core經(jīng)常對(duì)某個(gè)塊連續(xù)寫，且Core間對(duì)共享塊的競(jìng)爭(zhēng)

4、較小，這時(shí)寫無(wú)效策略維護(hù)一致性的開銷是很小的。l如發(fā)生嚴(yán)重競(jìng)爭(zhēng)，即Core之間對(duì)某個(gè)地址的共享數(shù)據(jù)競(jìng)爭(zhēng)，將產(chǎn)生較多的作廢，引起更多的作廢缺失。結(jié)果是共享數(shù)據(jù)在各Cache間倒來(lái)倒去，產(chǎn)生顛簸現(xiàn)象，當(dāng)緩存塊比較大時(shí)，這種顛簸現(xiàn)象更為嚴(yán)重。第14頁(yè)/共101頁(yè)16l寫更新的問(wèn)題寫更新的問(wèn)題l由于更新時(shí)，所有的副本均需要更新，開銷很大。第15頁(yè)/共101頁(yè)17第16頁(yè)/共101頁(yè)18監(jiān)聽總線協(xié)議監(jiān)聽總線協(xié)議(Snoopy protocol)l通過(guò)總線監(jiān)聽機(jī)制實(shí)現(xiàn)Cache和共享存儲(chǔ)器之間的一致性。l適用性分析：l適用于具有廣播能力的總線結(jié)構(gòu)多Core系統(tǒng)，允許每個(gè)Core監(jiān)聽其它Core的存儲(chǔ)器訪問(wèn)

5、情況。l只適用于小規(guī)模的多Core系統(tǒng)。第17頁(yè)/共101頁(yè)19l寫一次寫一次(write-once)協(xié)議協(xié)議l寫無(wú)效監(jiān)聽一致性協(xié)議，將寫通過(guò)和寫回策略結(jié)合。l為了減少總線流量，高速緩存塊的第一次寫用寫通過(guò)方法，產(chǎn)生一份正確的主存儲(chǔ)器副本，并使其它的Cache中的副本無(wú)效，之后就采用寫回方法更新Cache與主存儲(chǔ)器。第18頁(yè)/共101頁(yè)20l一致性協(xié)議的內(nèi)容包括一致性協(xié)議的內(nèi)容包括l l（1）Cache可能出現(xiàn)的狀態(tài)集合l（2）共享主存的狀態(tài)l（3）為維護(hù)一致性而引起的狀態(tài)轉(zhuǎn)換。第19頁(yè)/共101頁(yè)21l每份Cache中的副本可能出現(xiàn)的四種狀態(tài) l（1）有效（valid state）：與主存儲(chǔ)

6、器副本一致的Cache副本，即該副本未經(jīng)修改，所以這個(gè)Cache副本不是唯一的副本。l（2）保留（reserved state）：這一Cache副本是第一次修改，并用寫通過(guò)方法寫入主存，所以這一Cache副本和主存儲(chǔ)器副本一致。l（3）重寫（dirty state）：Cache副本不止一次被修改過(guò)，由于不再采用寫通過(guò)方法，所以這個(gè)Cache副本是唯一的副本。與存儲(chǔ)器和其它的Cache副本都不一致。主存儲(chǔ)器中的副本也是無(wú)效的。l（4）無(wú)效（invalid state）與存儲(chǔ)器或其它的Cache副本不一致，或在Cache中找不到。第20頁(yè)/共101頁(yè)22l局部命令（Local commands）

7、l（1）P-Read：本地處理機(jī)讀自己的Cache副本。l（2）P-Write：本地處理機(jī)寫自己的Cache副本。第21頁(yè)/共101頁(yè)23l一致性命令一致性命令l（1）Read-blk：從另一Cache讀一份有效的副本。l（2）Write-inv：在寫命中時(shí)在總線上廣播一個(gè)無(wú)效命令。l（3）Read-inv：在寫缺失時(shí)在總線上廣播一個(gè)無(wú)效命令。第22頁(yè)/共101頁(yè)24lDirty: modified more than once, the only copy in the system;lInvalid: inconsistent copy;lReserved: after written o

8、nce, the only copy consistent with memory;lValid: A copy consistent with the memory copy.lWrite-Once一致性協(xié)議狀態(tài)轉(zhuǎn)移圖一致性協(xié)議狀態(tài)轉(zhuǎn)移圖l其中，四種狀態(tài)的含義如下：第23頁(yè)/共101頁(yè)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:loca

9、l,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頁(yè)/共101頁(yè)26P-Write(1)(1)P-Write(miss: take a dirty copy from a remote cache, or from memory; send Read-inv to inv

10、alidate all copies; update local copy into a dirty one).InvalidValidDirtyReserved第25頁(yè)/共101頁(yè)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 copies become valid).P-Read(2)第

11、26頁(yè)/共101頁(yè)28InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)第27頁(yè)/共101頁(yè)29InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)第28頁(yè)/共101頁(yè)30InvalidValidDirtyReserved(4)Read-inv(A remote cache rea

12、ds a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)第29頁(yè)/共101頁(yè)31lWrite-Once一致性協(xié)議狀態(tài)轉(zhuǎn)移表必是局部進(jìn)行，不影響有效狀態(tài)第一次寫命中，用寫通過(guò)法。同時(shí)修改本地和主存副本并廣播Write-inv使所有副本失效commandcurrentstatenextstatestatusP-Read有效有效Read-hitP-Write有效保留Write-hitaction第二次寫命中，用寫回法。但不修改主存的副本P-Write保留重寫Write-hit第30頁(yè)

13、/共101頁(yè)32寫缺失時(shí)，則從主存或遠(yuǎn)程Cache送來(lái)副本。并廣播Read-inv使所有其它副本無(wú)效。commandcurrentstatenextstatestatusP-Write無(wú)效保留 Write-missactionl（續(xù)表）第二次以后更多的寫命中，用寫回法。無(wú)狀態(tài)改變。P-Write重寫重寫Write-hit第31頁(yè)/共101頁(yè)33寫缺失時(shí)，則從主存或遠(yuǎn)程Cache送來(lái)副本。并廣播Read-inv使所有其它副本無(wú)效。commandcurrentstatenextstatestatusP-Write無(wú)效保留 Write-missactionl（續(xù)表）第二次以后更多的寫命中，用寫回法。

14、無(wú)狀態(tài)改變。P-Write重寫重寫Write-hit第32頁(yè)/共101頁(yè)34commandcurrentstatenextstatestatusactionl（續(xù)表）讀缺失時(shí),如遠(yuǎn)程Cache中沒(méi)有重寫副本，則主存中一定有一份正確的副本，供給發(fā)請(qǐng)求的Cache。如遠(yuǎn)程的Cache有重寫的副本，則它禁止主存操作，并將副本發(fā)給請(qǐng)求的Cache，兩種情況均使發(fā)請(qǐng)求的Cache得到的副本為有效。P-Read無(wú)效有效 Read-miss第33頁(yè)/共101頁(yè)35遠(yuǎn)程Cache讀此副本，讀后兩份副本均有效Read-blk保留或重寫有效commandcurrentstatenextstatestatusact

15、ionl（續(xù)表）寫缺失時(shí)，遠(yuǎn)程Cache讀一個(gè)塊，并修改它，并使所有其它Cache的副本無(wú)效。Read-inv除無(wú)效外的其它狀態(tài)無(wú)效第34頁(yè)/共101頁(yè)36寫命中時(shí)，一遠(yuǎn)程Cache修改其本地副本，并使數(shù)據(jù)塊的其它副本無(wú)效Write-inv有效無(wú)效commandcurrentstatenextstatestatusactionl（續(xù)表）如果副本處于重寫狀態(tài)，必須通過(guò)塊替換寫回主存，否則不產(chǎn)生替換操作Write-inv有效無(wú)效替代第35頁(yè)/共101頁(yè)37l一個(gè)具體的例子一個(gè)具體的例子l如下圖的系統(tǒng)：MemoryC1Core1C2Core2C3Core3第36頁(yè)/共101頁(yè)38l讀的情況：l（1）

16、如果C1為Valid，讀C1，則Read hit，狀態(tài)不變。l（2）如果C1為Reserved，讀C1，則Read hit，狀態(tài)不變。l（3）如果C1為Dirty，讀C1，則Read hit，狀態(tài)不變。l（4）如果C1為Invalid，C2和C3沒(méi)有東西，則讀C1時(shí)Read miss，這時(shí)只有memory中有正確的副本，把它取到C1，C1改為Valid（P-Read負(fù)責(zé)實(shí)現(xiàn)狀態(tài)的改變）。第37頁(yè)/共101頁(yè)39l （5）如果C1為Invalid，C2為Dirty，則讀C1時(shí)Read miss，這時(shí)只有C2中的內(nèi)容是正確的，要發(fā)Read-blk信號(hào)把副本從C2讀到C1，同時(shí)修改memory，把C

17、1，C2都改為Valid（程序狀態(tài)轉(zhuǎn)移圖中P-Read(2)使C1Valid，Read-blk(3)使C2 Valid）。l （6）如果C1為Invalid，C2為Reserved，則讀C1時(shí)Read miss，這時(shí)發(fā)Read-blk信號(hào)把 C2C1，C1，C2都改為Valid，其中Read-blk(3)負(fù)責(zé)把C2由ReservedValid，P-Read(2)負(fù)責(zé)把C1由InvalidValid。第38頁(yè)/共101頁(yè)40l寫的情況：l （1）如果C1為Valid，寫C1，則Write hit，發(fā)P-write修改C1內(nèi)容，修改memory，發(fā)Write-inv(4)給所有Cache，C1變成

18、Reserved狀態(tài)。l （2）如果C1為Reserved，寫C1，則Write hit，發(fā)P-write修改C1內(nèi)容，不修改memory，C1狀態(tài)變?yōu)镈irty。l （3）如果C1為Dirty，寫C1，則Write hit，發(fā)P-write修改C1內(nèi)容，不修改memory，狀態(tài)仍為Dirty。第39頁(yè)/共101頁(yè)41l （4）如果C1為Invalid，C2，C3沒(méi)有東西，這時(shí)memory中有這個(gè)地址的數(shù)據(jù)副本，從memory中讀取該副本到C1，再把要寫的內(nèi)容寫入C1，這時(shí)C1和memory內(nèi)容不一致，把C1的狀態(tài)變?yōu)镈irty。l （5）如果C1為Invalid，C2為Dirty，這時(shí)mem

19、ory中內(nèi)容和C2中的內(nèi)容不一致，把 C2C1，再把要寫的內(nèi)容寫入C1，C1Dirty，發(fā)Read-inv使其它所有Cache的副本變成無(wú)效狀態(tài)。第40頁(yè)/共101頁(yè)42l （6）如果C1為Invalid，C2為Reserved，這時(shí)memory中的內(nèi)容和C2內(nèi)容一致，把C2C1，再把要寫的內(nèi)容寫入C1，這時(shí)C1與memory內(nèi)容不一致，使C1Dirty，發(fā)Read-inv使其它所有Cache的副本變成無(wú)效狀態(tài)。第41頁(yè)/共101頁(yè)43lC1的三種狀態(tài)的圖示:xxcore1xcore2xcore3C1C2C3memoryvalidC1中的副本和memory中一致第42頁(yè)/共101頁(yè)44xxco

20、re1Icore2Icore3C1C2C3memoryReservedInvalidC1中的副本和memory中一致，都正確第43頁(yè)/共101頁(yè)45xxcore1Icore2Icore3C1C2C3memoryDirtyInvalidC1中的副本和memory不一致，只有C1中的副本正確第44頁(yè)/共101頁(yè)46l其它的一些問(wèn)題其它的一些問(wèn)題l Core要向Cache寫數(shù)據(jù)，如果write miss，表示該數(shù)據(jù)塊不在Cache中或者該數(shù)據(jù)快處于無(wú)效狀態(tài)，那么需要把正確的數(shù)據(jù)從memory或其它的Cache中取過(guò)來(lái)，然后再寫操作。 第45頁(yè)/共101頁(yè)47l 為什么不能直接寫？為什么不能直接寫？l

21、（1）可能該數(shù)據(jù)塊根本不在Cache中，所以需要從其它地方調(diào)入。l（2）已在Cache中，但數(shù)據(jù)不正確，這時(shí)如果直接寫入數(shù)據(jù)，整個(gè)數(shù)據(jù)塊可能還是不正確的。例如，數(shù)據(jù)不正確的原因是100號(hào)單元數(shù)據(jù)已修改，如果要寫入一個(gè)數(shù)據(jù)到101單元，這時(shí)不能直接寫，否則100號(hào)單元還是錯(cuò)的。第46頁(yè)/共101頁(yè)48l Cache Coherence問(wèn)題概要：l多核或多處理機(jī)系統(tǒng)l共享存儲(chǔ)器lCache塊的狀態(tài)l訪問(wèn)的數(shù)據(jù)是最新的，不是“過(guò)時(shí)”的內(nèi)容第47頁(yè)/共101頁(yè)49lCache Coherence問(wèn)題l監(jiān)聽總線協(xié)議l基于目錄的Cache一致性協(xié)議l目錄的一般性問(wèn)題l全映射目錄l有限目錄l鏈?zhǔn)侥夸沴三種C

22、ache一致性策略第48頁(yè)/共101頁(yè)50基于目錄的基于目錄的Cache一致性協(xié)議一致性協(xié)議l 目錄的一般性問(wèn)題l 一致性協(xié)議的開銷分析l（1）采用寫無(wú)效協(xié)議l無(wú)效后，當(dāng)其它Core再讀該副本時(shí)，出現(xiàn)Read miss，要有開銷l（2）采用寫更新協(xié)議l需要更新所有Cache和memory中的副本，所以開銷大，有些Core對(duì)更新后的數(shù)據(jù)可能不會(huì)使用。第49頁(yè)/共101頁(yè)51l 2. 基于目錄的一致性協(xié)議的基本思想l當(dāng)Core個(gè)數(shù)增加時(shí)，一般不用總線結(jié)構(gòu)，而采用多級(jí)互連網(wǎng)絡(luò)。多級(jí)互連網(wǎng)絡(luò)實(shí)現(xiàn)廣播功能代價(jià)很大。l為什么需要廣播功能？把一致性命令，如Write-inv，Read-inv等命令要發(fā)送給所

23、有的Cache。l能不能只發(fā)送給存放該副本的Cache?l基于目錄的協(xié)議的基本思想第50頁(yè)/共101頁(yè)52l 3. 目錄的結(jié)構(gòu)目錄的結(jié)構(gòu)l（1）目錄里放什么有關(guān)Cache副本駐留在哪里的信息：所有共享數(shù)據(jù)塊的所有Cache副本的地址表。l（2）每個(gè)目錄項(xiàng)（每個(gè)數(shù)據(jù)結(jié)構(gòu)）包含若干個(gè)指向這個(gè)塊（每個(gè)數(shù)據(jù)塊有個(gè)目錄項(xiàng)）的Cache副本地址的指針以及一個(gè)重寫位（用來(lái)說(shuō)明是否有一個(gè)Cache允許把有關(guān)的數(shù)據(jù)寫入）。l（3）基于目錄的Cache一致性協(xié)議是依靠一個(gè)目錄來(lái)記錄系統(tǒng)之中哪些處理機(jī)的Cache中有指定存儲(chǔ)塊的副本。當(dāng)一臺(tái)處理機(jī)希望寫某個(gè)共享塊時(shí)，通過(guò)目錄向有該塊的副本的那些處理機(jī)“點(diǎn)對(duì)點(diǎn)”的發(fā)無(wú)

24、效信號(hào)，使所有其它的副本無(wú)效。第51頁(yè)/共101頁(yè)53l 4. 目錄的方式l（1）集中目錄方式（中心目錄）l1976年Tang提出。l用一個(gè)中心目錄存放所有Cache目錄的副本，它能提供為保證一致性所需要的所有信息。l缺點(diǎn)：l容量非常大，必須采用聯(lián)想方法來(lái)檢查，沖突多，檢索時(shí)間長(zhǎng)。第52頁(yè)/共101頁(yè)54l（2）分布式目錄l1978年Censier和Feautrier提出。l每個(gè)存儲(chǔ)模塊維護(hù)各自的目錄，目錄中記錄著每個(gè)存儲(chǔ)塊的當(dāng)前信息。當(dāng)前信息指明哪些Cache有該存儲(chǔ)塊的副本。l如下頁(yè)的圖：第53頁(yè)/共101頁(yè)55D1M1D2M2DmMmD1M1D2M2DmMm互連網(wǎng)絡(luò)第54頁(yè)/共101頁(yè)5

25、6l如果C2讀miss，這時(shí)C1中有Dirty的副本，則把它寫回memory，內(nèi)存再給C2一個(gè)副本，變成Valid。l如果C1寫命中，它告訴memory控制器，控制器發(fā)無(wú)效命令給在D1的當(dāng)前向量中有記錄的所有Cache。第55頁(yè)/共101頁(yè)57l 5. 三種目錄l全映射（full map）目錄：存放與全局存儲(chǔ)器中每個(gè)塊有關(guān)的數(shù)據(jù)。系統(tǒng)中的每個(gè)Cache可以同時(shí)存儲(chǔ)任何數(shù)據(jù)塊的副本，即每個(gè)目錄項(xiàng)包含N個(gè)指針（N是Core數(shù)目）。l有限（limited）目錄：每個(gè)目錄項(xiàng)有固定數(shù)目的指針（小于N）。l鏈?zhǔn)剑╟hained）目錄：將目錄分布到各個(gè)Cache（其余同全映射目錄）。第56頁(yè)/共101頁(yè)58

26、l全映射目錄l 1.目錄項(xiàng)結(jié)構(gòu)l 目錄項(xiàng)中有N個(gè)Core位（對(duì)應(yīng)N臺(tái)Core）和一個(gè)重寫位，如下圖所示：目錄項(xiàng)：重寫位（1位）Core位（N位）l Core位表示相應(yīng)Core的Cache block的狀態(tài)（存在或不存在）。l 有一個(gè)也只有一個(gè)Core位為“1”，那么該Core可以對(duì)該塊進(jìn)行寫操作。第57頁(yè)/共101頁(yè)59l Cache的每個(gè)塊有兩個(gè)狀態(tài)位：l有效位l有效塊是否允許寫有效1位l Cache的狀態(tài)位應(yīng)該和目錄項(xiàng)的狀態(tài)一致。1位允許寫目錄項(xiàng)：重寫位（1位）Core位（N位）Cache狀態(tài)位：第58頁(yè)/共101頁(yè)60l2.目錄的三種情況l我們來(lái)看三個(gè)Core（三個(gè)Cache）的例子。l

27、（1）C1，C2，C3都沒(méi)有單元X的副本Shared Memoryx:c000dataC1Core1C2Core2C3Core3第59頁(yè)/共101頁(yè)61l（2）C1，C2，C3同時(shí)請(qǐng)求X單元的副本，這時(shí)目錄項(xiàng)中的三個(gè)指針（Core位）被置一，表示這些Cache中已有數(shù)據(jù)副本。l 目錄項(xiàng)的重寫位被置為未寫（c）狀態(tài)，表示無(wú)一Core允許寫入該數(shù)據(jù)塊。Shared Memoryx:c111datax:Core1x:Core2x:Core3C1C2C3第60頁(yè)/共101頁(yè)62l（3）C3請(qǐng)求對(duì)該塊的寫允許權(quán)時(shí)出現(xiàn)第（3）種情形，重寫被置成D狀態(tài)，且有一個(gè)指針指向C3的數(shù)據(jù)塊。Shared Memor

28、yx:D001dataCore1Core2 x:Core3C1C2C3data第61頁(yè)/共101頁(yè)63l3.第二種情況第三種情況的過(guò)程l P3向C3發(fā)出寫請(qǐng)求時(shí)：l（1）C3檢測(cè)出包含單元X的塊是有效的，但Cache中的塊允許位狀態(tài)表示不允許Core對(duì)該塊進(jìn)行寫操作。l（2）C3向包含單元X的存儲(chǔ)器模塊發(fā)出寫請(qǐng)求，并暫停P3工作。l（3）該存儲(chǔ)器模塊發(fā)出一個(gè)無(wú)效請(qǐng)求給C1和C2（根據(jù)目錄項(xiàng)的內(nèi)容發(fā)幾個(gè)無(wú)效信號(hào)）第62頁(yè)/共101頁(yè)64l（4）C1和C2收到無(wú)效請(qǐng)求后，把相應(yīng)位置1，表示含單元X的塊已無(wú)效，并發(fā)送一個(gè)回答信號(hào)給請(qǐng)求的存儲(chǔ)器模塊。l（5）存儲(chǔ)器模塊收到回答信號(hào)后，將重寫位置1，清除

29、指向C1、C2的指針，發(fā)出允許信號(hào)給C3。l（6）C3收到寫允許信號(hào)后，修改Cache的狀態(tài)并激活Core3。第63頁(yè)/共101頁(yè)65l4. 目錄所占空間l 假設(shè)存儲(chǔ)器大小和Core個(gè)數(shù)N成正比，即個(gè)數(shù)增加時(shí)，存儲(chǔ)器的模塊數(shù)也增加，所以數(shù)據(jù)塊的個(gè)數(shù)也和N成正比。l 另外目錄項(xiàng)的大小也和Core數(shù)N成正比，所以目錄的總所占空間和N2成正比。l 即：l目錄項(xiàng)數(shù)*項(xiàng)大小 = O ( N2)l 太大不便于擴(kuò)展。第64頁(yè)/共101頁(yè)66l有限目錄l 解決目錄過(guò)大的問(wèn)題。l任意一個(gè)數(shù)據(jù)塊在Cache中同時(shí)存在的副本數(shù)量有一定限制，那么目錄大小的增加不會(huì)超過(guò)一個(gè)常數(shù)。第65頁(yè)/共101頁(yè)67l符號(hào)表示法：l

30、 DiriXl i:指針的數(shù)量。lX是NB，表示沒(méi)有廣播功能的方案。l DirNNB表示沒(méi)有廣播功能的全映射方式l DiriNB（i N）：使用i個(gè)指針的沒(méi)有廣播功能的有限目錄協(xié)議方式。l 除了多于i個(gè)Cache請(qǐng)求讀一個(gè)特定的數(shù)據(jù)塊的情況外，有限目錄協(xié)議與全映射協(xié)議類似。第66頁(yè)/共101頁(yè)68l 有限目錄中指針不是每個(gè)Core一位，而是針對(duì)Core的二進(jìn)制標(biāo)識(shí)符進(jìn)行編碼，所以指針占log2N位存儲(chǔ)器。l 在全映射方式中，每個(gè)Core對(duì)應(yīng)一個(gè)指針，所以N個(gè)Core一共用了N位，而有限目錄中只用log2N位，設(shè)N =16，則log216 = 4。l 如果允許兩個(gè)指針，則需要8位。l 所以目錄的

31、存儲(chǔ)容量為O（Nlog2N），比全映射容易擴(kuò)充。第67頁(yè)/共101頁(yè)69l 如果多Core系統(tǒng)中的Core具有局部性，即在任何給定的時(shí)間間隔內(nèi)，只有一小部分Core訪問(wèn)某個(gè)給定的存儲(chǔ)器字，那么有限目錄足以應(yīng)付這個(gè)小的工作Core組了。第68頁(yè)/共101頁(yè)70l鏈?zhǔn)侥夸沴 用目錄指針鏈來(lái)跟蹤共享數(shù)據(jù)副本。l 兩種方法，單鏈法與雙鏈法。l 數(shù)據(jù)塊共享副本的數(shù)目并無(wú)限制。l 所占的空間及可擴(kuò)展性同有限目錄。l 它的工作原理如下過(guò)程所示。第69頁(yè)/共101頁(yè)71l（1）P1要讀單元X，則memory發(fā)送一份副本給C1，同時(shí)送給C1一個(gè)鏈結(jié)束指針（CT：Chain Termination），存儲(chǔ)器也保存

32、指向C1的指針。Shared Memoryx:cdataCore1Core2Core3C1C2C3x:CTdata第70頁(yè)/共101頁(yè)72l（2）當(dāng)P2要讀單元X時(shí)，存儲(chǔ)器送一份副本給C2，同時(shí)送給C2一個(gè)指向C1的指針，存儲(chǔ)器保存指向C2的指針。Shared Memoryx:cdataCore1Core2Core3C1C2C3x:CTdatax:data第71頁(yè)/共101頁(yè)73l（3）重復(fù)以上步驟，所有Cache都得到單元X的副本。l（4）如果Core3要對(duì)單元X進(jìn)行寫操作，它必須沿著鏈發(fā)送一個(gè)數(shù)據(jù)無(wú)效信息。為了保證順序一致性，在有鏈結(jié)束指針的Core回答無(wú)效信號(hào)之前，存儲(chǔ)器模塊不給Core

33、3寫允許權(quán)。l 無(wú)效命令從一個(gè)Cache到一個(gè)Cache順序進(jìn)行，不象snoopy協(xié)議那樣同時(shí)發(fā)送給所有Cache。第72頁(yè)/共101頁(yè)74l（5）替換。假設(shè)C1到CN都有單元X的副本，還假設(shè)單元X和單元Y都映射到同一個(gè)高速緩存塊（直接映射法）。如果Corei要讀單元Y，它首先必須把X所在的塊從Cache中去掉，這可以采用兩種方法：l1）沿著鏈發(fā)一個(gè)消息使Ci+1的指針指向Ci-1，這樣使Ci從鏈中去掉（這時(shí)Ci中存放Y了）。l 2）使Ci+1到CN中的單元X無(wú)效（這時(shí)Ci中存放Y了）。第73頁(yè)/共101頁(yè)75l目錄占用的存儲(chǔ)容量：l指針的尺寸以Core數(shù)目的對(duì)數(shù)關(guān)系增長(zhǎng)（這和有限目錄相同）l

34、og2N，每個(gè)Cache塊的指針數(shù)目與Core個(gè)數(shù)無(wú)關(guān)。l第74頁(yè)/共101頁(yè)76l解決Cache一致性的其它辦法：l（1）不允許有私有 Cache：Shared Cache方案l（2）可寫的共享數(shù)據(jù)不存放在Cache中l(wèi)第75頁(yè)/共101頁(yè)77lCache Coherence問(wèn)題l監(jiān)聽總線協(xié)議l基于目錄的Cache一致性協(xié)議l三種Cache一致性策略l采用Write-Through策略的Cachel采用Write-Bach策略的Cachel采用Write-Once策略的Cache第76頁(yè)/共101頁(yè)78三種三種Cache一致性策略一致性策略l采用Write-Through策略的Cachel

35、數(shù)據(jù)塊的兩種狀態(tài)：l有效和無(wú)效（指本地Core相應(yīng)數(shù)據(jù)塊的狀態(tài)，并非整個(gè)Cache的狀態(tài)。)l 一致性的四種操作：lRr和Wr：其它Core對(duì)該數(shù)據(jù)塊（指在其它CoreCache中的數(shù)據(jù)塊）的讀寫lRl和Wl：是本地Core對(duì)該數(shù)據(jù)塊的讀寫l狀態(tài)轉(zhuǎn)移圖如下：第77頁(yè)/共101頁(yè)79有效無(wú)效RrWlRlRl, WlWrRr, Wr第78頁(yè)/共101頁(yè)80lCache的數(shù)據(jù)塊為無(wú)效時(shí)：l 其它Core的任何操作都不會(huì)影響本地Cache的這種無(wú)效狀態(tài)；l 只有在本地Core讀或者寫了數(shù)據(jù)塊中的某個(gè)數(shù)據(jù)，即對(duì)Cache執(zhí)行了Read或Write命令時(shí)，該數(shù)據(jù)塊的狀態(tài)才會(huì)成為“有效”。第79頁(yè)/共101

36、頁(yè)81l Cache的數(shù)據(jù)塊為“有效”時(shí)：l 本地Core的讀、寫操作，不會(huì)影響該狀態(tài)；l 其它Core對(duì)存有相同內(nèi)容的數(shù)據(jù)塊讀，不會(huì)影響該狀態(tài)；l 其它Core對(duì)存有相同內(nèi)容的數(shù)據(jù)塊執(zhí)行了寫操作，該數(shù)據(jù)塊狀態(tài)變成無(wú)效。第80頁(yè)/共101頁(yè)82l采用Write-Back策略的Cachel 1.數(shù)據(jù)塊的三種狀態(tài)l RO (只讀）狀態(tài)：表示整個(gè)系統(tǒng)中不止一個(gè)副本正確（例如一個(gè)在Cache中，一個(gè)在memory中）。l 讀-寫狀態(tài)：表示整個(gè)系統(tǒng)中，只有這個(gè)副本是正確的，其它都“過(guò)時(shí)”（即無(wú)效），這說(shuō)明這個(gè) Cache的數(shù)據(jù)塊至少被寫過(guò)一次，但memory中的內(nèi)容還沒(méi)有被修改。l 無(wú)效狀態(tài)：“過(guò)時(shí)”數(shù)

37、據(jù)。第81頁(yè)/共101頁(yè)83l2. 一致性的四種操作：l Rr和Wr：其它Core對(duì)該數(shù)據(jù)塊（指在其它Core的Cache中的數(shù)據(jù)塊）的讀寫l Rl和Wl：是本地Core對(duì)該數(shù)據(jù)塊的讀寫l狀態(tài)轉(zhuǎn)移圖如下：第82頁(yè)/共101頁(yè)84l3. 處于RO狀態(tài)l 本地讀，遠(yuǎn)程讀不會(huì)改變狀態(tài)l 本地寫，使ROR-W（這時(shí)只有一個(gè)數(shù)據(jù)塊正確）l 遠(yuǎn)程寫，使RO無(wú)效無(wú)效ROWlWrRl, RrW-R第83頁(yè)/共101頁(yè)85l4. 處于讀-寫狀態(tài)無(wú)效RORrWrRl,WlW-R第84頁(yè)/共101頁(yè)86l 本地讀、寫不會(huì)改變狀態(tài)l 遠(yuǎn)程讀：這時(shí)只有這個(gè) Cache的數(shù)據(jù)塊是正確的，所以要有“寫回”動(dòng)作（即把內(nèi)容寫回

38、Memory），另外還需要把正確的數(shù)據(jù)傳遞給遠(yuǎn)程讀的Core相應(yīng)的Cache。l兩個(gè)Cache的狀態(tài)ROl 遠(yuǎn)程寫：把本地Core的數(shù)據(jù)塊傳遞給遠(yuǎn)程Core，遠(yuǎn)程Core對(duì)數(shù)據(jù)塊進(jìn)行寫操作，遠(yuǎn)程Core對(duì)應(yīng)的Cache狀態(tài)變?yōu)镽O，而本地的Cache變?yōu)闊o(wú)效狀態(tài)。第85頁(yè)/共101頁(yè)87l5. 處于無(wú)效狀態(tài)無(wú)效ROWlRr,WrW-RRl第86頁(yè)/共101頁(yè)88l 本地讀：無(wú)效ROl 本地寫：無(wú)效WR（同時(shí)使其它擁有相同內(nèi)容的數(shù)據(jù)塊的Cache中相應(yīng)的數(shù)據(jù)塊的狀態(tài)變成無(wú)效）l 遠(yuǎn)程寫、遠(yuǎn)程讀：不影響狀態(tài)的改變第87頁(yè)/共101頁(yè)89l采用Write-Once策略的Cachel 1. Write

39、-Through和Write-Back的缺點(diǎn)l Write-Through策略的弱點(diǎn)是每次都要修改memory，所以總線流量增大；l Write-Back策略的弱點(diǎn)是Cache寫了一次后，Memory中的內(nèi)容不一致。第88頁(yè)/共101頁(yè)90l2. Write-Once的基本思想l 把Write-Through和Write-Back兩者的優(yōu)點(diǎn)結(jié)合在一起：減少總線流量。l Cache的第一次寫采用Write-Through策略（有一個(gè)以上的副本正確）；l Cache而后的寫采用Write-Back策略（只有一份副本正確）。l 為了區(qū)分是否是第一次寫，把“讀-寫”狀態(tài)分成兩個(gè)狀態(tài)：Reserved和Drity。第89頁(yè)/共101頁(yè)91l3. 數(shù)據(jù)塊的四種狀態(tài)l 有效狀態(tài)（Valid）：相當(dāng)于Write-Back里的“只讀”，從共享存儲(chǔ)器中讀入的并與存儲(chǔ)器副本一致的Cache數(shù)據(jù)塊。l 無(wú)效狀態(tài)