高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)(一)

計(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問題

6.1.1CacheCoherence的提出

6.1.2多個(gè)Cache不一致的原因

6.1.3兩種設(shè)計(jì)Cache一致性協(xié)議策略

6.2監(jiān)聽總線協(xié)議

6.3基于目錄的Cache一致性協(xié)議

6.4三種Cache一致性策略

6.1CacheCoherence問題

6.1.1CacheCoherence問題的提出

在多處理器系統(tǒng)中，多個(gè)Cache中，對(duì)應(yīng)

的copy內(nèi)容應(yīng)該一致,如下圖：

6.1.2多個(gè)Cache不一致的原因

1.共享可寫數(shù)據(jù)的不一致性(sharingof

writabledata)

處理機(jī)

Cache

shared

memory

更新前寫通過寫回

2.進(jìn)程遷移的不一致性

處理機(jī)

Cache

遷移前寫通過寫回

上圖中：

右圖為：包含共享變量X的進(jìn)程原來在P1

上運(yùn)行，并對(duì)X進(jìn)行了修改（但采取寫回策

略）所以暫時(shí)沒有修改Memory）,由于某

種原因遷移到P2,修改過的X，仍在P1的

Cache中,P2運(yùn)行時(shí)從Memory中得到x,這

個(gè)x其實(shí)是“過時(shí)”的，所以造成了不一致。

中間圖為：P2中運(yùn)行的進(jìn)程對(duì)x進(jìn)行了修

改）采取寫通過策略,所以把Memory中的x

也修改為x-由于某種原因該進(jìn)程遷移到PL

但P1的Cache中仍為x,所以造成不一致。

3.I/O操作（繞過Cache的I/O操作）

存儲(chǔ)器I/O

寫通過寫回

上圖中：

中間圖為：當(dāng)I/O處理機(jī)將一個(gè)新的數(shù)據(jù)父

寫入主存儲(chǔ)器時(shí)，繞過采用寫通過策略的

cache,則Cl和共享存儲(chǔ)器之間產(chǎn)生了不一

致。

右圖為：直接從主存儲(chǔ)器輸出數(shù)據(jù)時(shí)（繞

過Cache）,采用寫回策略的高速緩存產(chǎn)生

不'一致性。

6.1.3兩種設(shè)計(jì)Cache一致性協(xié)議策略

1.寫無(wú)效（writeinvalidate）

任一處理器寫它的私有Cache時(shí)，它都使所

有其它的Cache中的副本失效。

對(duì)Write-through）它也更新memory中的副

本（最終是一個(gè)Cache中的副本和memory中的

副本是有效的）。

對(duì)Write-back,它使memory中的副本也失

效（最終只有一個(gè)Cache中的副本是有效的）。

2.寫更新(writeupdate)

任一處理器寫它的私有Cache時(shí)，它都立即

更新所有其它的Cache中的副本。

對(duì)Write-through5它也更新主存儲(chǔ)器中的副

本。

對(duì)Write-back,對(duì)存儲(chǔ)器中副本的更新延遲

到這個(gè)Cache被置換的時(shí)刻。

寫回:

4,寫無(wú)效的問題

主要開銷在兩個(gè)方面：

(1)作廢各Cache副本的開銷；

(2)由作廢引起缺失造成的開銷，即處理

機(jī)需要訪問已經(jīng)作廢的數(shù)據(jù)時(shí)將引起Cache的

缺失。

后果：

如果一個(gè)處理機(jī)經(jīng)常對(duì)某個(gè)塊連續(xù)寫，且各

處理處理機(jī)間對(duì)共享塊的競(jìng)爭(zhēng)較小，這時(shí)寫無(wú)

效策略維護(hù)一致性的開銷是很小的。如發(fā)生嚴(yán)

重競(jìng)爭(zhēng)，即處理機(jī)之間對(duì)某個(gè)地址的共享數(shù)據(jù)

競(jìng)爭(zhēng)，將產(chǎn)生較多的作廢，引起更多的作廢缺

失。結(jié)果是共享數(shù)據(jù)在各Cache間倒來倒去，

產(chǎn)生顛簸現(xiàn)象，當(dāng)緩存塊比較大時(shí)，這種顛簸

現(xiàn)象更為嚴(yán)重。

5.寫更新的問題

由于更新時(shí)）所有的副本均需要更新）開

銷很大。

第六章CacheCoherence

6.1CacheCoherence問題

6.2監(jiān)聽總線協(xié)議

6.2.1寫一次協(xié)議

6.3基于目錄的Cache一致性協(xié)議

6.4三種Cache一致性策略

6.2監(jiān)聽總線協(xié)議(Snoopyprotocol)

通過總線監(jiān)聽機(jī)制實(shí)現(xiàn)Cache和共享存儲(chǔ)

器之間的一致性。

適用性分析：m■

適用于具有廣播能力的總線結(jié)構(gòu)多機(jī)系統(tǒng),

允許每臺(tái)處理機(jī)監(jiān)聽其它處理機(jī)的存儲(chǔ)器訪

問情況。

只適用于小規(guī)模的多處理機(jī)系統(tǒng)。

6.2.1寫一次(write-once)協(xié)議

寫無(wú)效監(jiān)聽一致性協(xié)議，將寫通過和寫回

策略結(jié)合。

為了減少總線流量，高速緩存塊的第一次

寫用寫通過方法，產(chǎn)生一份正確的主存儲(chǔ)器

副本，并使其它的Cache中的副本無(wú)效)之

后就采用寫回方法更新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副

本是第一次修改，并用寫通過方法寫入主存,

所以這一Cache副本和主存儲(chǔ)器副本一致。

(3)重寫(dirtystate):Cache副本不止

一次被修改過，由于不再采用寫通過方法，

所以這個(gè)Cache副本是唯一的副本。與存儲(chǔ)

器和其它的Cache副本都不一致。主存儲(chǔ)器

中的副本也是無(wú)效的。

(4)無(wú)效(invalidstate)與存儲(chǔ)器或其它

的Cache副本不一致)或在Cache中找不到。

3.局部命令(Localcommands)

(1)P-Read:本地處理機(jī)讀自己的Cache

副本。

(2)P-Write:本地處理機(jī)寫自己的Cache

副本。

4.一致性命令

(1)Read-blk:從另一Cache讀一份有效

的副本。

(2)Write-inv:在寫命中時(shí)在總線上廣

播一個(gè)無(wú)效命令。

(3)Read-inv:在寫缺失時(shí)在總線上廣播

一個(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)擊連線來察看詳細(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)

第一'次寫命中，用

P-Write有效保留Write-hit

寫通過法。同時(shí)修

改本地和主存副本

并廣播Write-inv

使月副本失效

第二次寫命中，用

P-Write保留重寫Write-hit

寫回法。但不修改

主存的副本

（續(xù)表）

currentnext

commandstatestatestatusaction

第二次以后更多的

P-Write重寫重寫Write-hit

寫命中，用寫回法。

無(wú)狀態(tài)改變。

,寫缺失時(shí)，則從主存

P-Write無(wú)效保留,Write-mist；或遠(yuǎn)程Cache送來副本

o并廣播Read-inv

使所有其它副本無(wú)效。

（續(xù)表）

currentnext

commandstatestatestatusaction

讀缺失時(shí),如遠(yuǎn)程Cache

P-Read無(wú)效有效Read-miss

中沒有重寫副本，則主

存中一定有一份正確的

副本，供給發(fā)請(qǐng)求的

Cacheo如遠(yuǎn)程的Cache

有重寫的副本，則它禁

止主存操作，并將副本

發(fā)給請(qǐng)求的Cache,兩種

情況均使發(fā)請(qǐng)求的Cache

得到的副本為有效。

（續(xù)表）

currentnext

commandstatestatestatusaction

保留或遠(yuǎn)程Cache讀此副本，

Read-blk有效

重寫讀后兩份副本均有效

寫缺失時(shí)，遠(yuǎn)程Cache

除無(wú)效

讀一個(gè)塊，并修改它，

Read-inv外的其無(wú)效

并使所有其它Cache的

它狀態(tài)

副本無(wú)效。

（續(xù)表）

currentnext

commandstatestatestatusaction

寫命中時(shí)，一遠(yuǎn)程Cache

Write-inv有效無(wú)效修改其本地副本，并使

數(shù)據(jù)塊的其它副本無(wú)效

如果副本處于重寫狀態(tài)，

Write-inv有效無(wú)效替代必須通過塊替換寫回主

存，否則不產(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沒有東西,

則讀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。

寫的情況:

(1)如果Cl為Valid,寫Cl,則Writehit,I

發(fā)P-write修改C1內(nèi)容)修改memory)發(fā)

Write-inv⑷給所有Cache5C1變成Reserved狀

態(tài)。

(2)如果C1為Reserved,寫CL貝UWritehit,

發(fā)P-write修改C1內(nèi)容,不修改memory,C1狀

態(tài)變?yōu)镈irty。

(3)如果Cl為Dirty,寫Cl,則Writehit,

發(fā)P-write修改Cl內(nèi)容,不修改memory,狀態(tài)

仍為Dirty。

(4)如果Cl為Invalid,C2,C3沒有東西，

這時(shí)memory中有這個(gè)地址的數(shù)據(jù)副本,從

memory中讀取該副本到C1,再把要寫的內(nèi)容

寫入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再把要寫的內(nèi)容寫入CL

ClfDirty)發(fā)Read-inv使其它所有Cache的副

本變成無(wú)效狀態(tài)。

(6)如果C1為Invalid,C2為Reserved,這

時(shí)memory中的內(nèi)容和C2內(nèi)容一致,把

C2fCL再把要寫的內(nèi)容寫入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.其它的一些問題

CPU要向Cache寫數(shù)據(jù),如果writemiss,表

示該數(shù)據(jù)塊不在Cache中或者該數(shù)據(jù)快處于無(wú)

效狀態(tài),那么需要把正確的數(shù)據(jù)從memory或

其它的Cache中取過來，然后再寫操作。

為什么不能直接寫？

(1)可能該數(shù)據(jù)塊根本不在Cache中，所

以需要從其它地方調(diào)入。

(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ò)

的。

CacheCoherence問題彳既要：

多處理機(jī)系統(tǒng)

共享存儲(chǔ)器

Cache塊的狀態(tài)

訪問的數(shù)據(jù)是最新的）不是“過時(shí)”的內(nèi)容

第六章CacheCoherence

6.1CacheCoherence問題

6.2監(jiān)聽總線協(xié)議

6.3基于目錄的Cache一致性協(xié)議

6.3.1目錄的一般性問題

6.3.2全映射目錄

6.3.3有限目錄

6.3.4鏈?zhǔn)侥夸?/p>

6.4三種Cache一致性策略

6.2基于目錄的Cache一致性協(xié)議

6.2.1目錄的一般性問題

1.Cache一致性協(xié)議的開銷分析

(1)采用寫無(wú)效協(xié)議

無(wú)效后，當(dāng)其它處理機(jī)再讀該副本時(shí),

出現(xiàn)Readmiss)要有開銷

(2)采用寫更新協(xié)議■

需要更新所有Cache和memory中的副

本，所以開銷大，有些處理機(jī)對(duì)更新后的

數(shù)據(jù)可能不會(huì)使用。

2.基于目錄的一致性協(xié)議的基本思想

當(dāng)處理機(jī)臺(tái)數(shù)增加時(shí)，一般不用總線結(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è)重寫位

（用來說明是否有一個(gè)Cache允許把有關(guān)的

數(shù)據(jù)寫入）。

(3)基于目錄的Cache一致性協(xié)議是依靠

一個(gè)目錄來記錄系統(tǒng)之中哪些處理機(jī)的

Cache中有指定存儲(chǔ)塊的副本。當(dāng)一臺(tái)處理

機(jī)希望寫某個(gè)共享塊時(shí)，通過目錄向有該塊

的副本的那些處理機(jī)“點(diǎn)對(duì)點(diǎn)”的發(fā)無(wú)效信

號(hào)，使所有其它的副本無(wú)效。

4.目錄的方式

（1）集中目錄方式（中心目錄）

1976年Tang提出。

用一個(gè)中心目錄存放所有Cache目錄的

副本，它能提供為保證一致性所需要的所有

信息。

容量非常大，必須采用聯(lián)想方法來檢

查，沖突多，檢索時(shí)間長(zhǎng)。

(2)分布式目錄

1978年Censier和Feautrier提出?！?/p>

每個(gè)存儲(chǔ)模塊維護(hù)各自的目錄，目錄

中記錄著每個(gè)存儲(chǔ)塊的當(dāng)前信息。當(dāng)前信息

指明哪些Cache有該存儲(chǔ)塊的副本。

如下面的圖：

如果C2讀miss）這時(shí)C：中有Dirty的副本）

則把它寫回memory,內(nèi)存再給C2一個(gè)副本）

變成Valid。

如果Cl寫命中）它告訴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è)重寫位，如下圖所示：

重寫位（1位）處理機(jī)位（N位）

1///

，///:

目錄項(xiàng):

處理機(jī)位表示相應(yīng)處理機(jī)的Cacheblock的

狀態(tài)（存在或不存在）。

有一個(gè)也只有一個(gè)處理機(jī)位為“1。那么

該處理機(jī)可以對(duì)該塊進(jìn)行寫操作。

Cache的每個(gè)塊有兩個(gè)狀態(tài)位:

有效位

有效塊是否允許寫

1位1位

Cache的狀態(tài)位應(yīng)該和目錄項(xiàng)的狀態(tài)一致。

2.目錄的三種情況

我們來看三臺(tái)處理機(jī)(三個(gè)Cache)的例

子。

(1)CLC2,C3都沒有單元X的副本

（2）Cl,C2,C3同時(shí)請(qǐng)求X單元的副本，

這時(shí)目錄項(xiàng)中的三個(gè)指針（處理機(jī)位）被

置一，表示這些Cache中已有數(shù)據(jù)副本。

目錄項(xiàng)的重寫位被置為未寫（c）狀態(tài)，

表示無(wú)一處理機(jī)允許寫入該數(shù)據(jù)塊。

C1

(3)C3請(qǐng)求對(duì)該塊的寫允許權(quán)時(shí)出現(xiàn)第(3)

種情形，重寫被置成D狀態(tài)，且有一個(gè)指針

指向C3的數(shù)據(jù)塊。

SharedMemory

x:IDI0I0I1data

ClC2C3x:data

PlP2P3

3.第二種情況一第三種情況的過程

P3向C3發(fā)出寫請(qǐng)求時(shí)：

(1)C3檢測(cè)出包含單元X的塊是有效的，但

Cache中的塊允許位狀態(tài)表示不允許處理機(jī)

對(duì)該塊進(jìn)行寫操作。

(2)C3向包含單元X的存儲(chǔ)器模塊發(fā)出寫請(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)后，將重寫位

置1,清除指向Cl、C2的指針，發(fā)出允許信

號(hào)給C3。

(6)C3收到寫允許信號(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有限目錄

解決目錄過大的問題。

任意一個(gè)數(shù)據(jù)塊在Cache中同時(shí)存在的副本

數(shù)量有一定限制，那么目錄大小的增加不會(huì)

超過一個(gè)常數(shù)。

符號(hào)表示法：

DirjX

i:指針的數(shù)量。I

X是NB,表示沒有廣播功能的方案。

Di^NB表示沒有廣播功能的全映射方式

Di^NB(i<N):使用i個(gè)指針的沒有廣播

功能的有限目錄協(xié)議方式。

除了多于i個(gè)Cache請(qǐng)求讀一個(gè)特定的數(shù)據(jù)

塊的情況外，有限目錄協(xié)議與全映射協(xié)議類

似。

有限目錄中指針不是每臺(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ī)訪問某個(gè)給定的存儲(chǔ)器字，那么有限

目錄足以應(yīng)付這個(gè)小的工作處理機(jī)組了。

6.2.4鏈?zhǔn)侥夸?/p>

用目錄指針鏈來跟蹤共享數(shù)據(jù)副本。

兩種方法，單鏈法與雙鏈法。

數(shù)據(jù)塊共享副本的數(shù)目并無(wú)限制。

所占的空間及可擴(kuò)展性同有限目錄。

它的工作原理如下過程所示。

(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)行寫操作,它必須

沿著鏈發(fā)送一個(gè)數(shù)據(jù)無(wú)效信息。為了保證順

序一致性，在有鏈結(jié)束指針的處理機(jī)回答無(wú)

效信號(hào)之前，存儲(chǔ)器模塊不給P3寫允許權(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)可寫的共享數(shù)據(jù)不存放在Cache中

第六章CacheCoherence

6.1CacheCoherence問題

6.2監(jiā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ù)塊）的讀寫

R1和W1:是本地處理機(jī)對(duì)該數(shù)據(jù)塊的讀寫

狀態(tài)轉(zhuǎn)移圖如下：

Cache的數(shù)據(jù)塊為無(wú)效時(shí)：

其它處理機(jī)的任何操作都不會(huì)影響本地

Cache的這種無(wú)效狀態(tài)；

只有在本地處理機(jī)讀或者寫了數(shù)據(jù)塊中的

某個(gè)數(shù)據(jù),即對(duì)Cache執(zhí)行了Read或Write命令

時(shí)，該數(shù)據(jù)塊的狀態(tài)才會(huì)成為“有效”。

Cache的數(shù)據(jù)塊為“有效”時(shí)：

本地處理機(jī)的讀、寫操作）不會(huì)影響該狀

態(tài)；

其它處理機(jī)對(duì)存有相同內(nèi)容的數(shù)據(jù)塊讀，

不會(huì)影響該狀態(tài)；

其它處理機(jī)對(duì)存有相同內(nèi)容的數(shù)據(jù)塊執(zhí)行

了寫操作，該數(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中）。

讀-寫狀態(tài)：表示整個(gè)系統(tǒng)中，只有這個(gè)

副本是正確的，其它都“過時(shí)”（即無(wú)效），

這說明這個(gè)Cache的數(shù)據(jù)塊至少被寫過一次,

但memory中的內(nèi)容還沒有被修改。

無(wú)效狀態(tài)：“過時(shí)”數(shù)據(jù)。

2.一致性的四種操作：

Rr和Wr:其它處理機(jī)對(duì)該數(shù)據(jù)塊（指在其

它處理機(jī)Cache中的數(shù)據(jù)塊）的讀寫

R1和W1:是本地處理機(jī)對(duì)該數(shù)據(jù)塊的讀寫

狀態(tài)轉(zhuǎn)移圖如下：

4.處于讀-寫狀態(tài)

本地讀、寫不會(huì)改變狀態(tài)

遠(yuǎn)程讀：這時(shí)只有這個(gè)Cache的數(shù)據(jù)塊是

正確的，所以要有“寫回”動(dòng)作（即把內(nèi)容

寫回Memory）,另外還需要把正確的數(shù)據(jù)

傳遞給遠(yuǎn)程讀的處理機(jī)相應(yīng)的Cache。

兩個(gè)Cache的狀態(tài)-RO

遠(yuǎn)程寫：把本地處理機(jī)的數(shù)據(jù)塊傳遞給遠(yuǎn)

程處理機(jī)，遠(yuǎn)程處理機(jī)對(duì)數(shù)據(jù)塊進(jìn)行寫操作,

遠(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

本地寫：無(wú)效fWR（同時(shí)使其它擁有相

同內(nèi)容的數(shù)據(jù)塊的Cache中相應(yīng)的數(shù)據(jù)塊的

狀態(tài)變成無(wú)效）

遠(yuǎn)程寫、遠(yuǎn)程讀：不影響狀態(tài)的改變

6.4.3采用Write-Once策略的Cache

1.Write-Through和Write-Back的缺點(diǎn)

Write-Through策略的弱點(diǎn)是每次都要修改

memory,所以總線流量增大；

Write-Back策略的弱點(diǎn)是Cache寫了一次后,

Memory中的內(nèi)容不一致。

2.Write-Once的基本思想

把Write-Throug