計算機系統(tǒng)結(jié)構(gòu)(第二版)尹朝慶主編第6章多處理機

《計算機系統(tǒng)結(jié)構(gòu)(第二版)尹朝慶主編第6章多處理機》由會員分享，可在線閱讀，更多相關(guān)《計算機系統(tǒng)結(jié)構(gòu)(第二版)尹朝慶主編第6章多處理機（105頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1第第6章章 多處理機多處理機6.1 多處理機的結(jié)構(gòu)與特點多處理機的結(jié)構(gòu)與特點6.2 多處理機的多處理機的Cache一致性一致性6.3 多處理機的軟件多處理機的軟件6.4 多處理機的性能多處理機的性能6.5 MIMD并行機結(jié)構(gòu)模型并行機結(jié)構(gòu)模型第第6 6章章 多處理機多處理機2多處理機具有兩臺以上處理機，每臺處理機可以帶有本地Cache、本地存儲器、甚至I/O設(shè)備，它們都能獨立執(zhí)行各自的程序。多臺處理機之間通過總線、縱橫交叉開關(guān)、多級互連網(wǎng)絡(luò)或高速的商品化網(wǎng)絡(luò)實現(xiàn)互連。多處理機可以通過共享存儲器，也可以通過消息傳送系統(tǒng)來實現(xiàn)處理機間的通信。多臺處理機在操作系統(tǒng)的控制下，實現(xiàn)資源的統(tǒng)一分配與調(diào)度

2、。第第6 6章章 多處理機多處理機36.1多處理機的結(jié)構(gòu)與特點多處理機的結(jié)構(gòu)與特點6.1.1 多處理機的結(jié)構(gòu)多處理機的結(jié)構(gòu)多處理機在系統(tǒng)結(jié)構(gòu)上可分為兩類：1.緊耦合多處理機2.松耦合多處理機第第6 6章章 多處理機多處理機41.緊耦合多處理機緊耦合多處理機是通過共享主存來實現(xiàn)處理機間的通信的。各處理機與主存之間通過一個互連網(wǎng)絡(luò)連接。它的典型結(jié)構(gòu)如圖6.1所示。 第第6 6章章 多處理機多處理機5在緊耦合多處理機系統(tǒng)中，為了減少處理機訪問主存的沖突而采取的措施有：v 多處理機的主存采用多模塊交叉存取。模塊數(shù)越多，發(fā)生訪主存沖突的概率將越低，但必須解決好數(shù)據(jù)在各存儲器模塊中的定位和分配。v 讓每臺

3、處理機擁有一個小容量的本地存儲器，用來存放頻繁使用的核心代碼等，以減少對主存的訪問。v 讓每臺處理機都有一個Cache，以減少對主存的訪問。但要解決好Cache與主存之間以及各個Cache之間的數(shù)據(jù)一致性問題。第第6 6章章 多處理機多處理機6緊耦合多處理機按所用處理機類型是否相同可分為同構(gòu)型和異構(gòu)型兩種。而按其對稱性又可分為對稱式多處理機和非對稱式多處理機。如果緊耦合多處理機中的每臺處理機在訪問任意一個存儲器模塊或I/O用設(shè)備時，都具有同等的能力，那么這個系統(tǒng)就具有對稱性。反之，表示多處理機是非對稱的。一個多處理機要成為對稱式多處理機必須滿足兩個條件：首先存儲器必須是集中共享的，其次系統(tǒng)所用

4、的互連網(wǎng)絡(luò)也必須是對稱的。 第第6 6章章 多處理機多處理機7具有非對稱I/O子系統(tǒng)的多處理機如圖6.2所示。第第6 6章章 多處理機多處理機8采用冗余連接非對稱I/O子系統(tǒng)的多處理機如圖6.3所示第第6 6章章 多處理機多處理機9 在緊耦合多處理機中，常見的組合是同構(gòu)對稱式多處理機及異構(gòu)非對稱式多處理機。 1）同構(gòu)對稱式多處理機 Sequent公司生產(chǎn)的Balance多處理機就是同構(gòu)對稱式的，它的結(jié)構(gòu)如圖6.4所示。 第第6 6章章 多處理機多處理機10第第6 6章章 多處理機多處理機112）異構(gòu)非對稱式多處理機異構(gòu)非對稱式多處理機的一般結(jié)構(gòu)如圖6.5所示。 第第6 6章章 多處理機多處理機

5、122. 松耦合多處理機松耦合多處理機是通過消息傳送方式來實現(xiàn)處理機間的相互通信的。每臺處理機是由一個獨立性較強的計算機模塊組成，該模塊由處理器、較大容量的本地存儲器（在運算時所需的絕大部分的指令和數(shù)據(jù)均取自本地存儲器）、I/O設(shè)備以及網(wǎng)絡(luò)接口電路組成。各模塊之間通過消息傳送系統(tǒng)(MTS)相連接。當不同模塊上運行的進程間需要通信時，通過網(wǎng)絡(luò)接口電路及消息傳送系統(tǒng)進行信息交換。由于這種相互間的耦合程度是很松散的，因此稱之為松耦合多處理機。 第第6 6章章 多處理機多處理機13松耦合多處理機可分為層次式和非層次式兩種結(jié)構(gòu)。1）松耦合非層次式多處理機圖6.6所示是一個典型的通過消息傳送系統(tǒng)進行互連的

6、松耦合非層次式多處理機。 第第6 6章章 多處理機多處理機142）松耦合層次式多處理機松耦合層次式多處理機采用多級總線實現(xiàn)層次連接。圖6.7所示為卡內(nèi)基梅隆大學研制的Cm* 松耦合層次式多處理機。 第第6 6章章 多處理機多處理機156.1.2 多處理機的特點多處理機的特點1.靈活性和通用性強 2.高層次的并行性等級 3.并行任務(wù)派生 4.進程同步 5.資源分配和任務(wù)調(diào)度 第第6 6章章 多處理機多處理機166.2 多處理機的多處理機的Cache一致性一致性Cache作為提高系統(tǒng)性能的一種技術(shù)手段在計算機系統(tǒng)中得到普遍的使用。在共享存儲器的多處理機中，每臺處理機都有自己的局部Cache。這類多

7、處理機在運行一個具有多個進程的程序時，各處理機可能會使用到共享存儲器中的同一數(shù)據(jù)塊，為維持多處理機的高速運行，這些共享數(shù)據(jù)塊將被調(diào)入各處理機的局部Cache中。由于多個處理機是異步地獨立操作，可能使共享存儲器中同一數(shù)據(jù)塊的不同Cache拷貝出現(xiàn)不一致，就可能危及系統(tǒng)的正常運行，這就是Cache的一致性問題。第第6 6章章 多處理機多處理機176.2.1 出現(xiàn)出現(xiàn)Cache一致性問題的原因一致性問題的原因出現(xiàn)Cache一致性問題的原因主要有3個：1.共享可寫的數(shù)據(jù)2.進程遷移3.I/O傳輸?shù)诘? 6章章 多處理機多處理機181共享可寫數(shù)據(jù)引起的不一致 假設(shè)在寫操作之前，Cache的初始狀態(tài)如圖6

8、.8(a)所示。處理機P1和P2的局部高速緩沖存儲器Cache1和Cache2中分別有共享存儲器的某個數(shù)據(jù)x的副本。第第6 6章章 多處理機多處理機19 若采用寫直達法，如圖6.8(b)所示，當處理機P1改寫Cache1中的數(shù)據(jù)為x時，共享存儲器中的相應(yīng)數(shù)據(jù)也立即更新為x，這將導致Cache1中的數(shù)據(jù)與Cache2中所緩存的數(shù)據(jù)不一致。第第6 6章章 多處理機多處理機20 若采用寫回法，如圖6.8(c)所示，當處理機P1改寫Cache1中的數(shù)據(jù)為x時，Cache1的變化不會引起Cache2和共享存儲器的變化，這將導致Cache1中的數(shù)據(jù)與共享存儲器和Cache2中所緩存的數(shù)據(jù)不一致。第第6 6

9、章章 多處理機多處理機212進程遷移引起的不一致 在多處理機上，有時為了提高系統(tǒng)的效率而允許進程遷移，將一個尚未執(zhí)行完而被掛起的進程調(diào)度到另一個空閑的處理機上去執(zhí)行，使系統(tǒng)中各處理機的負荷保持均衡。但這樣做可能會造成Cache一致性問題。 假設(shè)在遷移前Cache的初始狀態(tài)仍如圖6.9(a)所示，處理機P1的Cache1中有共享存儲器中數(shù)據(jù)x的拷貝，而處理機P2的Cache2中沒有該數(shù)據(jù)。第第6 6章章 多處理機多處理機22 若采用寫直達法，如圖6.9(b)所示，當某進程從P1遷移到P2后，處理機P2在執(zhí)行此進程時需要使用數(shù)據(jù)x時，會將x所在塊由共享存儲器調(diào)入Cache2。假設(shè)進程運行時將Cac

10、he2的數(shù)據(jù)x改寫為x，在共享存儲器中的相應(yīng)數(shù)據(jù)也立即更新為x，這將導致共享存儲器和Cache2中的數(shù)據(jù)與處理機P1中Cache1所緩存的數(shù)據(jù)的不一致。第第6 6章章 多處理機多處理機23 若采用寫回法，如圖6.9(c)所示，當處理機P1修改Cache1中的數(shù)據(jù)成x時Cache1的變化不會引起共享存儲器的變化。當某進程從P1遷移到P2后，處理機P2在執(zhí)行此進程時需要使用數(shù)據(jù)x時，會將x所在塊由共享存儲器調(diào)入Cache2。此時調(diào)入的數(shù)據(jù)x并非是已經(jīng)修改過的x，這將導致共享存儲器及Cache2與處理機P1中Cache1所緩存的數(shù)據(jù)的不一致。第第6 6章章 多處理機多處理機243I/O操作引起的不一

11、致 假設(shè)在執(zhí)行I/O操作之前，Cache的初始狀態(tài)如圖6.10(a)所示。處理機P1和P2的局部Cache中分別有共享存儲器的某個數(shù)據(jù)x的拷貝。 第第6 6章章 多處理機多處理機25 若采用寫直達法，當I/O處理機執(zhí)行輸入操作，直接將共享存儲器中的數(shù)據(jù)x改寫成x時，將導致Cache1和Cache2中的數(shù)據(jù)與共享存儲器數(shù)據(jù)的不一致，如圖6.10(b)所示。第第6 6章章 多處理機多處理機26 若采用寫回法，當處理機P1將Cache1中的數(shù)據(jù)x改寫為x時，由于Cache1數(shù)據(jù)的修改不會立即引起共享存儲器中數(shù)據(jù)x的更新，此時若此數(shù)據(jù)恰好被I/O處理機輸出，就會造成輸出錯誤，如圖6.10(c)所示。第

12、第6 6章章 多處理機多處理機27 解決多處理器維護Cache一致性的協(xié)議稱為Cache一致性協(xié)議。實現(xiàn)Cache一致性協(xié)議的關(guān)鍵是跟蹤共享數(shù)據(jù)塊的狀態(tài)。目前有兩類協(xié)議，它們采用了不同的共享數(shù)據(jù)狀態(tài)跟蹤技術(shù)，分別適合于不同的系統(tǒng)結(jié)構(gòu)。 （1）監(jiān)聽：每個Cache除了包含物理存儲器中塊的數(shù)據(jù)拷貝之外，也保存著各個塊的共享狀態(tài)信息。這是一種基于總線的一致性協(xié)議，各處理機通過監(jiān)聽總線上處理機與存儲器之間的Cache操作事件，對各自局部Cache中的數(shù)據(jù)采取保持一致性的措施。 （2）目錄：物理存儲器中共享數(shù)據(jù)塊的狀態(tài)及相關(guān)信息均被保存在一個稱為目錄的地方。共享數(shù)據(jù)塊的變化通過此數(shù)據(jù)塊所在的各目錄項，將

13、一致性命令發(fā)給所有存放該數(shù)據(jù)塊拷貝的Cache。第第6 6章章 多處理機多處理機286.2.2 監(jiān)聽一致性協(xié)議監(jiān)聽一致性協(xié)議 在基于總線互連結(jié)構(gòu)的系統(tǒng)中，各處理機的Cache都連接到公共總線。一般都采用監(jiān)聽協(xié)議，通過總線監(jiān)聽機制實現(xiàn)高速緩存和共享存儲器之間的數(shù)據(jù)一致性。監(jiān)聽協(xié)議有兩種策略來保持Cache一致性：1.寫無效策略2.寫更新策略第第6 6章章 多處理機多處理機291. 寫無效策略 寫無效策略是指在某局部Cache數(shù)據(jù)被修改后，使所有其它Cache中的相應(yīng)數(shù)據(jù)拷貝都無效。 假設(shè)在寫操作之前，Cache的初始狀態(tài)如圖6.11(a)所示。處理機P1和P2的局部Cache中都存有共享存儲器中

14、數(shù)據(jù)x的拷貝，圖中數(shù)據(jù)x加虛線框表示數(shù)據(jù)x所在的數(shù)據(jù)塊。 當處理機P1要進行寫操作時，它必須首先獲得對x的唯一訪問權(quán)， 然后更新數(shù)據(jù)為x并使Cache2中的相應(yīng)數(shù)據(jù)塊拷貝失效（標志為I）。第第6 6章章 多處理機多處理機30 若采用寫直達法，則共享存儲器中的數(shù)據(jù)x將會立即更新為x，如圖6.11(b)所示。當處理機P2訪問已修改的數(shù)據(jù)x時，會發(fā)生Cache2失效并從共享存儲器中讀取新值x，同時將x所在數(shù)據(jù)塊調(diào)入Cache2。第第6 6章章 多處理機多處理機31 若采用寫回法，則共享存儲器中數(shù)據(jù)x所在的數(shù)據(jù)塊也將被設(shè)置為無效，如圖6.11(c)所示。當處理機P2訪問已修改的數(shù)據(jù)x時，會發(fā)生Cach

15、e2失效并從處理機P1的Cache1讀取新值x，同時將x所在數(shù)據(jù)塊調(diào)入Cache2并且更新共享存儲器中的相應(yīng)數(shù)據(jù)塊。第第6 6章章 多處理機多處理機322.寫更新策略 寫更新策略是指在某局部Cache數(shù)據(jù)被修改后，通過總線廣播修改后的數(shù)據(jù)使所有含有相應(yīng)數(shù)據(jù)拷貝的其他Cache進行更新。 假設(shè)在寫操作之前，Cache的初始狀態(tài)如圖6.12(a)所示。處理機P1和P2的局部Cache中都存有共享存儲器中數(shù)據(jù)x的拷貝。第第6 6章章 多處理機多處理機33 若采用寫直達法，則共享存儲器中數(shù)據(jù)x所在的數(shù)據(jù)塊將會立即更新，如圖6.12(b)所示。若采用寫回法，則共享存儲器中數(shù)據(jù)x所在的數(shù)據(jù)塊將會被設(shè)置為無

16、效，如圖6.12(c)所示。第第6 6章章 多處理機多處理機34寫更新和寫無效策略性能上的差別來自三個方面：對同一數(shù)據(jù)的多個寫而中間無讀操作的情況，寫更新策略需進行多次寫廣播操作，而在寫無效策略下只需一次置無效操作。對同一塊中多個字進行寫操作，寫更新策略對每個字的寫均要進行一次廣播，而在寫無效策略下僅在對該塊第一次寫時進行置無效操作即可。寫無效是針對Cache塊進行操作，而寫更新則是針對字（或字節(jié)）進行操作。從一個處理機寫到另一個處理機讀之間的延遲通常在寫更新模式中較低，因為它寫數(shù)據(jù)時馬上更新了相應(yīng)的其他Cache中的內(nèi)容（假設(shè)讀的處理器Cache中有此數(shù)據(jù)）。而在寫無效策略中，需要讀一個新的

17、拷貝。第第6 6章章 多處理機多處理機356.2.3 基于目錄的協(xié)議基于目錄的協(xié)議 在監(jiān)聽協(xié)議中，每當Cache被修改時，要與所有的Cache進行通信，包括對于可能共享的數(shù)據(jù)的寫操作，這可能導致總線的流量大大增加。 基于目錄的協(xié)議的基本思想是：使用Cache目錄來記錄可以進入Cache的每個數(shù)據(jù)塊的訪問狀態(tài)、該塊在各個處理機的共享狀態(tài)以及是否修改過等信息。把一致性命令只發(fā)給存有相應(yīng)數(shù)據(jù)塊拷貝的Cache，從而支持Cache的一致性。各種目錄協(xié)議的主要差別是目錄存放什么信息以及如何維護信息。 第第6 6章章 多處理機多處理機36根據(jù)目錄的結(jié)構(gòu)特點，基于目錄的協(xié)議可分為三類：1.全映射目錄（ful

18、l-map directory）2.有限目錄（limited directory）3.鏈式目錄（chained directory） 第第6 6章章 多處理機多處理機371. 全映射目錄協(xié)議 全映射目錄協(xié)議規(guī)定共享存儲器中的每個數(shù)據(jù)塊都有一個目錄項，每個目錄項中有N個處理機位和一個重寫位，其中N為處理機的臺數(shù)，目錄項結(jié)構(gòu)如圖6.13所示。 第第6 6章章 多處理機多處理機38 下面以三個處理機的系統(tǒng)為例，說明全映射目錄的三種狀態(tài)以及全映射目錄協(xié)議保持Cache一致性的原理。 （1）處理機Cache中沒有包含單元x的數(shù)據(jù)塊副本 全映射目錄的第一種狀態(tài)。此時，包含單元x的數(shù)據(jù)塊Bd目錄項中的三個處

19、理機位均為“0”，表示整個系統(tǒng)所有Cache中都沒有數(shù)據(jù)塊Bd的副本；重寫位為未寫(C)狀態(tài)，表示沒有一臺處理機允許寫入該數(shù)據(jù)塊。第第6 6章章 多處理機多處理機39（2）處理機從共享存儲器讀入數(shù)據(jù)塊到Cache 當三臺處理機都有過讀x的請求之后，全映射目錄出現(xiàn)第二種狀態(tài)。目錄項中的三個處理機位被置“1”，表示這些Cache中已有數(shù)據(jù)塊Bd的拷貝；重寫位仍為未寫狀態(tài)，不允許處理機寫Cache塊Bd。此時，三個Cache中Bd的Cache塊狀態(tài)位均為有效位1，允許寫位0，與Cache目錄的狀態(tài)位一致。第第6 6章章 多處理機多處理機40（3）處理機寫Cache塊 如果處理機P3向Cache3發(fā)出

20、寫x（或Bd中其它單元）的請求，全映射目錄將從第二種狀態(tài)轉(zhuǎn)換到第三種狀態(tài)，此時的Cache全映射目錄呈現(xiàn)第三種狀態(tài)。目錄項中Cache1和Cache2的處理機位被置“0”，表示這些Cache中數(shù)據(jù)塊Bd的拷貝已失效；Cache3的處理機位為“1”，同時重寫位為重寫狀態(tài)，表示允許處理機P3寫Cache塊Bd，且Cache3中的Bd塊已被修改為Bd。第第6 6章章 多處理機多處理機412. 有限目錄協(xié)議 有限目錄協(xié)議與全映射目錄協(xié)議十分相似，都有一位重寫位，但有限目錄的目錄項中的指針（處理機位）實際上是數(shù)目固定的若干個處理機編號。若共有N臺處理機，則每個處理機指針為log2N位。有I個指針域的目錄

21、項最多只能允許該數(shù)據(jù)塊裝入I個Cache中，有限目錄協(xié)議使用IN個指針，可以緩解目錄過大的問題。 第第6 6章章 多處理機多處理機42 如圖6.15所示，假設(shè)多處理機系統(tǒng)中共有三臺處理機，目錄項中只有兩個指針域。當P1和P2的Cache中都有單元x所在數(shù)據(jù)塊Bd的拷貝時，該數(shù)據(jù)塊對應(yīng)的目錄項中的兩個指針分別指向處理機P1和P2。 第第6 6章章 多處理機多處理機433. 鏈式目錄協(xié)議 鏈式目錄通過將目錄信息分布到多個小規(guī)模的本地目錄中來模擬全映射機制。其主要思想是通過維護一個目錄指針鏈來跟蹤共享數(shù)據(jù)塊的拷貝。要想得到某個數(shù)據(jù)塊在所有Cache中的共享情況，必須搜索整個Cache目錄鏈。鏈式目錄

22、的優(yōu)點在于既不限制共享數(shù)據(jù)塊的拷貝數(shù)目，又保持了可擴展性。鏈式目錄有兩種實現(xiàn)方法，單向鏈和雙向鏈。若采用比較簡單的單向鏈，則目錄項中除一位重寫位之外，只需要一個指針域。第第6 6章章 多處理機多處理機44采用單向鏈的鏈式目錄如圖6.16所示。 第第6 6章章 多處理機多處理機456.3 多處理機的軟件多處理機的軟件6.3.1并行算法并行算法算法對于并行性的開發(fā)至關(guān)重要。算法必須適應(yīng)具體的計算機結(jié)構(gòu)。對表達式E1abxcx2dx3 ，順序算法與并行算法比較如圖6.17所示。將運算過程用樹形流程圖來表示的方法。運算的級數(shù)就是樹的高度，用Tp代表；P為所需處理機數(shù)目；Sp為加速比，SpTl/Tp；E

23、p為效率，EpSp/P 第第6 6章章 多處理機多處理機46 對樹進行變換來降低樹高，減少運算級數(shù)，即可提高運算的并行性。樹形結(jié)構(gòu)可以用交換律、結(jié)合律、分配律來變換。 先從算術(shù)表達式的最直接形式出發(fā)，利用交換律把相同的運算集中在一起；再利用結(jié)合律把參加運算的操作數(shù)（稱原子）配對，盡可能并行運算，組成樹高最小的子樹；最后利用分配律，平衡各分支運算的級數(shù)，把這些子樹結(jié)合起來，使總級數(shù)減至最少。 第第6 6章章 多處理機多處理機47 例如：某表達式E2ab(cdefg)h，需7級運算，如圖6.18(a)所示。利用交換律和結(jié)合律改寫為E2(ah)b(cg)def ，則需5級運算，如圖6.18(b)所示

24、。 第第6 6章章 多處理機多處理機48再利用分配律，將上式改寫為E2(ah)(bcbg)bdef則用3個處理機，僅需4級運算。如圖6.18(c)所示。 第第6 6章章 多處理機多處理機496.3.2 程序并行性分析程序并行性分析除算法以外，任務(wù)間能否并行在很大程度還取決于程序的結(jié)構(gòu)形式。假設(shè)一個程序包含P1、P2、Pi、Pj、Pn等n個程序段，其書寫的順序反映了該程序正常執(zhí)行的順序。為了便于分析，設(shè)Pi和Pj程序段都是一條語句，Pi在Pj之前執(zhí)行，且只討論Pi和Pj之間的直接數(shù)據(jù)相關(guān)關(guān)系。第第6 6章章 多處理機多處理機50程序段之間會出現(xiàn)類似的3種數(shù)據(jù)相關(guān)。1.如果Pi的左部變量在Pj的右

25、部變量集內(nèi)，且Pj要從Pi取得運算結(jié)果來作為操作數(shù)，則稱Pj“數(shù)據(jù)相關(guān)”于Pi。如Pi A = B + DPj C = A * EPj必須取Pi算得的A值作為操作數(shù)，相當于流水中發(fā)生的“先寫后讀”相關(guān)。第第6 6章章 多處理機多處理機512.如果Pj的左部變量在Pi的右部變量集內(nèi)，且當Pi未取用其變量的值之前，不允許被Pj所改變，則稱Pi“數(shù)據(jù)反相關(guān)”于Pj。如Pi C = A * EPj A = B + D在A的值未被Pi取用之前不能被Pj所改變，相當于流水中發(fā)生的“先讀后寫”相關(guān)。3.如果Pi的左部變量也是Pj的左部變量，且Pj存入其算得的值必須在Pi存入之后。則稱Pj“數(shù)據(jù)輸出相關(guān)”于P

26、i。如Pi A = B + DPj A = C + E Pj存入其算得的A值必須在Pi存入其結(jié)果A之后，相當于流水中發(fā)生的“寫寫”相關(guān)。第第6 6章章 多處理機多處理機52對程序并行性的影響表現(xiàn)為下列幾種可能的執(zhí)行次序。1.寫讀串行次序2.讀寫次序3.可并行次序4.必并行次序第第6 6章章 多處理機多處理機531. 寫讀串行次序如果程序必須保持前面的語句先寫，后面的語句后讀的次序，則允許上述任意一種數(shù)據(jù)相關(guān)存在。一般情況下，執(zhí)行的次序不可并行，也不可顛倒。這是通常遇到的典型串行程序。但有一種特殊情況，即當Pi和Pj服從交換律時，雖仍需串行執(zhí)行，但允許Pi和Pj的執(zhí)行次序交換，這稱為可交換串行。

27、如Pi A = 2 * APj A = 3 * A為可交換串行，但Pi A = B + 1Pj B = A + 1就不是可交換串行的。第第6 6章章 多處理機多處理機542. 讀寫次序如果兩個程序段之間只包含第2種數(shù)據(jù)相關(guān)，則只須保持前面的語句先讀，后面的語句后寫的次序，便允許它們既可串行執(zhí)行，也可并行執(zhí)行，但不可交換串行。如Pi A = B + DPj B = C + E二者同時執(zhí)行，能保證Pi先讀B，Pj后寫B(tài)的次序。又如Pi A = 3 * C/BPj B = C * 5Pk C = 7 + E 三者同時執(zhí)行雖屬可能，但由于處理時間上Pi費時最長，Pj次之，Pk最短，如果不采取特別的同步

28、措施，就不能保證必要的先讀后寫次序。第第6 6章章 多處理機多處理機553. 可并行次序如果兩程序段之間不存在任何一種數(shù)據(jù)相關(guān)，即無共同變量，或共同變量僅為右部變量，而不作為左部變量出現(xiàn)，則它們可以無條件地并行執(zhí)行。當然，也可以串行執(zhí)行，而且是可交換串行的。如Pi A = B * CPj D = B + E第第6 6章章 多處理機多處理機564. 必并行次序如果兩程序段的輸入變量互為輸出變量，同時具有“先寫后讀”和“先讀后寫”兩種相關(guān)，以交換數(shù)據(jù)為目的，則二者必須并行執(zhí)行，既不能順序串行，也不能交換串行。如Pi A = BPj B = A兩語句的左右變量互相交換，必須并行執(zhí)行，且需保證讀寫完全

29、同步。第第6 6章章 多處理機多處理機57綜上所述：兩個程序段之間若有先寫后讀的數(shù)據(jù)相關(guān)，不能并行，只在特殊情況下可以交換串行；若有先讀后寫的數(shù)據(jù)反相關(guān)，可以并行執(zhí)行，但必須保證其寫入共享主存時的先讀后寫次序，不能交換串行；若有寫寫的數(shù)據(jù)輸出相關(guān)，可以并行執(zhí)行 但同樣需保證其寫入的先后次序，不能交換串行；若同時有先寫后讀和先讀后寫兩種相關(guān)，以交換數(shù)據(jù)為目的時，則必須并行執(zhí)行，且要求讀寫完全同步，不許順序串行和交換串行；若沒有任何相關(guān)，或僅有右部源數(shù)據(jù)相同時，可以并行、順序串行和交換串行。第第6 6章章 多處理機多處理機586.3.3并行程序設(shè)計語言并行程序設(shè)計語言并行算法需要用并行程序來實現(xiàn)，

30、而編寫并行程序所用的程序語言中需要含有能明確表示并發(fā)進程的成分，這就要使用并行程序設(shè)計語言。并行進程的特點是多個進程在時間上重疊地執(zhí)行，而并行程序設(shè)計語言必須便于具體描述這些并行關(guān)系。 第第6 6章章 多處理機多處理機591.描述程序并行性的語句包含并行性的程序在多處理機上運行時，需要對并行任務(wù)的派生和匯合進行管理。 并行任務(wù)的派生和匯合通常是用軟件手段來控制的。要在程序中反映出并行任務(wù)的派生和匯合關(guān)系，可以在程序語言中使用FORK 語句來派生并行任務(wù)，用JOIN語句來實現(xiàn)對多個并發(fā)任務(wù)的匯合。第第6 6章章 多處理機多處理機60語句格式：FORK m，其中m為一個新進程開始的標號。功能：執(zhí)行

31、一個 FORK m 語句時l繼續(xù)在原分配的處理機上執(zhí)行FORK m 語句的原進程；l派生出標號為m開始的新進程。準備好啟動和繼續(xù)執(zhí)行新進程所必需的有關(guān)信息。若是共享主存，則應(yīng)該產(chǎn)生存儲器指針、映像函數(shù)和訪問權(quán)等信息。l將空閑處理機分配給被FORK語句派生的新進程，如果所有處理機都忙，則讓新進程排隊等待。第第6 6章章 多處理機多處理機61語句格式：JOIN n ，其中n為已派生出的并發(fā)進程個數(shù)。JOIN與FORK語句相配合，作為每個并發(fā)進程的終端語句。功能：JOIN語句附有一個計數(shù)器，其初始值為0。當執(zhí)行JOIN語句時，計數(shù)器加1，并與n比較。l若計數(shù)器值等于n，表明此進程是執(zhí)行中的第n個并發(fā)

32、進程經(jīng)過JOIN語句，則允許該進程通過JOIN語句，將計數(shù)器清0，在其所在的處理機上繼續(xù)執(zhí)行后續(xù)語句。l若計數(shù)器值小于n，表明此進程不是并發(fā)進程中的最后一個，可讓現(xiàn)在執(zhí)行JOIN語句的這個進程先結(jié)束，并把它占用的處理機釋放出來，分配給排隊等待的其他任務(wù)。若無等待任務(wù)，則該處理機空閑。第第6 6章章 多處理機多處理機62給定算術(shù)表達式Z = E + A * B * C/D + F經(jīng)并行編譯得到如下程序： S1 G = A * B S2 H = C/D S3 I = G * H S4 J = E + F S5 Z = I + J如果不加并行控制語句，該程序仍是串行程序，不能發(fā)揮多處理機作用。圖6.

33、19(a)示出了各語句間的數(shù)據(jù)相關(guān)情況。 第第6 6章章 多處理機多處理機63 利用FORK和JOIN語句實現(xiàn)并行任務(wù)派生和匯合，可將程序改寫為： FORK S2 S1G = A * B （進程S1）JOIN 2GOTO S3S2H = C/D （進程S2）JOIN 2S3FORK S4I = G * H （進程S3）JOIN 2GOTO S5S4J = E + F （進程S4）JOIN 2S5Z = I + J （進程S5） 第第6 6章章 多處理機多處理機64 執(zhí)行這個程序可用P1和P2兩個處理機。假定最初的程序在P1上運行，按照FORK語句和JOIN語句對并行任務(wù)的派生和匯合關(guān)系，程序執(zhí)

34、行過程如圖6.19(b)所示。第第6 6章章 多處理機多處理機65 作為FORKJOIN概念的發(fā)展，E.W.Dijkstra提出一種新的塊結(jié)構(gòu)語言。它把所有可并行執(zhí)行的語句或進程S1，S2，Sn用并行語句對cobegincoend（或parbeginparend）括起來，如下程序的執(zhí)行過程如圖所示：beginS0；cobegin S1；S2； Sn；coendSn+1；end第第6 6章章 多處理機多處理機66并行語句也可以嵌套。例如：begin S0； cobegin S1； begin S2； cobegin S3；S4；S5；coend S6； end S7； coend S8；end其

35、程序的執(zhí)行過程如圖6.21所示。第第6 6章章 多處理機多處理機672.并行編譯 實現(xiàn)算術(shù)表達式的并行處理可以應(yīng)用并行算法編制并行程序，還可以依靠并行編譯程序。有一些編譯算法，可以經(jīng)過或不經(jīng)過逆波蘭式，直接從算術(shù)表達式產(chǎn)生能并行執(zhí)行的目標程序。例如，對下列表達式：Z = E + A * B * C/D + F利用普通串行編譯算法，產(chǎn)生三元指令組為 1 *AB2 *1C3 /2D4 +3E5 +4F6 =5Z指令之間均相關(guān)，需5級運算。第第6 6章章 多處理機多處理機68如采用并行編譯算法可得 1 *AB2 /2D3 *124 +EF5 +346 =5Z 其中，1，2為第1級；3，4為第2級；5

36、，6為第3級。分配給兩個處理機，只需3級運算即可實現(xiàn)。第第6 6章章 多處理機多處理機696.3.4 多處理機的操作系統(tǒng)多處理機的操作系統(tǒng)1.多處理機操作系統(tǒng)的功能與特點在多處理機中有多臺實際的處理機，它可以真正實現(xiàn)多個進程的并行執(zhí)行。在多處理機中有多個進程并行執(zhí)行，很可能出現(xiàn)若干個進程同時要求訪問某一共享的資源的情況。在多處理機中有各處理機共享的全局性存儲器，還有每個處理機自己的局部存儲器。多處理機（尤其是松耦合多處理機）表現(xiàn)出任務(wù)、資源和控制上的分布性。 系統(tǒng)的容錯性對多處理機，特別是分布式系統(tǒng)是非常重要的。 第第6 6章章 多處理機多處理機702. 多處理機操作系統(tǒng)的類型主從型，即集中控

37、制方式；單獨管理型，即分布控制方式；浮動管理型，即對稱控制方式。第第6 6章章 多處理機多處理機716.4 多處理機的性能多處理機的性能多處理機系統(tǒng)是程序并行的基礎(chǔ)，使用多處理機的主要目的是用多個處理機并發(fā)執(zhí)行多個任務(wù)來提高解題速度。只有當多處理機系統(tǒng)的并行性能為程序并行帶來較高的性能時才能產(chǎn)生效益，否則只會增加程序的運行成本和復(fù)雜性。因此，多處理機的性能除取決于多處理機系統(tǒng)硬件和軟件的性能之外，在很大程度上取決于程序的并行度。第第6 6章章 多處理機多處理機726.4.1 任務(wù)粒度與系統(tǒng)性能任務(wù)粒度與系統(tǒng)性能 顆粒規(guī)?；蛄６仁呛饬寇浖M程所含計算量的尺度。任務(wù)粒度過小，輔助開銷大，系統(tǒng)效率低

38、；粒度過大，并行度低，性能也不會很高。 如果用R表示程序用于有效計算的時間開銷，C表示處理機間的通信等的輔助時間開銷，則比值R/C就作為衡量任務(wù)粒度大小的依據(jù)。在粗任務(wù)粒度并行情況下，R/C比值較大，計算所需的處理機數(shù)量少；在細任務(wù)粒度并行情況下，R/C比值較小，計算所需的處理機數(shù)量多。用R/C比值能直觀地反映系統(tǒng)的性能，只有R/C比值較大時，開發(fā)并行性才能得到好處。第第6 6章章 多處理機多處理機736.4.2 多處理機性能模型多處理機性能模型現(xiàn)在我們通過幾種不同的多處理機模型來分析R/C的值對系統(tǒng)性能的影響。 1.基本模型2.隨機模型3.通信開銷為線性函數(shù)的模型4.完全重疊通信的模型5.具

39、有多條通信鏈的模型第第6 6章章 多處理機多處理機741.基本模型若某應(yīng)用程序包含M個任務(wù)，在一個由N臺處理機組成的系統(tǒng)上運行。為了簡單起見，我們先討論在一個僅有兩臺處理機的系統(tǒng)上運行的情況，并假設(shè)以下兩個條件是成立的。l每個任務(wù)的計算時間開銷為R，各處理機的執(zhí)行速度相同；l不在同一臺處理機上運行的兩個任務(wù)之間用于通信的額外時間開銷為C，忽略在同一臺處理機上運行的兩個任務(wù)之間的通信開銷。第第6 6章章 多處理機多處理機75 M個任務(wù)在兩臺處理機上有多種分配方法。如果把全部任務(wù)都分配給一臺處理機而另一臺空閑，則通信開銷最小，但沒有并行性。若把K個任務(wù)分配給一臺處理機，把（MK）個任務(wù)分配給另一臺

40、處理機，則系統(tǒng)運行包含M個任務(wù)的應(yīng)用程序所需總的處理時間為： TRmax(MK，K)C(MK)K (6.1)式中第一項為程序用于計算的時間，取兩臺處理機執(zhí)行時間中的大者；第二項為通信產(chǎn)生的額外開銷時間。K稱為任務(wù)分配參數(shù)。 第第6 6章章 多處理機多處理機76由(6.1)式可知，總處理時間是K的函數(shù), 第一項是K的線性函數(shù)，第二項是K的二次函數(shù)。任務(wù)分配應(yīng)使總處理時間最小，分析任務(wù)分配參數(shù)K對處理時間的影響可得：l當K0 時(任務(wù)集中分配給一臺處理機)，執(zhí)行時間最長(為RM)，通信時間最短(為0)，總的處理時間為T1RM；l當KM/2時(任務(wù)平均分配給兩臺處理機) ，執(zhí)行時間最短(為RM/2)

41、，通信時間最長(為CM2/4)，總的處理時間為T2RM/2CM2/4。第第6 6章章 多處理機多處理機77使總處理時間最短的K的最佳值的范圍為：0KM/2。當0KM/2時，max(MK，K)MK，總處理時間為TR(MK)C(MK)K CK2(CMR)KRM (6.2)T與K的關(guān)系曲線為一開口向下的拋物線，如圖6.22所示。第第6 6章章 多處理機多處理機78由圖6.22可見，當K0和KM/2時的總處理時間T較小，而誰是使總處理時間最小的最佳K值則與任務(wù)粒度有關(guān)。設(shè)TT1T2，有TRM(RM/2CM2/4) RM/2CM2/4 (6.3) 對(6.3)式進行討論，并得該模型的結(jié)論：l若T0，得R

42、/CM/2，說明任務(wù)粒度較細。此時T1T2，表示采用集中分配策略(K0)可使總的處理時間最短，為TRM；l若T0，得R/CM/2，說明任務(wù)粒度較粗。此時T1T2，表示采用平均分配策略(KM/2)可使總的處理時間最短，為TRM/2CM2/4。第第6 6章章 多處理機多處理機79 現(xiàn)在，討論包含M個任務(wù)的程序，在一個由N臺處理機組成的系統(tǒng)上運行的情況。仍假設(shè)各處理機的速度相同，每個任務(wù)的執(zhí)行時間均為R，將Ki個任務(wù)分配給第i臺處理機，則N臺處理機執(zhí)行一個包含M個任務(wù)的應(yīng)用程序所需的總處理時間為 (6.4)式中第一項為N臺處理機中最大的計算時間，第二項為不同處理機上的任務(wù)兩兩之間通信的額外時間開銷的

43、總和。這里，假設(shè)處理機的計算時間和通信時間不會重疊，而且所有的任務(wù)間的通信是串行執(zhí)行的。iiiiiiiiiiiKMKKKKKkKCRMCRMCRT2222max2max2max第第6 6章章 多處理機多處理機80與兩臺處理機系統(tǒng)的基本模型類似，N臺處理機系統(tǒng)的基本模型也有一個決定采用平均分配還是采用集中分配的臨界值。設(shè)M為N的倍數(shù)，由(6.4)式可得：l當K0 時(采用集中分配策略)，執(zhí)行時間最長(為RM)，通信時間最短(為0)，總的處理時間為T1RM；l當KM/N時(采用平均分配策略，將M個任務(wù)盡可能平均分配給N臺處理機) ，執(zhí)行時間最短(為RM/N)，通信時間最長(為CM2/2(11/N)

44、，總的處理時間為TNRM/NCM2/2(11/N) 第第6 6章章 多處理機多處理機81 注意，這里的所謂平均，是指如果任務(wù)數(shù)M是處理機數(shù)N的整數(shù)倍，則每臺處理機分得M/N個任務(wù)，否則讓大多數(shù)處理機分得個任務(wù)，一臺處理機分配剩余的不足個任務(wù)，余下的處理機空閑不分配任務(wù)。這樣可減少不必要的通信開銷。例如，有19個任務(wù)和6臺處理機。讓其中4臺處理機各分得個任務(wù)，第5臺處理機分得余下的3個任務(wù)，而第6臺處理機空閑，免去了通信開銷。第第6 6章章 多處理機多處理機82令TT1TN ，有 (6.5)對(6.5)式進行討論，由此得出R/C比值對最佳任務(wù)分配的影響：l若T0，得R/CM/2，細粒度任務(wù)對應(yīng)的

45、R/C比值很小，T1TN表示采用集中分配策略(K0)將任務(wù)集中分配給一臺處理機可使總的處理時間最短，為TRM；l若T0，得R/CM/2，粗粒度任務(wù)對應(yīng)的R/C比值較大，T1TN表示采用平均分配策略(KM/N)將任務(wù)平均分配給所有處理機會使總的處理時間最短，為TRM/NCM2/2(11/N) NCNRMRMTM1122第第6 6章章 多處理機多處理機832. 隨機模型對于N臺處理機系統(tǒng)的隨機模型，假設(shè)各處理機的速度不一定相同，各任務(wù)的執(zhí)行時間也可能不同。執(zhí)行一個包含M個任務(wù)的應(yīng)用程序所需的總處理時間為 (6.6)其中，Ri表示i臺處理機執(zhí)行一個任務(wù)所需的時間，其它參數(shù)的含義與N臺處理機系統(tǒng)的基本

46、模型相同。iiiiiKKKRMCT2max第第6 6章章 多處理機多處理機84 例2.2假設(shè)有兩臺處理機，處理機A的速度是B的兩倍，參考基本性能模型和隨機模型的分析，請問如何分配任務(wù)能達到最優(yōu)性能?解：由于A處理機的速度是B處理機的兩倍，現(xiàn)給B分配K個任務(wù)，每個任務(wù)執(zhí)行的時間為R，則A分配MK個任務(wù)，每個任務(wù)執(zhí)行的時間為R/2，同時設(shè)各對任務(wù)之間的通信開銷為C。參考基本性能模型和隨機模型的系統(tǒng)總處理時間公式，可寫出兩臺處理機執(zhí)行M個任務(wù)的總處理時間為 (6.7)式中第一項為并行執(zhí)行時間，若要使其最小，必須讓兩個處理器的執(zhí)行時間完全相等，即R/2(MK)RK，可得KM/3。KKMCRKKMRT，

47、2max第第6 6章章 多處理機多處理機85分析(6.7)式可得：l當K0時(全部任務(wù)集中分配給速度快的A處理機)，計算時間最長(為RM/2)，通信時間最短(為0)，總處理時間為T1RM/2； l當KM/3時(讓兩個處理機的執(zhí)行時間相等)，計算時間最短(為RM/3)，通信時間為2M2C/9，總處理時間為T2RM/32M2C/9；l當KM/2時(將任務(wù)平均分配給兩個處理機)，計算時間并不是最短(為RM/2)，但通信開銷卻是最大(M2C/4)，故其總處理時間(RM/2M2C/4) 肯定大于T2。第第6 6章章 多處理機多處理機86 由此可知，使總處理時間T最小的K值最佳取值范圍為0KM/3。據(jù)此簡

48、化(6.7)式得 (6.8)2222RMKRMCCKKMCKMRTK第第6 6章章 多處理機多處理機87T與K的關(guān)系曲線為一開口向下的拋物線，如圖6.23所示。其中，圖6.23(a) 表示當K0時T取最小值（圖中M/3也可能大于(2MCR)/(4C)，圖中未標出），圖6.23(b) 表示當KM/3時T取最小值。第第6 6章章 多處理機多處理機88具體K取何值能使總處理時間最短仍與任務(wù)粒度有關(guān)。設(shè)TT1T2，有 (6.9)分析上式并得以下結(jié)論：l若T0，得R/C4M/3，說明任務(wù)粒度較細。此時取K0可使總的處理時間最短，為TRM/2；l若T0，得R/C4M/3，說明任務(wù)粒度較粗。此時取KM/3可

49、使總的處理時間最短，為TRM/32M2C/9。92322CRMRMTM第第6 6章章 多處理機多處理機893. 通信開銷為線性函數(shù)的模型在基本模型中，我們假設(shè)每一對在不同處理機上的任務(wù)之間都要通信，因此通信開銷隨處理機數(shù)目的增加以二次函數(shù)增加。實際上一個任務(wù)要同另一臺處理機上的所有任務(wù)通信，且通信內(nèi)容相同，只需向這臺處理機發(fā)送一次信息就可以了，當信息到達該處理機后，在這臺處理機上各任務(wù)之間的信息傳遞就不必花費通信開銷了。 第第6 6章章 多處理機多處理機90在通信開銷為線性函數(shù)的模型中，就假設(shè)通信開銷與處理機的數(shù)目N成正比，而不是同分配的任務(wù)數(shù)成正比。如果把M個任務(wù)分配給N臺處理機，并假設(shè)M是

50、N的整數(shù)倍，各處理機的速度相同，每個任務(wù)的執(zhí)行時間均為R，則總的處理時間為TRmax(Ki)CN (6.10)式中的第一項與任務(wù)的分配有關(guān)，第二項與任務(wù)的分配無關(guān)。如果把M個任務(wù)平均地分配給N臺處理機，那么第一項等于RM/N，使計算時間最短。總處理時間為T(N)RM/NCN。當N增加時，第二項的增加甚至會超過第一項的減少。所以存在一個最大的N值，這時的性能最佳，這個N值是R/C的函數(shù)。 第第6 6章章 多處理機多處理機91把M個任務(wù)平均地分配給N1臺處理機，則總處理時間為T(N1)RM/(N1)C(N1)對 M個任務(wù)多分配一臺處理機是希望總處理時間減少，即T(N1)T(N)，由此可得出進一步提

51、高并行性的條件為： 或 N (6.11)上式表明，如果分配M個任務(wù)給N臺處理機并行處理，當任務(wù)的R/C比值已達到臨界值N(N1)/M后，總的處理時間不會隨N的增加而減少，反而也會增加。原因是通信開銷的增加超過了提高并行性帶來的好處。式(6.11)的第二種形式直接給出了可使用處理機數(shù)量N的上限。CRMNN1CRM第第6 6章章 多處理機多處理機92 該模型的結(jié)論是：將任務(wù)平均地分配給各臺處理機，且當處理機的數(shù)目 時，總的處理時間最短。 在本模型中，通信開銷隨著N值的增大線性增加，當N超過臨界值時，計算時間的減少將小于通信開銷的增加，這使得系統(tǒng)的整體性能下降。前面的幾種模型告訴我們，在某種情況下，

52、限制并行性反而能獲得高性能，也就是說，使用的處理機數(shù)目并不是越多越好。CRMN 第第6 6章章 多處理機多處理機934. 完全重疊通信的模型 完全重疊通信是指任務(wù)間的通信過程可以完全與任務(wù)的計算過程重疊進行以使額外開銷趨于零。在N臺處理機系統(tǒng)的完全重疊通信模型中，執(zhí)行包含M個任務(wù)的程序所需的總處理時間為iiiiiiiKMKKKKCRMCRT222maxmax2maxmax，第第6 6章章 多處理機多處理機94通信過程與計算過程完全重疊時，計算時間越短，總處理時間也就越短。當任務(wù)平均分配時，即KM/N并帶入式(6.12)，得最短計算時間為 (6.13)通信時間為 (6.14)對于完全重疊通信模型

53、，計算時間等于通信時間，由式(6.13)和(6.14)得 (6.15)NRMRTKimaxNCCMNMMi1122222NCNRMM1122第第6 6章章 多處理機多處理機95 當N值很大時，1/N可忽略，式(6.15)可簡化為 (6.16) 式(6.16)表明，包含M個任務(wù)的程序在N臺處理機上并行處理，若任務(wù)間的通信過程能與計算過程重疊進行，則只有當R/C比值等于或大于MN/2，才能將通信的開銷完全屏蔽，從而使總處理時間最短。式(6.16)的第二種形式直接給出了可使用處理機數(shù)量N的上限，并顯示處理機數(shù)量N的選擇與可提供的任務(wù)數(shù)M成反比。MCRNMNCR22或第第6 6章章 多處理機多處理機9

54、6 若N的值不是很大，則式(6.15)中的1/N不能忽略。如對N2的兩臺處理機完全重疊通信的理想模型，有 (6.17) 簡化上式，得R/CM/2，滿足此關(guān)系時總處理時間最短，為TRM/2。 該模型的結(jié)論是：將任務(wù)平均地分配給各臺處理機，當處理機的數(shù)目N較大且等于2R/(CN) 時，計算時間與通信時間完全重疊，且總的處理時間最短。21122MCRM第第6 6章章 多處理機多處理機975. 具有多條通信鏈的模型如果每臺處理機與其他任何一臺處理機之間都有專用的通信鏈路，而且鏈路和處理機都支持雙向通信。由于一臺處理機在某一時刻只能與另一臺處理機通信，則在一個具有N臺處理機的系統(tǒng)中，通信過程的最大并發(fā)度

55、為N。在這種理想情況下，總的通信開銷可縮短為原來通信過程串行執(zhí)行時的1/N。在此具有多條通信鏈路支持并行通信的模型中，N臺處理機執(zhí)行M個任務(wù)的總處理時間為iiiiKKKMNCRT2max第第6 6章章 多處理機多處理機98設(shè)M為N的倍數(shù)，由式(6.18)可得l當K0時（采用集中分配策略），執(zhí)行時間最長（為RM），通信時間最短（為0）總的處理時間為T1RM；l當N2時，由N臺處理機系統(tǒng)的基本模型可知，盡可能平均分配任務(wù)可以使總處理時間達到最小。故當KM/N時（采用平均分配策略），執(zhí)行時間最短（為RM/N），通信時間最長（CM2/(2N)(11/N)），總處理時間為NNCNRMMTN1122第第6

56、 6章章 多處理機多處理機99 由式(6.19)可看出，當N2時，計算時間和通信時間將隨N的增大而逐漸減少，即N越大，總處理時間TN越短，提高并行性將縮短程序的運行時間。 為了確定任務(wù)粒度與分配策略和系統(tǒng)性能的關(guān)系， 設(shè)TT1TN，有 (6.20)分析(6.20)式可得以下結(jié)論：l若T0，則R/CM/(2N)，說明任務(wù)粒度較細。此時取 K0，采用集中分配策略可使總處理時間最短，為 TRM；l若T0，則R/CM/(2N)，說明任務(wù)粒度較粗。此時取KM/N，采用平均分配策略可使總處理時間最短，為TRM/NCM2/(2N)(11/N)，并且N的值越大(NM)總處理時間越短。NNCNRMRMTM112

57、2第第6 6章章 多處理機多處理機1006.5 MIMD并行機結(jié)構(gòu)模型并行機結(jié)構(gòu)模型6.5.1并行向量處理機并行向量處理機 并行向量處理機的結(jié)構(gòu)如圖6.24所示。它包含功能很強的定制向量處理機、共享存儲器SM模塊和定制的高速縱橫交叉開關(guān)互連網(wǎng)絡(luò)。PVP系統(tǒng)由少數(shù)幾臺巨型向量處理機采用共享存儲器方式互連而成，每個存儲模塊都能提供高速數(shù)據(jù)訪問。這類機器通常不使用Cache，而是使用大量向量寄存器以及指令緩存。第第6 6章章 多處理機多處理機1016.5.2對稱多處理機對稱多處理機 對稱多處理機的結(jié)構(gòu)如圖6.25所示。它由帶有片內(nèi)和片外Cache的處理機經(jīng)總線或交叉開關(guān)網(wǎng)絡(luò)與共享存儲器連接而成。該系

58、統(tǒng)是具有對稱性特點的緊密耦合系統(tǒng)，每個處理機的能力都一樣，并且可以平等地訪問任何共享存儲器模塊、I/O設(shè)備和操作系統(tǒng)服務(wù)，同時可以開發(fā)較高的并行性。所有存儲單元按單一物理地址空間編址。 第第6 6章章 多處理機多處理機1026.5.3大規(guī)模并行處理機大規(guī)模并行處理機 大規(guī)模并行處理機的結(jié)構(gòu)如圖6.26所示。MPP并行機采用了大量的商品化微處理器芯片作為單結(jié)點，每個處理結(jié)點都帶有獨立編址的本地存儲器以及網(wǎng)絡(luò)接口電路(NIC) ，結(jié)點內(nèi)部通過存儲器總線(MB)相連，結(jié)點之間則由NIC通過高性能定制網(wǎng)絡(luò)實現(xiàn)互連。第第6 6章章 多處理機多處理機103分布共享存儲器多處理機的結(jié)構(gòu)如圖6.27所示。它與

59、MPP在結(jié)構(gòu)上的區(qū)別是每個結(jié)點中增加了一個用于支持分布Cache一致性的Cache目錄DIR。所謂分布共享存儲器也稱為共享虛擬存儲器。它是將在物理上分散的各臺處理機所擁有的本地存儲器在邏輯上加以統(tǒng)一編址，形成一個統(tǒng)一的虛擬地址空間來支持存儲器的共享，以實現(xiàn)每臺處理機可以訪問共享虛擬存儲器的任意一個地址。6.5.4分布共享存儲器多處理機分布共享存儲器多處理機第第6 6章章 多處理機多處理機1046.5.5機群系統(tǒng)機群系統(tǒng)機群系統(tǒng)是指利用高速網(wǎng)絡(luò)將一組計算機結(jié)點按某種結(jié)構(gòu)連接起來，并在并行程序設(shè)計以及可視化人機交互集成開發(fā)環(huán)境支持下，統(tǒng)一調(diào)度、協(xié)調(diào)處理，實現(xiàn)高效并行處理的計算機系統(tǒng)。機群系統(tǒng)的結(jié)構(gòu)

60、如圖6.28所示。第第6 6章章 多處理機多處理機105五種MIMD并行機模型的特性 PVPSMPMPPDSMCOW同構(gòu)性MIMDMIMDMIMDMIMDMIMD同步性異步或松同步異步或松同步異步或松同步異步或松同步異步或松同步通信機制共享變量共享變量消息傳遞共享變量消息傳遞地址空間單地址空間單地址空間多地址空間單地址空間多地址空間處理器類型專用定制商用商用商用商用互連網(wǎng)絡(luò)定制的縱橫交叉開關(guān)總線或交叉開關(guān)定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)商品化網(wǎng)絡(luò)（以太網(wǎng)、ATM）系統(tǒng)存儲器集中式共享集中式共享分布式非共享分布式共享分布式非共享代表機器Cray C-90、Fujistu VPP500、銀河2號IBM R50、SUN Ultra En-terprise 1000曙光1號Cray T3E、Inter ASCI Op-tion Red、曙光-1000Stanford DASH、Cray T3DSGI/Cray Origin 2000Berkeley NOW、Alpha Farm、Digital Trucluster模型特性