高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)(一)_第1頁(yè)
高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)(一)_第2頁(yè)
高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)(一)_第3頁(yè)
高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)(一)_第4頁(yè)
高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)(一)_第5頁(yè)
已閱讀5頁(yè),還剩103頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(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ì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論