計算機(jī)系統(tǒng)結(jié)構(gòu)：第七章 多處理機(jī)-教材

1、第七章 多處理機(jī)主要介紹：多處理機(jī)結(jié)構(gòu)的分類；多處理機(jī)體系結(jié)構(gòu)；多處理機(jī)的存儲器體系結(jié)構(gòu)；多處理機(jī)的互連方式第七章 多處理機(jī)引言并行計算機(jī)體系結(jié)構(gòu)的分類Flynn分類法：（1）SISD；（2）SIMD；（3）MISD；（4）MIMD。第七章 多處理機(jī)引言MIMD是通用多處理機(jī)體系結(jié)構(gòu)的主流：（1）MIMD具有靈活性。（2）MIMD可以充分利用商品化微處理器在性能價格比方面的優(yōu)勢。MIMD的兩種結(jié)構(gòu)：（1）集中式共享存儲器結(jié)構(gòu)（UMA）；（2）分布的物理存儲器結(jié)構(gòu)。第七章 多處理機(jī)引言存儲器分布到各個節(jié)點的好處：（1）如果大多數(shù)的訪問時針對本節(jié)點的局部存儲器，則可以降低存儲器和互連網(wǎng)絡(luò)的帶寬要求

2、；（2）對局部存儲器的訪問延遲低。缺點：處理器之間的通信復(fù)雜，且處理器之間訪問延遲大。第七章 多處理機(jī)引言通信模型和存儲器的結(jié)構(gòu)模型分布式存儲器結(jié)構(gòu)的通信模型有兩類：（1）（DSM或SSM）物理上分離的多個存儲器可以作為一個邏輯上共享存儲空間進(jìn)行編址，一個處理器如果具有訪問權(quán)限，就可以訪問任何一個其他的局部存儲器（NUMA）；（2）整個地址空間由多個獨立的地址空間構(gòu)成，它們在邏輯上也是獨立的，遠(yuǎn)程的處理器不能對其直接尋址（多計算機(jī)）。通信機(jī)制：（1）NUMA采用LOAD和STORE指令；（2）多計算機(jī)系統(tǒng)采用消息傳遞，RPC是消息傳遞的一種特殊形式。第七章 多處理機(jī)引言通信機(jī)制的性能：（1）通

3、信帶寬(P270)；（2）通信延遲(P270) ； 通信延遲=發(fā)送開銷+跨越時間+ 傳輸延遲+ 接收開銷（3）通信延遲的隱藏(P270) 。第七章 多處理機(jī)引言不同通信機(jī)制的優(yōu)點共享存儲器通信的優(yōu)點(P270) ：（1）與常用的集中式多處理器使用的通信機(jī)制兼容；（2）易于編程、簡化編譯器設(shè)計；（3）當(dāng)通信數(shù)據(jù)較少時，通信開銷低，帶寬利用較好；（4）通過硬件控制的Cache減少了遠(yuǎn)程通信的頻度、減少了通信延遲、減少了共享數(shù)據(jù)的訪問沖突。消息傳遞通信機(jī)制的優(yōu)點(P271) ：（1）硬件較簡單；（2）通信是顯式的，程序員可著重處理開銷大的通信。第七章 多處理機(jī)引言并行處理面臨的挑戰(zhàn)(P271)（1）

4、程序中有限的并行性（通過更好的算法來解決）；（2）相對較高的通信開銷（多種方法解決：如體系結(jié)構(gòu)的支持、編程技術(shù)支持、數(shù)據(jù)重組增加局部訪問減少遠(yuǎn)程訪問、預(yù)取技術(shù)等）。程序的粒度：并行程序的計算/通信比率。第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)集中式共享存儲器體系結(jié)構(gòu)共享數(shù)據(jù)與私有數(shù)據(jù)。Cache的一致性問題：多個處理器cache對應(yīng)同一存儲器單元產(chǎn)生出不同的值。存儲系統(tǒng)是一致的：如果對某個數(shù)據(jù)項的任何讀操作均可以得到其最新寫入的值，則認(rèn)為這個存儲系統(tǒng)是一致的。第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)一致性存儲系統(tǒng)要滿足的三個條件：（1）處理器P對X進(jìn)行一次寫之后又對X進(jìn)行讀，讀寫之間沒有其他處

5、理器對X進(jìn)行寫，則讀的返回值總是寫進(jìn)的值；（2）一個處理器對X進(jìn)行寫之后，另一個處理器對X進(jìn)行讀，讀和寫之間無其他寫，則讀X的返回值應(yīng)為寫進(jìn)的值；（3）對同一單元的寫是順序化的，即任意兩個處理器對同一單元的兩次寫，從所有處理器看來順序都應(yīng)是相同的。第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)實現(xiàn)一致性的基本方案： 共享數(shù)據(jù)的遷移和復(fù)制：共享數(shù)據(jù)的遷移是把遠(yuǎn)程的共享數(shù)據(jù)項拷貝到本地處理器的局部cache中使用，從而降低了對遠(yuǎn)程共享數(shù)據(jù)的訪問延遲；共享數(shù)據(jù)的復(fù)制是把多個處理器需要同時讀取的共享數(shù)據(jù)項拷貝到各自局部cache中使用，復(fù)制不僅降低了訪存的延遲，也減少了訪問共享數(shù)據(jù)所產(chǎn)生的沖突。第七章 多處

6、理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)共享數(shù)據(jù)狀態(tài)跟蹤技術(shù)：（1）目錄協(xié)議：物理存儲器中共享數(shù)據(jù)塊的狀態(tài)及相關(guān)信息均被保存在一個被稱為目錄的地方。（2）監(jiān)聽協(xié)議：每個cache除了包含物理存儲器中塊的數(shù)據(jù)拷貝之外，也保存著各個塊的共享狀態(tài)信息。各個cache控制器通過監(jiān)聽總線來判斷它們是否有總線上請求的數(shù)據(jù)塊。第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)維持一致性的方法：寫作廢協(xié)議和寫更新協(xié)議。寫作廢協(xié)議：在一個處理器寫某個數(shù)據(jù)項之前保證它對該數(shù)據(jù)項有唯一的訪問權(quán)。所以其他副本應(yīng)該作廢。寫更新協(xié)議：當(dāng)一個處理器寫某個數(shù)據(jù)項時，通過廣播使其他cache中所有對應(yīng)的該數(shù)據(jù)項的副本進(jìn)行更新。第七章 多處理機(jī)多處理

7、機(jī)的存儲器體系結(jié)構(gòu)處理器行為總線行為CPU A cache內(nèi)容CPU B cache內(nèi)容主存X單元內(nèi)容0CPU A讀XCache失效00CPU B讀XCache失效000CPU A將X單元寫1作廢X單元1CPU B讀XCache失效111在寫回cache的條件下，監(jiān)聽總線中寫作廢協(xié)議第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)處理器行為總線行為CPU A cache內(nèi)容CPU B cache內(nèi)容主存X單元內(nèi)容0CPU A讀XCache失效00CPU B讀XCache失效000CPU A將X單元寫1廣播寫X單元111CPU B讀XCache失效111在寫回cache的條件下，監(jiān)聽總線中寫更新協(xié)議第七

8、章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)寫更新和寫作廢協(xié)議性能上的差別：（1）對同一數(shù)據(jù)的多個寫而中間無讀操作的情況，寫更新協(xié)議需進(jìn)行多次寫廣播操作，而在寫作廢協(xié)議下只需一次作廢操作。（2）對同一塊中多個字進(jìn)行寫，寫更新協(xié)議對每個字的寫均要進(jìn)行一次廣播，而在寫作廢協(xié)議下僅在對本塊第一次寫時進(jìn)行作廢操作即可。（3）從一個處理器寫到另一個處理器讀之間的延遲通常在寫更新模式中較低，因為它寫數(shù)據(jù)時馬上更新了相應(yīng)的其他cache中的內(nèi)容。而在寫作廢協(xié)議中，需要讀一個新的拷貝。第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)監(jiān)聽協(xié)議的基本實現(xiàn)技術(shù)：（1）如何利用總線進(jìn)行作廢操作？（2）寫cache未命中時，需哪些操作

9、？（3）寫cache未命中時，如何獲得最新數(shù)據(jù)（寫直達(dá)法的情況下？寫回法的情況下？）（4）在寫回法的情況下，塊的有效位的作用？（5）塊的共享位的作用？（6）狀態(tài)控制器的作用？第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)分布式共享存儲器體系結(jié)構(gòu)1.基于目錄的cache一致性Cache塊的三種狀態(tài)：共享、未緩沖、專有。存儲器的每一塊在目錄中有一個對應(yīng)項，每一個目錄項主要有“狀態(tài)”和“位向量”兩種成分。第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)2.目錄協(xié)議的基本實現(xiàn)技術(shù)（1）當(dāng)一個塊處于未緩沖狀態(tài)時，如何處理讀失效？如何處理寫失效？（2）當(dāng)一個塊處于共享狀態(tài)時，如何處理讀失效？如何處理寫失效？（3）當(dāng)一個

10、塊處于專有狀態(tài)時，如何處理讀失效？如何處理寫失效？如何進(jìn)行數(shù)據(jù)寫回。第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)目錄三種協(xié)議：全映像目錄、有限映像目錄、鏈?zhǔn)侥夸?。第七?多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)全映像目錄第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)有限映像目錄第七章 多處理機(jī)多處理機(jī)的存儲器體系結(jié)構(gòu)鏈?zhǔn)侥夸浀谄哒?多處理機(jī)互連網(wǎng)絡(luò)什么是互連網(wǎng)絡(luò)：互連網(wǎng)絡(luò)是將集中式系統(tǒng)或分布式系統(tǒng)中的節(jié)點連接起來所構(gòu)成的網(wǎng)絡(luò)。節(jié)點：可能是處理器、存儲模塊或其他設(shè)備，它們通過互連網(wǎng)絡(luò)進(jìn)行信息交換。第七章 多處理機(jī)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)的性能參數(shù)靜態(tài)網(wǎng)絡(luò)：由點和點直接相連，這種連接方式在程序執(zhí)行過程中不會改變。動態(tài)網(wǎng)絡(luò)：

11、用開關(guān)通道實現(xiàn)的，它可動態(tài)地改變結(jié)構(gòu)，使其與用戶程序中的通信相匹配。網(wǎng)絡(luò)的表示方法：常用圖表示，圖是由有向邊或無向邊連接的有限個節(jié)點構(gòu)成。其節(jié)點數(shù)目稱為網(wǎng)絡(luò)規(guī)模。第七章 多處理機(jī)互連網(wǎng)絡(luò)（1）節(jié)點度、入度和出度。（2）網(wǎng)絡(luò)直徑。（3）等分寬度。（4）通道長度。對稱網(wǎng)絡(luò)：從其中的任何一個節(jié)點看，拓?fù)浣Y(jié)構(gòu)都是一樣的。第七章 多處理機(jī)互連網(wǎng)絡(luò)路由在網(wǎng)絡(luò)通信中對路徑的選擇與指定?；ミB函數(shù)：反映不同互連網(wǎng)絡(luò)的連接特性。如果把互連網(wǎng)絡(luò)的N個入端和N個出端各自用整數(shù)0、1、N-1代表，則互連函數(shù)則表示互連的出端號和入端號的一一對應(yīng)關(guān)系。第七章 多處理機(jī)互連網(wǎng)絡(luò)1.循環(huán)循環(huán)互連函數(shù)f(x)表示為(x0,x1,

12、x2,xj)其含義為：f(x0)=x1, f(x1)=x2, , f(xj)=x0循環(huán)周期為：j+1第七章 多處理機(jī)互連網(wǎng)絡(luò)2.置換對象的重新排序！對于n個對象來說，有n！中置換。例如置換=(a,b,c)(d,e)3.均勻混洗x=(xk-1,x1,x0)f(x)=(xk-2,x1,x0,xk-1)第七章 多處理機(jī)互連網(wǎng)絡(luò)4.超立方體x=(xn-1,xk,x1,x0)f(x)=(xn-1,xk,x1,x0)5.廣播和選播廣播是一種一對全體的映射，選播是一個子集到另一個子集（多對多）的映射。第七章 多處理機(jī)互連網(wǎng)絡(luò)靜態(tài)連接網(wǎng)絡(luò)靜態(tài)連接網(wǎng)絡(luò)使用直接鏈路，一旦構(gòu)成后就固定不變。1.線性陣列2.環(huán)和帶弦環(huán)3.循環(huán)移數(shù)網(wǎng)絡(luò)4.樹形和星形第七章 多處理機(jī)互連網(wǎng)絡(luò)5.胖樹形6.網(wǎng)格形和環(huán)形網(wǎng)7.超立方體8.K元n-立方體網(wǎng)絡(luò)第七章 多處理機(jī)互連網(wǎng)絡(luò)動態(tài)連接網(wǎng)絡(luò)采用動態(tài)網(wǎng)絡(luò)的多處理器互連是在程序控制下實現(xiàn)的。動態(tài)連接網(wǎng)絡(luò)的主要操作特征：定時、開關(guān)和控制。單級網(wǎng)絡(luò)（循環(huán)網(wǎng)絡(luò)）與多級網(wǎng)絡(luò)。阻塞網(wǎng)絡(luò)與非阻塞網(wǎng)絡(luò)。第七章 多處理機(jī)互連網(wǎng)絡(luò)1.總線系統(tǒng)2.交叉開關(guān)網(wǎng)絡(luò)3.多端口存儲器