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

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

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

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

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

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

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

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

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

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

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

11、用開(kāi)關(guān)通道實(shí)現(xiàn)的，它可動(dòng)態(tài)地改變結(jié)構(gòu)，使其與用戶(hù)程序中的通信相匹配。網(wǎng)絡(luò)的表示方法：常用圖表示，圖是由有向邊或無(wú)向邊連接的有限個(gè)節(jié)點(diǎn)構(gòu)成。其節(jié)點(diǎn)數(shù)目稱(chēng)為網(wǎng)絡(luò)規(guī)模。第七章 多處理機(jī)互連網(wǎng)絡(luò)（1）節(jié)點(diǎn)度、入度和出度。（2）網(wǎng)絡(luò)直徑。（3）等分寬度。（4）通道長(zhǎng)度。對(duì)稱(chēng)網(wǎng)絡(luò)：從其中的任何一個(gè)節(jié)點(diǎn)看，拓?fù)浣Y(jié)構(gòu)都是一樣的。第七章 多處理機(jī)互連網(wǎng)絡(luò)路由在網(wǎng)絡(luò)通信中對(duì)路徑的選擇與指定?；ミB函數(shù)：反映不同互連網(wǎng)絡(luò)的連接特性。如果把互連網(wǎng)絡(luò)的N個(gè)入端和N個(gè)出端各自用整數(shù)0、1、N-1代表，則互連函數(shù)則表示互連的出端號(hào)和入端號(hào)的一一對(duì)應(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.置換對(duì)象的重新排序！對(duì)于n個(gè)對(duì)象來(lái)說(shuō)，有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.廣播和選播廣播是一種一對(duì)全體的映射，選播是一個(gè)子集到另一個(gè)子集（多對(duì)多）的映射。第七章 多處理機(jī)互連網(wǎng)絡(luò)靜態(tài)連接網(wǎng)絡(luò)靜態(tài)連接網(wǎng)絡(luò)使用直接鏈路，一旦構(gòu)成后就固定不變。1.線(xiàn)性陣列2.環(huán)和帶弦環(huán)3.循環(huán)移數(shù)網(wǎng)絡(luò)4.樹(shù)形和星形第七章 多處理機(jī)互連網(wǎng)絡(luò)5.胖樹(shù)形6.網(wǎng)格形和環(huán)形網(wǎng)7.超立方體8.K元n-立方體網(wǎng)絡(luò)第七章 多處理機(jī)互連網(wǎng)絡(luò)動(dòng)態(tài)連接網(wǎng)絡(luò)采用動(dòng)態(tài)網(wǎng)絡(luò)的多處理器互連是在程序控制下實(shí)現(xiàn)的。動(dòng)態(tài)連接網(wǎng)絡(luò)的主要操作特征：定時(shí)、開(kāi)關(guān)和控制。單級(jí)網(wǎng)絡(luò)（循環(huán)網(wǎng)絡(luò)）與多級(jí)網(wǎng)絡(luò)。阻塞網(wǎng)絡(luò)與非阻塞網(wǎng)絡(luò)。第七章 多處理機(jī)互連網(wǎng)絡(luò)1.總線(xiàn)系統(tǒng)2.交叉開(kāi)關(guān)網(wǎng)絡(luò)3.多端口存儲(chǔ)器