版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
計(jì)算機(jī)科學(xué)與技術(shù)系研究生課程
高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)
清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系高性能計(jì)算研究所
鄭緯民教授
2007年11月
高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)
第一章高等計(jì)算機(jī)的核心技術(shù)——并行處理
第二章加速比性能模型與可擴(kuò)展性分析
第三章互連與通信
第四章劃分與調(diào)度
第五章并行存儲(chǔ)器系統(tǒng)
第六章CacheCoherence
第七章MemoryConsistency
第八章指令級(jí)并行處理
第六章CacheCoherence
6.1CacheCoherence問(wèn)題
6.1.1CacheCoherence的提出
6.1.2多個(gè)Cache不一致的原因
6.1.3兩種設(shè)計(jì)Cache一致性協(xié)議策略
6.2監(jiān)聽(tīng)總線(xiàn)協(xié)議
6.3基于目錄的Cache一致性協(xié)議
6.4三種Cache一致性策略
6.1CacheCoherence問(wèn)題
6.1.1CacheCoherence問(wèn)題的提出
在多處理器系統(tǒng)中,多個(gè)Cache中,對(duì)應(yīng)
的copy內(nèi)容應(yīng)該一致,如下圖:
6.1.2多個(gè)Cache不一致的原因
1.共享可寫(xiě)數(shù)據(jù)的不一致性(sharingof
writabledata)
處理機(jī)
Cache
shared
memory
更新前寫(xiě)通過(guò)寫(xiě)回
2.進(jìn)程遷移的不一致性
處理機(jī)
Cache
遷移前寫(xiě)通過(guò)寫(xiě)回
上圖中:
右圖為:包含共享變量X的進(jìn)程原來(lái)在P1
上運(yùn)行,并對(duì)X進(jìn)行了修改(但采取寫(xiě)回策
略)所以暫時(shí)沒(méi)有修改Memory),由于某
種原因遷移到P2,修改過(guò)的X,仍在P1的
Cache中,P2運(yùn)行時(shí)從Memory中得到x,這
個(gè)x其實(shí)是“過(guò)時(shí)”的,所以造成了不一致。
中間圖為:P2中運(yùn)行的進(jìn)程對(duì)x進(jìn)行了修
改)采取寫(xiě)通過(guò)策略,所以把Memory中的x
也修改為x-由于某種原因該進(jìn)程遷移到PL
但P1的Cache中仍為x,所以造成不一致。
3.I/O操作(繞過(guò)Cache的I/O操作)
存儲(chǔ)器I/O
寫(xiě)通過(guò)寫(xiě)回
上圖中:
中間圖為:當(dāng)I/O處理機(jī)將一個(gè)新的數(shù)據(jù)父
寫(xiě)入主存儲(chǔ)器時(shí),繞過(guò)采用寫(xiě)通過(guò)策略的
cache,則Cl和共享存儲(chǔ)器之間產(chǎn)生了不一
致。
右圖為:直接從主存儲(chǔ)器輸出數(shù)據(jù)時(shí)(繞
過(guò)Cache),采用寫(xiě)回策略的高速緩存產(chǎn)生
不'一致性。
6.1.3兩種設(shè)計(jì)Cache一致性協(xié)議策略
1.寫(xiě)無(wú)效(writeinvalidate)
任一處理器寫(xiě)它的私有Cache時(shí),它都使所
有其它的Cache中的副本失效。
對(duì)Write-through)它也更新memory中的副
本(最終是一個(gè)Cache中的副本和memory中的
副本是有效的)。
對(duì)Write-back,它使memory中的副本也失
效(最終只有一個(gè)Cache中的副本是有效的)。
2.寫(xiě)更新(writeupdate)
任一處理器寫(xiě)它的私有Cache時(shí),它都立即
更新所有其它的Cache中的副本。
對(duì)Write-through5它也更新主存儲(chǔ)器中的副
本。
對(duì)Write-back,對(duì)存儲(chǔ)器中副本的更新延遲
到這個(gè)Cache被置換的時(shí)刻。
寫(xiě)回:
4,寫(xiě)無(wú)效的問(wèn)題
主要開(kāi)銷(xiāo)在兩個(gè)方面:
(1)作廢各Cache副本的開(kāi)銷(xiāo);
(2)由作廢引起缺失造成的開(kāi)銷(xiāo),即處理
機(jī)需要訪(fǎng)問(wèn)已經(jīng)作廢的數(shù)據(jù)時(shí)將引起Cache的
缺失。
后果:
如果一個(gè)處理機(jī)經(jīng)常對(duì)某個(gè)塊連續(xù)寫(xiě),且各
處理處理機(jī)間對(duì)共享塊的競(jìng)爭(zhēng)較小,這時(shí)寫(xiě)無(wú)
效策略維護(hù)一致性的開(kāi)銷(xiāo)是很小的。如發(fā)生嚴(yán)
重競(jìng)爭(zhēng),即處理機(jī)之間對(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)重。
5.寫(xiě)更新的問(wèn)題
由于更新時(shí))所有的副本均需要更新)開(kāi)
銷(xiāo)很大。
第六章CacheCoherence
6.1CacheCoherence問(wèn)題
6.2監(jiān)聽(tīng)總線(xiàn)協(xié)議
6.2.1寫(xiě)一次協(xié)議
6.3基于目錄的Cache一致性協(xié)議
6.4三種Cache一致性策略
6.2監(jiān)聽(tīng)總線(xiàn)協(xié)議(Snoopyprotocol)
通過(guò)總線(xiàn)監(jiān)聽(tīng)機(jī)制實(shí)現(xiàn)Cache和共享存儲(chǔ)
器之間的一致性。
適用性分析:m■
適用于具有廣播能力的總線(xiàn)結(jié)構(gòu)多機(jī)系統(tǒng),
允許每臺(tái)處理機(jī)監(jiān)聽(tīng)其它處理機(jī)的存儲(chǔ)器訪(fǎng)
問(wèn)情況。
只適用于小規(guī)模的多處理機(jī)系統(tǒng)。
6.2.1寫(xiě)一次(write-once)協(xié)議
寫(xiě)無(wú)效監(jiān)聽(tīng)一致性協(xié)議,將寫(xiě)通過(guò)和寫(xiě)回
策略結(jié)合。
為了減少總線(xiàn)流量,高速緩存塊的第一次
寫(xiě)用寫(xiě)通過(guò)方法,產(chǎn)生一份正確的主存儲(chǔ)器
副本,并使其它的Cache中的副本無(wú)效)之
后就采用寫(xiě)回方法更新Cache與主存儲(chǔ)器。
1.一致性協(xié)議的內(nèi)容
一致性協(xié)議包括:
(1)Cache可能出現(xiàn)的狀態(tài)集合M
(2)共享主存的狀態(tài)
(3)為維護(hù)一致性而引起的狀態(tài)轉(zhuǎn)換。
2.每份Cache中的副本可能出現(xiàn)的四種狀態(tài)
(1)有效(validstate):與主存儲(chǔ)器副本
一致的Cache副本,即該副本未經(jīng)修改)所
以這個(gè)Cache副本不是唯一的副本。
(2)保留(reservedstate):這一Cache副
本是第一次修改,并用寫(xiě)通過(guò)方法寫(xiě)入主存,
所以這一Cache副本和主存儲(chǔ)器副本一致。
(3)重寫(xiě)(dirtystate):Cache副本不止
一次被修改過(guò),由于不再采用寫(xiě)通過(guò)方法,
所以這個(gè)Cache副本是唯一的副本。與存儲(chǔ)
器和其它的Cache副本都不一致。主存儲(chǔ)器
中的副本也是無(wú)效的。
(4)無(wú)效(invalidstate)與存儲(chǔ)器或其它
的Cache副本不一致)或在Cache中找不到。
3.局部命令(Localcommands)
(1)P-Read:本地處理機(jī)讀自己的Cache
副本。
(2)P-Write:本地處理機(jī)寫(xiě)自己的Cache
副本。
4.一致性命令
(1)Read-blk:從另一Cache讀一份有效
的副本。
(2)Write-inv:在寫(xiě)命中時(shí)在總線(xiàn)上廣
播一個(gè)無(wú)效命令。
(3)Read-inv:在寫(xiě)缺失時(shí)在總線(xiàn)上廣播
一個(gè)無(wú)效命令。
5.Write-Once一致性協(xié)議狀態(tài)轉(zhuǎn)移圖
其中,四種狀態(tài)的含義如下:
Dirty:modifiedmorethanonce,theonly
copyinthesystem;
Invalid:inconsistentcopy;
Reserved:afterwrittenonce,theonlycopy
consistentwithmemory;
Valid:Acopyconsistentwiththememory
copy.
P-Read
Read-inv(4)/Write-inv(5)(hit:always
local,
InvalidP-Read(2)Validnostate
transition)
'、、、Read-inv(4)
P-Write
(hit:local,update
Read-inv;;
Read-blkmemorycopy,
(4);P-Write(l)/
(3);broadcast
write-inv
Read-blk(3)toallcache,
DirtyReservedlocalcopy
P-Writebecomes
-Write(hitdocal,notmemoryreserved)
(hit:localstilldirty)update,localcopybecomesdirty)
工
(用鼠標(biāo)點(diǎn)擊連線(xiàn)來(lái)察看詳細(xì)信息)衛(wèi)
衛(wèi)
copybecomevalid).
衛(wèi)
(4)Read-inv(Aremotecachereadsablockduringawrite-miss,
updatesitandinvalidatesallothercopies).X
衛(wèi)
(4)Read-inv(Aremotecachereadsablockduringawrite-miss,
updatesitandinvalidatesallothercopies).X
衛(wèi)
(4)Read-inv(Aremotecachereadsablockduringawrite-miss,
updatesitandinvalidatesallothercopies).
(5)Write-inv(AremotecacheupdatesitslocalcopyduringaX
write-hitsandinvalidatesallothercopies).
衛(wèi)
(l)P-Write(miss:takeadirtycopyfroma
remotecachewhichthenupdatesmemory,or
frommemory;sendRead-invtoinvalidateall
copies;updatelocalcopyintoadirtyone).
(2)P-Read(miss:ifnodirtycopyexists,
memorysuppliesavalidcopy,otherwise,the
cacheinhibitsmemoryandsuppliesacopyand
updatesmemory.Bothcopiesbecomevalid).
(3)Read-blk(readfromremoteprocessors,
thelocalcopybecomevalid).
(4)Read-inv(Aremotecachereadsablock
duringawrite-miss,updatesitandinvalidates
allothercopies).
(5)Write-inv(Aremotecacheupdatesitslocal
copyduringawrite-hitsandinvalidatesall
othercopies).
6.Write-Once-'致性協(xié)議狀態(tài)轉(zhuǎn)移表
currentnext
commandstatestatestatusaction
必是局部進(jìn)行,
P-Read有效有效Read-hit
不影響有效狀態(tài)
第一'次寫(xiě)命中,用
P-Write有效保留Write-hit
寫(xiě)通過(guò)法。同時(shí)修
改本地和主存副本
并廣播Write-inv
使月副本失效
第二次寫(xiě)命中,用
P-Write保留重寫(xiě)Write-hit
寫(xiě)回法。但不修改
主存的副本
(續(xù)表)
currentnext
commandstatestatestatusaction
第二次以后更多的
P-Write重寫(xiě)重寫(xiě)Write-hit
寫(xiě)命中,用寫(xiě)回法。
無(wú)狀態(tài)改變。
,寫(xiě)缺失時(shí),則從主存
P-Write無(wú)效保留,Write-mist;或遠(yuǎn)程Cache送來(lái)副本
o并廣播Read-inv
使所有其它副本無(wú)效。
(續(xù)表)
currentnext
commandstatestatestatusaction
讀缺失時(shí),如遠(yuǎn)程Cache
P-Read無(wú)效有效Read-miss
中沒(méi)有重寫(xiě)副本,則主
存中一定有一份正確的
副本,供給發(fā)請(qǐng)求的
Cacheo如遠(yuǎn)程的Cache
有重寫(xiě)的副本,則它禁
止主存操作,并將副本
發(fā)給請(qǐng)求的Cache,兩種
情況均使發(fā)請(qǐng)求的Cache
得到的副本為有效。
(續(xù)表)
currentnext
commandstatestatestatusaction
保留或遠(yuǎn)程Cache讀此副本,
Read-blk有效
重寫(xiě)讀后兩份副本均有效
寫(xiě)缺失時(shí),遠(yuǎn)程Cache
除無(wú)效
讀一個(gè)塊,并修改它,
Read-inv外的其無(wú)效
并使所有其它Cache的
它狀態(tài)
副本無(wú)效。
(續(xù)表)
currentnext
commandstatestatestatusaction
寫(xiě)命中時(shí),一遠(yuǎn)程Cache
Write-inv有效無(wú)效修改其本地副本,并使
數(shù)據(jù)塊的其它副本無(wú)效
如果副本處于重寫(xiě)狀態(tài),
Write-inv有效無(wú)效替代必須通過(guò)塊替換寫(xiě)回主
存,否則不產(chǎn)生替換操作
7.一個(gè)具體的例子
如下圖的系統(tǒng):
讀的情況:
(1)如果Cl為Valid,讀CL則Readhit,
狀態(tài)不變。.
(2)4□果C1為Reserved,讀CL則Readhit,
狀態(tài)不變。
(3)如果C1為Dirty,讀CL則Readhit,
狀態(tài)不變?!?/p>
(4)如果C1為Invalid,C2和C3沒(méi)有東西,
則讀C1時(shí)Readmiss,這時(shí)只有memory中有正
確的副本,把它取到Cl,C1改為Valid(P-
Read負(fù)責(zé)實(shí)現(xiàn)狀態(tài)的改變)。
(5)4□果Cl為Invalid,C2為Dirty,則讀Cl
時(shí)Readmiss,這時(shí)只有C2中的內(nèi)容是正確的,
要發(fā)Read-blk信號(hào)把副本從C2讀到CL同時(shí)
不多改memory,才巴Cl,C2都改為Valid(程序
狀態(tài)轉(zhuǎn)移圖中P-Read(2)使C1-Valid,Read-
blk(3)使C2-Valid)。
(6)如果Cl為Invalid,C2為Reserved,貝I
讀C1時(shí)Readmiss)這時(shí)發(fā)Read-blk信號(hào)把
C29CLCl,C2都改為Valid,其中Read-
blk(3)負(fù)責(zé)才巴C2由ReservedfValid,P-Read(2)
負(fù)責(zé)》巴C1由InvalidfValid。
寫(xiě)的情況:
(1)如果Cl為Valid,寫(xiě)Cl,則Writehit,I
發(fā)P-write修改C1內(nèi)容)修改memory)發(fā)
Write-inv⑷給所有Cache5C1變成Reserved狀
態(tài)。
(2)如果C1為Reserved,寫(xiě)CL貝UWritehit,
發(fā)P-write修改C1內(nèi)容,不修改memory,C1狀
態(tài)變?yōu)镈irty。
(3)如果Cl為Dirty,寫(xiě)Cl,則Writehit,
發(fā)P-write修改Cl內(nèi)容,不修改memory,狀態(tài)
仍為Dirty。
(4)如果Cl為Invalid,C2,C3沒(méi)有東西,
這時(shí)memory中有這個(gè)地址的數(shù)據(jù)副本,從
memory中讀取該副本到C1,再把要寫(xiě)的內(nèi)容
寫(xiě)入C1)這時(shí)C1和memory內(nèi)容不一'致,才巴
C1的狀態(tài)變?yōu)镈irty。
(5)如果Cl為Invalid,C2為Dirty,這時(shí)
memory中內(nèi)容和C;中的內(nèi)容不一致)把
C2.CL再把要寫(xiě)的內(nèi)容寫(xiě)入CL
ClfDirty)發(fā)Read-inv使其它所有Cache的副
本變成無(wú)效狀態(tài)。
(6)如果C1為Invalid,C2為Reserved,這
時(shí)memory中的內(nèi)容和C2內(nèi)容一致,把
C2fCL再把要寫(xiě)的內(nèi)容寫(xiě)入CL這時(shí)C1
與memory內(nèi)容不一致,使ClfDirty,發(fā)
Read-inv使其它所有Cache的副本變成無(wú)效狀
態(tài)。
C1的三種狀態(tài)的圖示:
valid
Cl中的副本和memory中一致
ReservedInvalid
Cl中的副本和memory中一致,都正確
DirtyInvalid
Cl中的副本和memory不一致)
只有Cl中的副采正確
8.其它的一些問(wèn)題
CPU要向Cache寫(xiě)數(shù)據(jù),如果writemiss,表
示該數(shù)據(jù)塊不在Cache中或者該數(shù)據(jù)快處于無(wú)
效狀態(tài),那么需要把正確的數(shù)據(jù)從memory或
其它的Cache中取過(guò)來(lái),然后再寫(xiě)操作。
為什么不能直接寫(xiě)?
(1)可能該數(shù)據(jù)塊根本不在Cache中,所
以需要從其它地方調(diào)入。
(2)已在Cache中,但數(shù)據(jù)不正確,這時(shí)
如果直接寫(xiě)入數(shù)據(jù),整個(gè)數(shù)據(jù)塊可能還是不
正確的。例如,數(shù)據(jù)不正確的原因是100號(hào)單
元數(shù)據(jù)已修改,如果要寫(xiě)入一個(gè)數(shù)據(jù)到101單
元,這時(shí)不能直接寫(xiě),否則100號(hào)單元還是錯(cuò)
的。
CacheCoherence問(wèn)題彳既要:
多處理機(jī)系統(tǒng)
共享存儲(chǔ)器
Cache塊的狀態(tài)
訪(fǎng)問(wèn)的數(shù)據(jù)是最新的)不是“過(guò)時(shí)”的內(nèi)容
第六章CacheCoherence
6.1CacheCoherence問(wèn)題
6.2監(jiān)聽(tīng)總線(xiàn)協(xié)議
6.3基于目錄的Cache一致性協(xié)議
6.3.1目錄的一般性問(wèn)題
6.3.2全映射目錄
6.3.3有限目錄
6.3.4鏈?zhǔn)侥夸?/p>
6.4三種Cache一致性策略
6.2基于目錄的Cache一致性協(xié)議
6.2.1目錄的一般性問(wèn)題
1.Cache一致性協(xié)議的開(kāi)銷(xiāo)分析
(1)采用寫(xiě)無(wú)效協(xié)議
無(wú)效后,當(dāng)其它處理機(jī)再讀該副本時(shí),
出現(xiàn)Readmiss)要有開(kāi)銷(xiāo)
(2)采用寫(xiě)更新協(xié)議■
需要更新所有Cache和memory中的副
本,所以開(kāi)銷(xiāo)大,有些處理機(jī)對(duì)更新后的
數(shù)據(jù)可能不會(huì)使用。
2.基于目錄的一致性協(xié)議的基本思想
當(dāng)處理機(jī)臺(tái)數(shù)增加時(shí),一般不用總線(xiàn)結(jié)構(gòu),
而采用多級(jí)互連網(wǎng)絡(luò)。多級(jí)互連網(wǎng)絡(luò)實(shí)現(xiàn)廣
播功能代價(jià)很大。
為什么需要廣播功能?把一致性命令,如
Write-inv,Read-inv等命令要發(fā)送給所有的
Cache。
能不能只發(fā)送給存放該副本的Cache?M
——基于目錄的協(xié)議的基本思想
3.目錄的結(jié)構(gòu)
(1)目錄里放什么——有關(guān)Cache副本駐
留在哪里的信息:所有共享數(shù)據(jù)塊的所有
Cache副本的地址表。
(2)每個(gè)目錄項(xiàng)(每個(gè)數(shù)據(jù)結(jié)構(gòu))包含
若干個(gè)指向這個(gè)塊(每個(gè)數(shù)據(jù)塊有個(gè)目錄項(xiàng))
的Cache副本地址的指針以及一個(gè)重寫(xiě)位
(用來(lái)說(shuō)明是否有一個(gè)Cache允許把有關(guān)的
數(shù)據(jù)寫(xiě)入)。
(3)基于目錄的Cache一致性協(xié)議是依靠
一個(gè)目錄來(lái)記錄系統(tǒng)之中哪些處理機(jī)的
Cache中有指定存儲(chǔ)塊的副本。當(dāng)一臺(tái)處理
機(jī)希望寫(xiě)某個(gè)共享塊時(shí),通過(guò)目錄向有該塊
的副本的那些處理機(jī)“點(diǎn)對(duì)點(diǎn)”的發(fā)無(wú)效信
號(hào),使所有其它的副本無(wú)效。
4.目錄的方式
(1)集中目錄方式(中心目錄)
1976年Tang提出。
用一個(gè)中心目錄存放所有Cache目錄的
副本,它能提供為保證一致性所需要的所有
信息。
容量非常大,必須采用聯(lián)想方法來(lái)檢
查,沖突多,檢索時(shí)間長(zhǎng)。
(2)分布式目錄
1978年Censier和Feautrier提出?!?/p>
每個(gè)存儲(chǔ)模塊維護(hù)各自的目錄,目錄
中記錄著每個(gè)存儲(chǔ)塊的當(dāng)前信息。當(dāng)前信息
指明哪些Cache有該存儲(chǔ)塊的副本。
如下面的圖:
如果C2讀miss)這時(shí)C:中有Dirty的副本)
則把它寫(xiě)回memory,內(nèi)存再給C2一個(gè)副本)
變成Valid。
如果Cl寫(xiě)命中)它告訴memory控制器,
控制器發(fā)無(wú)效命令給在D1的當(dāng)前向量中有記
錄的所有Cache。
5.三種目錄
全映射(fullmap)目錄:存放與全局存儲(chǔ)
器中每個(gè)塊有關(guān)的數(shù)據(jù)。系統(tǒng)中的每個(gè)
Cache可以同時(shí)存儲(chǔ)任何數(shù)據(jù)塊的副本,即
每個(gè)目錄項(xiàng)包含N個(gè)指針(N是處理機(jī)數(shù)
目)。.
有限(limited)目錄:每個(gè)目錄項(xiàng)有固定
數(shù)目的指針(小于N)o
鏈?zhǔn)剑╟hained)目錄:將目錄分布到各個(gè)
Cache(其余同全映射目錄)。
622全映射目錄
1.目錄項(xiàng)結(jié)構(gòu)
目錄項(xiàng)中有N個(gè)處理機(jī)位(對(duì)應(yīng)N臺(tái)處理
機(jī))和一個(gè)重寫(xiě)位,如下圖所示:
重寫(xiě)位(1位)處理機(jī)位(N位)
1///
,///:
目錄項(xiàng):
處理機(jī)位表示相應(yīng)處理機(jī)的Cacheblock的
狀態(tài)(存在或不存在)。
有一個(gè)也只有一個(gè)處理機(jī)位為“1。那么
該處理機(jī)可以對(duì)該塊進(jìn)行寫(xiě)操作。
Cache的每個(gè)塊有兩個(gè)狀態(tài)位:
有效位
有效塊是否允許寫(xiě)
1位1位
Cache的狀態(tài)位應(yīng)該和目錄項(xiàng)的狀態(tài)一致。
2.目錄的三種情況
我們來(lái)看三臺(tái)處理機(jī)(三個(gè)Cache)的例
子。
(1)CLC2,C3都沒(méi)有單元X的副本
(2)Cl,C2,C3同時(shí)請(qǐng)求X單元的副本,
這時(shí)目錄項(xiàng)中的三個(gè)指針(處理機(jī)位)被
置一,表示這些Cache中已有數(shù)據(jù)副本。
目錄項(xiàng)的重寫(xiě)位被置為未寫(xiě)(c)狀態(tài),
表示無(wú)一處理機(jī)允許寫(xiě)入該數(shù)據(jù)塊。
C1
(3)C3請(qǐng)求對(duì)該塊的寫(xiě)允許權(quán)時(shí)出現(xiàn)第(3)
種情形,重寫(xiě)被置成D狀態(tài),且有一個(gè)指針
指向C3的數(shù)據(jù)塊。
SharedMemory
x:IDI0I0I1data
ClC2C3x:data
PlP2P3
3.第二種情況一第三種情況的過(guò)程
P3向C3發(fā)出寫(xiě)請(qǐng)求時(shí):
(1)C3檢測(cè)出包含單元X的塊是有效的,但
Cache中的塊允許位狀態(tài)表示不允許處理機(jī)
對(duì)該塊進(jìn)行寫(xiě)操作。
(2)C3向包含單元X的存儲(chǔ)器模塊發(fā)出寫(xiě)請(qǐng)
求,并暫停P3工作。
(3)該存儲(chǔ)器模塊發(fā)出一個(gè)無(wú)效請(qǐng)求給C1和
C2(根據(jù)目錄項(xiàng)的內(nèi)容發(fā)幾個(gè)無(wú)效信號(hào))
(4)Cl和C2收到無(wú)效請(qǐng)求后,把相應(yīng)位置1,
表示含單元X的塊已無(wú)效,并發(fā)送一個(gè)回答
信號(hào)給請(qǐng)求的存儲(chǔ)器模塊。
(5)存儲(chǔ)器模塊收到回答信號(hào)后,將重寫(xiě)位
置1,清除指向Cl、C2的指針,發(fā)出允許信
號(hào)給C3。
(6)C3收到寫(xiě)允許信號(hào)后夕修改Cache的狀
態(tài)并激活處理機(jī)P3。
4.目錄所占空間
假設(shè)存儲(chǔ)器大小和處理機(jī)臺(tái)數(shù)N成正比,
即臺(tái)數(shù)增加時(shí))存儲(chǔ)器的模塊數(shù)也增加)所
以數(shù)據(jù)塊的個(gè)數(shù)也和N成正比。
另外目錄項(xiàng)的大小也和處理機(jī)臺(tái)數(shù)N成正
比)所以目錄的總所占空間和N2成正比。
■
目錄項(xiàng)數(shù)*項(xiàng)大小=0(N2)
太大不便于擴(kuò)展。
623有限目錄
解決目錄過(guò)大的問(wèn)題。
任意一個(gè)數(shù)據(jù)塊在Cache中同時(shí)存在的副本
數(shù)量有一定限制,那么目錄大小的增加不會(huì)
超過(guò)一個(gè)常數(shù)。
符號(hào)表示法:
DirjX
i:指針的數(shù)量。I
X是NB,表示沒(méi)有廣播功能的方案。
Di^NB表示沒(méi)有廣播功能的全映射方式
Di^NB(i<N):使用i個(gè)指針的沒(méi)有廣播
功能的有限目錄協(xié)議方式。
除了多于i個(gè)Cache請(qǐng)求讀一個(gè)特定的數(shù)據(jù)
塊的情況外,有限目錄協(xié)議與全映射協(xié)議類(lèi)
似。
有限目錄中指針不是每臺(tái)處理機(jī)一位,而
是針對(duì)處理機(jī)的二進(jìn)制標(biāo)識(shí)符進(jìn)行編碼,所
以指針占logzN位存儲(chǔ)器。
在全映射方式中,每個(gè)處理機(jī)對(duì)應(yīng)一個(gè)指
針,所以N臺(tái)處理機(jī)一共用了N位,而有限
目錄中只用logzN位)設(shè)N=16夕則log216=4。
如果允許兩個(gè)指針,則需要8位。
所以目錄的存儲(chǔ)容量為0(NlogzN),比
全映射容易擴(kuò)充。
如果多處理機(jī)系統(tǒng)中的處理機(jī)具有局部性,
即在任何給定的時(shí)間間隔內(nèi),只有一小部分
處理機(jī)訪(fǎng)問(wèn)某個(gè)給定的存儲(chǔ)器字,那么有限
目錄足以應(yīng)付這個(gè)小的工作處理機(jī)組了。
6.2.4鏈?zhǔn)侥夸?/p>
用目錄指針鏈來(lái)跟蹤共享數(shù)據(jù)副本。
兩種方法,單鏈法與雙鏈法。
數(shù)據(jù)塊共享副本的數(shù)目并無(wú)限制。
所占的空間及可擴(kuò)展性同有限目錄。
它的工作原理如下過(guò)程所示。
(1)P〔要讀單元二貝Umemory發(fā)送一份副本
給Cl,同時(shí)送給C1一個(gè)鏈結(jié)束指針(CT:
ChainTermination),存儲(chǔ)器也保存指向C1
的指針。
SharedMemory
(2)當(dāng)P2要讀單元X時(shí),存儲(chǔ)器送一份副本
給C2,同時(shí)送給C2一個(gè)指向C1的指針,存
儲(chǔ)器保存指向C2的指針。
C1
(3)重復(fù)以上步驟,所有Cache都得到單元X
的副本。
(4)如果P3要對(duì)單元X進(jìn)行寫(xiě)操作,它必須
沿著鏈發(fā)送一個(gè)數(shù)據(jù)無(wú)效信息。為了保證順
序一致性,在有鏈結(jié)束指針的處理機(jī)回答無(wú)
效信號(hào)之前,存儲(chǔ)器模塊不給P3寫(xiě)允許權(quán)。
無(wú)效命令從一個(gè)Cache到一個(gè)Cache順序
進(jìn)行)不象snoopy協(xié)議那樣同時(shí)發(fā)送給所有
Cacheo
(5)替換。假設(shè)C]到CN都有單元X的副本,
還假設(shè)單元X和單元Y都映射到同一個(gè)高速
緩存塊(直接映射法)。如果處理機(jī)R要讀
單元Y,它首先必須把X所在的塊從Cache中
去掉,這可以采用兩種方法:
1)沿著鏈發(fā)一個(gè)消息使Ci+]的指針指向
q.p這樣使G從鏈中去掉(這時(shí)G中存放丫
了)。
2)使Cj+i到CN中的單元X無(wú)效(這時(shí)C1中
存放Y了)。
目錄占用的存儲(chǔ)容量:
指針的尺寸以處理機(jī)數(shù)目的對(duì)數(shù)關(guān)系增長(zhǎng)
(這和有限目錄相同)log2N,每個(gè)Cache塊
的指針數(shù)目與處理機(jī)個(gè)數(shù)無(wú)關(guān)。
解決Cache一致性的其它辦法:
(1)不允許有私有Cache:SharedCache
方案
(2)可寫(xiě)的共享數(shù)據(jù)不存放在Cache中
第六章CacheCoherence
6.1CacheCoherence問(wèn)題
6.2監(jiān)聽(tīng)總線(xiàn)協(xié)議
6.3基于目錄的Cache一致性協(xié)議
6.4三種Cache一致性策略
6.4.1采用Write-Through策略的Cache
6.4.2采用Write-用ch策略的Cache
6.4.3采用Write-Once策略的Cache
6.4三種Cache一致性策略
6.4.1采用Write-Through策略的Cache
數(shù)據(jù)塊的兩種狀態(tài):
有效和無(wú)效(指本地處理機(jī)相應(yīng)數(shù)據(jù)塊
的狀態(tài),并非整個(gè)Cache的狀態(tài)。)
一致性的四種操作:B
Rr和Wr:其它處理機(jī)對(duì)該數(shù)據(jù)塊(指在其
它處理機(jī)Cache中的數(shù)據(jù)塊)的讀寫(xiě)
R1和W1:是本地處理機(jī)對(duì)該數(shù)據(jù)塊的讀寫(xiě)
狀態(tài)轉(zhuǎn)移圖如下:
Cache的數(shù)據(jù)塊為無(wú)效時(shí):
其它處理機(jī)的任何操作都不會(huì)影響本地
Cache的這種無(wú)效狀態(tài);
只有在本地處理機(jī)讀或者寫(xiě)了數(shù)據(jù)塊中的
某個(gè)數(shù)據(jù),即對(duì)Cache執(zhí)行了Read或Write命令
時(shí),該數(shù)據(jù)塊的狀態(tài)才會(huì)成為“有效”。
Cache的數(shù)據(jù)塊為“有效”時(shí):
本地處理機(jī)的讀、寫(xiě)操作)不會(huì)影響該狀
態(tài);
其它處理機(jī)對(duì)存有相同內(nèi)容的數(shù)據(jù)塊讀,
不會(huì)影響該狀態(tài);
其它處理機(jī)對(duì)存有相同內(nèi)容的數(shù)據(jù)塊執(zhí)行
了寫(xiě)操作,該數(shù)據(jù)塊狀態(tài)變成無(wú)效。
6.4.2采用Write-Back策略的Cache
1.數(shù)據(jù)塊的三種狀態(tài)
R0(只讀)狀態(tài):表示整個(gè)系統(tǒng)中不止一
個(gè)副本正確(例如一個(gè)在Cache中,一個(gè)在
memory中)。
讀-寫(xiě)狀態(tài):表示整個(gè)系統(tǒng)中,只有這個(gè)
副本是正確的,其它都“過(guò)時(shí)”(即無(wú)效),
這說(shuō)明這個(gè)Cache的數(shù)據(jù)塊至少被寫(xiě)過(guò)一次,
但memory中的內(nèi)容還沒(méi)有被修改。
無(wú)效狀態(tài):“過(guò)時(shí)”數(shù)據(jù)。
2.一致性的四種操作:
Rr和Wr:其它處理機(jī)對(duì)該數(shù)據(jù)塊(指在其
它處理機(jī)Cache中的數(shù)據(jù)塊)的讀寫(xiě)
R1和W1:是本地處理機(jī)對(duì)該數(shù)據(jù)塊的讀寫(xiě)
狀態(tài)轉(zhuǎn)移圖如下:
4.處于讀-寫(xiě)狀態(tài)
本地讀、寫(xiě)不會(huì)改變狀態(tài)
遠(yuǎn)程讀:這時(shí)只有這個(gè)Cache的數(shù)據(jù)塊是
正確的,所以要有“寫(xiě)回”動(dòng)作(即把內(nèi)容
寫(xiě)回Memory),另外還需要把正確的數(shù)據(jù)
傳遞給遠(yuǎn)程讀的處理機(jī)相應(yīng)的Cache。
兩個(gè)Cache的狀態(tài)-RO
遠(yuǎn)程寫(xiě):把本地處理機(jī)的數(shù)據(jù)塊傳遞給遠(yuǎn)
程處理機(jī),遠(yuǎn)程處理機(jī)對(duì)數(shù)據(jù)塊進(jìn)行寫(xiě)操作,
遠(yuǎn)程處理機(jī)對(duì)應(yīng)的Cache狀態(tài)變?yōu)镽O,而本
地的Cache變?yōu)闊o(wú)效狀態(tài)。
5.處于無(wú)效狀態(tài)
本地讀:無(wú)效fRO
本地寫(xiě):無(wú)效fWR(同時(shí)使其它擁有相
同內(nèi)容的數(shù)據(jù)塊的Cache中相應(yīng)的數(shù)據(jù)塊的
狀態(tài)變成無(wú)效)
遠(yuǎn)程寫(xiě)、遠(yuǎn)程讀:不影響狀態(tài)的改變
6.4.3采用Write-Once策略的Cache
1.Write-Through和Write-Back的缺點(diǎn)
Write-Through策略的弱點(diǎn)是每次都要修改
memory,所以總線(xiàn)流量增大;
Write-Back策略的弱點(diǎn)是Cache寫(xiě)了一次后,
Memory中的內(nèi)容不一致。
2.Write-Once的基本思想
把Write-Throug
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 專(zhuān)業(yè)咨詢(xún)協(xié)作協(xié)議樣本(2024版)版B版
- 2025年度產(chǎn)業(yè)園入駐企業(yè)市場(chǎng)推廣合作協(xié)議4篇
- 2024年04月遼寧中國(guó)建設(shè)銀行大連分行春季校園招考筆試筆試歷年參考題庫(kù)附帶答案詳解
- 2024鐵路建設(shè)環(huán)境保護(hù)及恢復(fù)合同3篇
- 2025年度市場(chǎng)潛力評(píng)估調(diào)研合同3篇
- 2024跨界融合創(chuàng)新科技研發(fā)合作合同
- 2025年度養(yǎng)老公寓租賃服務(wù)合同標(biāo)準(zhǔn)4篇
- 2025年度柴油居間服務(wù)合作協(xié)議4篇
- 二零二四學(xué)校與教師聘用合同(傳統(tǒng)文化教育)3篇
- 2024年03月北京2024年中國(guó)農(nóng)業(yè)發(fā)展銀行委托研究課題征集筆試歷年參考題庫(kù)附帶答案詳解
- 高二物理競(jìng)賽霍爾效應(yīng) 課件
- 金融數(shù)學(xué)-(南京大學(xué))
- 基于核心素養(yǎng)下的英語(yǔ)寫(xiě)作能力的培養(yǎng)策略
- 現(xiàn)場(chǎng)安全文明施工考核評(píng)分表
- 亞什蘭版膠衣操作指南
- 四年級(jí)上冊(cè)數(shù)學(xué)教案 6.1口算除法 人教版
- DB32-T 3129-2016適合機(jī)械化作業(yè)的單體鋼架塑料大棚 技術(shù)規(guī)范-(高清現(xiàn)行)
- 6.農(nóng)業(yè)產(chǎn)值與增加值核算統(tǒng)計(jì)報(bào)表制度(2020年)
- 人工挖孔樁施工監(jiān)測(cè)監(jiān)控措施
- 供應(yīng)商物料質(zhì)量問(wèn)題賠償協(xié)議(終端)
- 物理人教版(2019)必修第二冊(cè)5.2運(yùn)動(dòng)的合成與分解(共19張ppt)
評(píng)論
0/150
提交評(píng)論