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

1第第6章章 多處理機(jī)多處理機(jī)6.1 多處理機(jī)的結(jié)構(gòu)與特點(diǎn)多處理機(jī)的結(jié)構(gòu)與特點(diǎn)6.2 多處理機(jī)的多處理機(jī)的Cache一致性一致性6.3 多處理機(jī)的軟件多處理機(jī)的軟件6.4 多處理機(jī)的性能多處理機(jī)的性能6.5 MIMD并行機(jī)結(jié)構(gòu)模型并行機(jī)結(jié)構(gòu)模型第第6 6章章 多處理機(jī)多處理機(jī)2多處理機(jī)具有兩臺(tái)以上處理機(jī)，每臺(tái)處理機(jī)可以帶有本地Cache、本地存儲(chǔ)器、甚至I/O設(shè)備，它們都能獨(dú)立執(zhí)行各自的程序。多臺(tái)處理機(jī)之間通過(guò)總線、縱橫交叉開(kāi)關(guān)、多級(jí)互連網(wǎng)絡(luò)或高速的商品化網(wǎng)絡(luò)實(shí)現(xiàn)互連。多處理機(jī)可以通過(guò)共享存儲(chǔ)器，也可以通過(guò)消息傳送系統(tǒng)來(lái)實(shí)現(xiàn)處理機(jī)間的通信。多臺(tái)處理機(jī)在操作系統(tǒng)的控制下，實(shí)現(xiàn)資源的統(tǒng)一分配與調(diào)度。第第6 6章章 多處理機(jī)多處理機(jī)36.1多處理機(jī)的結(jié)構(gòu)與特點(diǎn)多處理機(jī)的結(jié)構(gòu)與特點(diǎn)6.1.1 多處理機(jī)的結(jié)構(gòu)多處理機(jī)的結(jié)構(gòu)多處理機(jī)在系統(tǒng)結(jié)構(gòu)上可分為兩類：1.緊耦合多處理機(jī)2.松耦合多處理機(jī)第第6 6章章 多處理機(jī)多處理機(jī)41.緊耦合多處理機(jī)緊耦合多處理機(jī)是通過(guò)共享主存來(lái)實(shí)現(xiàn)處理機(jī)間的通信的。各處理機(jī)與主存之間通過(guò)一個(gè)互連網(wǎng)絡(luò)連接。它的典型結(jié)構(gòu)如圖6.1所示。 第第6 6章章 多處理機(jī)多處理機(jī)5在緊耦合多處理機(jī)系統(tǒng)中，為了減少處理機(jī)訪問(wèn)主存的沖突而采取的措施有：v 多處理機(jī)的主存采用多模塊交叉存取。模塊數(shù)越多，發(fā)生訪主存沖突的概率將越低，但必須解決好數(shù)據(jù)在各存儲(chǔ)器模塊中的定位和分配。v 讓每臺(tái)處理機(jī)擁有一個(gè)小容量的本地存儲(chǔ)器，用來(lái)存放頻繁使用的核心代碼等，以減少對(duì)主存的訪問(wèn)。v 讓每臺(tái)處理機(jī)都有一個(gè)Cache，以減少對(duì)主存的訪問(wèn)。但要解決好Cache與主存之間以及各個(gè)Cache之間的數(shù)據(jù)一致性問(wèn)題。第第6 6章章 多處理機(jī)多處理機(jī)6緊耦合多處理機(jī)按所用處理機(jī)類型是否相同可分為同構(gòu)型和異構(gòu)型兩種。而按其對(duì)稱性又可分為對(duì)稱式多處理機(jī)和非對(duì)稱式多處理機(jī)。如果緊耦合多處理機(jī)中的每臺(tái)處理機(jī)在訪問(wèn)任意一個(gè)存儲(chǔ)器模塊或I/O用設(shè)備時(shí)，都具有同等的能力，那么這個(gè)系統(tǒng)就具有對(duì)稱性。反之，表示多處理機(jī)是非對(duì)稱的。一個(gè)多處理機(jī)要成為對(duì)稱式多處理機(jī)必須滿足兩個(gè)條件：首先存儲(chǔ)器必須是集中共享的，其次系統(tǒng)所用的互連網(wǎng)絡(luò)也必須是對(duì)稱的。 第第6 6章章 多處理機(jī)多處理機(jī)7具有非對(duì)稱I/O子系統(tǒng)的多處理機(jī)如圖6.2所示。第第6 6章章 多處理機(jī)多處理機(jī)8采用冗余連接非對(duì)稱I/O子系統(tǒng)的多處理機(jī)如圖6.3所示第第6 6章章 多處理機(jī)多處理機(jī)9 在緊耦合多處理機(jī)中，常見(jiàn)的組合是同構(gòu)對(duì)稱式多處理機(jī)及異構(gòu)非對(duì)稱式多處理機(jī)。 1）同構(gòu)對(duì)稱式多處理機(jī) Sequent公司生產(chǎn)的Balance多處理機(jī)就是同構(gòu)對(duì)稱式的，它的結(jié)構(gòu)如圖6.4所示。 第第6 6章章 多處理機(jī)多處理機(jī)10第第6 6章章 多處理機(jī)多處理機(jī)112）異構(gòu)非對(duì)稱式多處理機(jī)異構(gòu)非對(duì)稱式多處理機(jī)的一般結(jié)構(gòu)如圖6.5所示。 第第6 6章章 多處理機(jī)多處理機(jī)122. 松耦合多處理機(jī)松耦合多處理機(jī)是通過(guò)消息傳送方式來(lái)實(shí)現(xiàn)處理機(jī)間的相互通信的。每臺(tái)處理機(jī)是由一個(gè)獨(dú)立性較強(qiáng)的計(jì)算機(jī)模塊組成，該模塊由處理器、較大容量的本地存儲(chǔ)器（在運(yùn)算時(shí)所需的絕大部分的指令和數(shù)據(jù)均取自本地存儲(chǔ)器）、I/O設(shè)備以及網(wǎng)絡(luò)接口電路組成。各模塊之間通過(guò)消息傳送系統(tǒng)(MTS)相連接。當(dāng)不同模塊上運(yùn)行的進(jìn)程間需要通信時(shí)，通過(guò)網(wǎng)絡(luò)接口電路及消息傳送系統(tǒng)進(jìn)行信息交換。由于這種相互間的耦合程度是很松散的，因此稱之為松耦合多處理機(jī)。 第第6 6章章 多處理機(jī)多處理機(jī)13松耦合多處理機(jī)可分為層次式和非層次式兩種結(jié)構(gòu)。1）松耦合非層次式多處理機(jī)圖6.6所示是一個(gè)典型的通過(guò)消息傳送系統(tǒng)進(jìn)行互連的松耦合非層次式多處理機(jī)。 第第6 6章章 多處理機(jī)多處理機(jī)142）松耦合層次式多處理機(jī)松耦合層次式多處理機(jī)采用多級(jí)總線實(shí)現(xiàn)層次連接。圖6.7所示為卡內(nèi)基梅隆大學(xué)研制的Cm* 松耦合層次式多處理機(jī)。 第第6 6章章 多處理機(jī)多處理機(jī)156.1.2 多處理機(jī)的特點(diǎn)多處理機(jī)的特點(diǎn)1.靈活性和通用性強(qiáng) 2.高層次的并行性等級(jí) 3.并行任務(wù)派生 4.進(jìn)程同步 5.資源分配和任務(wù)調(diào)度 第第6 6章章 多處理機(jī)多處理機(jī)166.2 多處理機(jī)的多處理機(jī)的Cache一致性一致性Cache作為提高系統(tǒng)性能的一種技術(shù)手段在計(jì)算機(jī)系統(tǒng)中得到普遍的使用。在共享存儲(chǔ)器的多處理機(jī)中，每臺(tái)處理機(jī)都有自己的局部Cache。這類多處理機(jī)在運(yùn)行一個(gè)具有多個(gè)進(jìn)程的程序時(shí)，各處理機(jī)可能會(huì)使用到共享存儲(chǔ)器中的同一數(shù)據(jù)塊，為維持多處理機(jī)的高速運(yùn)行，這些共享數(shù)據(jù)塊將被調(diào)入各處理機(jī)的局部Cache中。由于多個(gè)處理機(jī)是異步地獨(dú)立操作，可能使共享存儲(chǔ)器中同一數(shù)據(jù)塊的不同Cache拷貝出現(xiàn)不一致，就可能危及系統(tǒng)的正常運(yùn)行，這就是Cache的一致性問(wèn)題。第第6 6章章 多處理機(jī)多處理機(jī)176.2.1 出現(xiàn)出現(xiàn)Cache一致性問(wèn)題的原因一致性問(wèn)題的原因出現(xiàn)Cache一致性問(wèn)題的原因主要有3個(gè)：1.共享可寫的數(shù)據(jù)2.進(jìn)程遷移3.I/O傳輸?shù)诘? 6章章 多處理機(jī)多處理機(jī)181共享可寫數(shù)據(jù)引起的不一致 假設(shè)在寫操作之前，Cache的初始狀態(tài)如圖6.8(a)所示。處理機(jī)P1和P2的局部高速緩沖存儲(chǔ)器Cache1和Cache2中分別有共享存儲(chǔ)器的某個(gè)數(shù)據(jù)x的副本。第第6 6章章 多處理機(jī)多處理機(jī)19 若采用寫直達(dá)法，如圖6.8(b)所示，當(dāng)處理機(jī)P1改寫Cache1中的數(shù)據(jù)為x時(shí)，共享存儲(chǔ)器中的相應(yīng)數(shù)據(jù)也立即更新為x，這將導(dǎo)致Cache1中的數(shù)據(jù)與Cache2中所緩存的數(shù)據(jù)不一致。第第6 6章章 多處理機(jī)多處理機(jī)20 若采用寫回法，如圖6.8(c)所示，當(dāng)處理機(jī)P1改寫Cache1中的數(shù)據(jù)為x時(shí)，Cache1的變化不會(huì)引起Cache2和共享存儲(chǔ)器的變化，這將導(dǎo)致Cache1中的數(shù)據(jù)與共享存儲(chǔ)器和Cache2中所緩存的數(shù)據(jù)不一致。第第6 6章章 多處理機(jī)多處理機(jī)212進(jìn)程遷移引起的不一致 在多處理機(jī)上，有時(shí)為了提高系統(tǒng)的效率而允許進(jìn)程遷移，將一個(gè)尚未執(zhí)行完而被掛起的進(jìn)程調(diào)度到另一個(gè)空閑的處理機(jī)上去執(zhí)行，使系統(tǒng)中各處理機(jī)的負(fù)荷保持均衡。但這樣做可能會(huì)造成Cache一致性問(wèn)題。 假設(shè)在遷移前Cache的初始狀態(tài)仍如圖6.9(a)所示，處理機(jī)P1的Cache1中有共享存儲(chǔ)器中數(shù)據(jù)x的拷貝，而處理機(jī)P2的Cache2中沒(méi)有該數(shù)據(jù)。第第6 6章章 多處理機(jī)多處理機(jī)22 若采用寫直達(dá)法，如圖6.9(b)所示，當(dāng)某進(jìn)程從P1遷移到P2后，處理機(jī)P2在執(zhí)行此進(jìn)程時(shí)需要使用數(shù)據(jù)x時(shí)，會(huì)將x所在塊由共享存儲(chǔ)器調(diào)入Cache2。假設(shè)進(jìn)程運(yùn)行時(shí)將Cache2的數(shù)據(jù)x改寫為x，在共享存儲(chǔ)器中的相應(yīng)數(shù)據(jù)也立即更新為x，這將導(dǎo)致共享存儲(chǔ)器和Cache2中的數(shù)據(jù)與處理機(jī)P1中Cache1所緩存的數(shù)據(jù)的不一致。第第6 6章章 多處理機(jī)多處理機(jī)23 若采用寫回法，如圖6.9(c)所示，當(dāng)處理機(jī)P1修改Cache1中的數(shù)據(jù)成x時(shí)Cache1的變化不會(huì)引起共享存儲(chǔ)器的變化。當(dāng)某進(jìn)程從P1遷移到P2后，處理機(jī)P2在執(zhí)行此進(jìn)程時(shí)需要使用數(shù)據(jù)x時(shí)，會(huì)將x所在塊由共享存儲(chǔ)器調(diào)入Cache2。此時(shí)調(diào)入的數(shù)據(jù)x并非是已經(jīng)修改過(guò)的x，這將導(dǎo)致共享存儲(chǔ)器及Cache2與處理機(jī)P1中Cache1所緩存的數(shù)據(jù)的不一致。第第6 6章章 多處理機(jī)多處理機(jī)243I/O操作引起的不一致 假設(shè)在執(zhí)行I/O操作之前，Cache的初始狀態(tài)如圖6.10(a)所示。處理機(jī)P1和P2的局部Cache中分別有共享存儲(chǔ)器的某個(gè)數(shù)據(jù)x的拷貝。 第第6 6章章 多處理機(jī)多處理機(jī)25 若采用寫直達(dá)法，當(dāng)I/O處理機(jī)執(zhí)行輸入操作，直接將共享存儲(chǔ)器中的數(shù)據(jù)x改寫成x時(shí)，將導(dǎo)致Cache1和Cache2中的數(shù)據(jù)與共享存儲(chǔ)器數(shù)據(jù)的不一致，如圖6.10(b)所示。第第6 6章章 多處理機(jī)多處理機(jī)26 若采用寫回法，當(dāng)處理機(jī)P1將Cache1中的數(shù)據(jù)x改寫為x時(shí)，由于Cache1數(shù)據(jù)的修改不會(huì)立即引起共享存儲(chǔ)器中數(shù)據(jù)x的更新，此時(shí)若此數(shù)據(jù)恰好被I/O處理機(jī)輸出，就會(huì)造成輸出錯(cuò)誤，如圖6.10(c)所示。第第6 6章章 多處理機(jī)多處理機(jī)27 解決多處理器維護(hù)Cache一致性的協(xié)議稱為Cache一致性協(xié)議。實(shí)現(xiàn)Cache一致性協(xié)議的關(guān)鍵是跟蹤共享數(shù)據(jù)塊的狀態(tài)。目前有兩類協(xié)議，它們采用了不同的共享數(shù)據(jù)狀態(tài)跟蹤技術(shù)，分別適合于不同的系統(tǒng)結(jié)構(gòu)。 （1）監(jiān)聽(tīng)：每個(gè)Cache除了包含物理存儲(chǔ)器中塊的數(shù)據(jù)拷貝之外，也保存著各個(gè)塊的共享狀態(tài)信息。這是一種基于總線的一致性協(xié)議，各處理機(jī)通過(guò)監(jiān)聽(tīng)總線上處理機(jī)與存儲(chǔ)器之間的Cache操作事件，對(duì)各自局部Cache中的數(shù)據(jù)采取保持一致性的措施。 （2）目錄：物理存儲(chǔ)器中共享數(shù)據(jù)塊的狀態(tài)及相關(guān)信息均被保存在一個(gè)稱為目錄的地方。共享數(shù)據(jù)塊的變化通過(guò)此數(shù)據(jù)塊所在的各目錄項(xiàng)，將一致性命令發(fā)給所有存放該數(shù)據(jù)塊拷貝的Cache。第第6 6章章 多處理機(jī)多處理機(jī)286.2.2 監(jiān)聽(tīng)一致性協(xié)議監(jiān)聽(tīng)一致性協(xié)議 在基于總線互連結(jié)構(gòu)的系統(tǒng)中，各處理機(jī)的Cache都連接到公共總線。一般都采用監(jiān)聽(tīng)協(xié)議，通過(guò)總線監(jiān)聽(tīng)機(jī)制實(shí)現(xiàn)高速緩存和共享存儲(chǔ)器之間的數(shù)據(jù)一致性。監(jiān)聽(tīng)協(xié)議有兩種策略來(lái)保持Cache一致性：1.寫無(wú)效策略2.寫更新策略第第6 6章章 多處理機(jī)多處理機(jī)291. 寫無(wú)效策略 寫無(wú)效策略是指在某局部Cache數(shù)據(jù)被修改后，使所有其它Cache中的相應(yīng)數(shù)據(jù)拷貝都無(wú)效。 假設(shè)在寫操作之前，Cache的初始狀態(tài)如圖6.11(a)所示。處理機(jī)P1和P2的局部Cache中都存有共享存儲(chǔ)器中數(shù)據(jù)x的拷貝，圖中數(shù)據(jù)x加虛線框表示數(shù)據(jù)x所在的數(shù)據(jù)塊。 當(dāng)處理機(jī)P1要進(jìn)行寫操作時(shí)，它必須首先獲得對(duì)x的唯一訪問(wèn)權(quán)， 然后更新數(shù)據(jù)為x并使Cache2中的相應(yīng)數(shù)據(jù)塊拷貝失效（標(biāo)志為I）。第第6 6章章 多處理機(jī)多處理機(jī)30 若采用寫直達(dá)法，則共享存儲(chǔ)器中的數(shù)據(jù)x將會(huì)立即更新為x，如圖6.11(b)所示。當(dāng)處理機(jī)P2訪問(wèn)已修改的數(shù)據(jù)x時(shí)，會(huì)發(fā)生Cache2失效并從共享存儲(chǔ)器中讀取新值x，同時(shí)將x所在數(shù)據(jù)塊調(diào)入Cache2。第第6 6章章 多處理機(jī)多處理機(jī)31 若采用寫回法，則共享存儲(chǔ)器中數(shù)據(jù)x所在的數(shù)據(jù)塊也將被設(shè)置為無(wú)效，如圖6.11(c)所示。當(dāng)處理機(jī)P2訪問(wèn)已修改的數(shù)據(jù)x時(shí)，會(huì)發(fā)生Cache2失效并從處理機(jī)P1的Cache1讀取新值x，同時(shí)將x所在數(shù)據(jù)塊調(diào)入Cache2并且更新共享存儲(chǔ)器中的相應(yīng)數(shù)據(jù)塊。第第6 6章章 多處理機(jī)多處理機(jī)322.寫更新策略 寫更新策略是指在某局部Cache數(shù)據(jù)被修改后，通過(guò)總線廣播修改后的數(shù)據(jù)使所有含有相應(yīng)數(shù)據(jù)拷貝的其他Cache進(jìn)行更新。 假設(shè)在寫操作之前，Cache的初始狀態(tài)如圖6.12(a)所示。處理機(jī)P1和P2的局部Cache中都存有共享存儲(chǔ)器中數(shù)據(jù)x的拷貝。第第6 6章章 多處理機(jī)多處理機(jī)33 若采用寫直達(dá)法，則共享存儲(chǔ)器中數(shù)據(jù)x所在的數(shù)據(jù)塊將會(huì)立即更新，如圖6.12(b)所示。若采用寫回法，則共享存儲(chǔ)器中數(shù)據(jù)x所在的數(shù)據(jù)塊將會(huì)被設(shè)置為無(wú)效，如圖6.12(c)所示。第第6 6章章 多處理機(jī)多處理機(jī)34寫更新和寫無(wú)效策略性能上的差別來(lái)自三個(gè)方面：對(duì)同一數(shù)據(jù)的多個(gè)寫而中間無(wú)讀操作的情況，寫更新策略需進(jìn)行多次寫廣播操作，而在寫無(wú)效策略下只需一次置無(wú)效操作。對(duì)同一塊中多個(gè)字進(jìn)行寫操作，寫更新策略對(duì)每個(gè)字的寫均要進(jìn)行一次廣播，而在寫無(wú)效策略下僅在對(duì)該塊第一次寫時(shí)進(jìn)行置無(wú)效操作即可。寫無(wú)效是針對(duì)Cache塊進(jìn)行操作，而寫更新則是針對(duì)字（或字節(jié)）進(jìn)行操作。從一個(gè)處理機(jī)寫到另一個(gè)處理機(jī)讀之間的延遲通常在寫更新模式中較低，因?yàn)樗鼘憯?shù)據(jù)時(shí)馬上更新了相應(yīng)的其他Cache中的內(nèi)容（假設(shè)讀的處理器Cache中有此數(shù)據(jù)）。而在寫無(wú)效策略中，需要讀一個(gè)新的拷貝。第第6 6章章 多處理機(jī)多處理機(jī)356.2.3 基于目錄的協(xié)議基于目錄的協(xié)議 在監(jiān)聽(tīng)協(xié)議中，每當(dāng)Cache被修改時(shí)，要與所有的Cache進(jìn)行通信，包括對(duì)于可能共享的數(shù)據(jù)的寫操作，這可能導(dǎo)致總線的流量大大增加。 基于目錄的協(xié)議的基本思想是：使用Cache目錄來(lái)記錄可以進(jìn)入Cache的每個(gè)數(shù)據(jù)塊的訪問(wèn)狀態(tài)、該塊在各個(gè)處理機(jī)的共享狀態(tài)以及是否修改過(guò)等信息。把一致性命令只發(fā)給存有相應(yīng)數(shù)據(jù)塊拷貝的Cache，從而支持Cache的一致性。各種目錄協(xié)議的主要差別是目錄存放什么信息以及如何維護(hù)信息。 第第6 6章章 多處理機(jī)多處理機(jī)36根據(jù)目錄的結(jié)構(gòu)特點(diǎn)，基于目錄的協(xié)議可分為三類：1.全映射目錄（full-map directory）2.有限目錄（limited directory）3.鏈?zhǔn)侥夸洠╟hained directory） 第第6 6章章 多處理機(jī)多處理機(jī)371. 全映射目錄協(xié)議 全映射目錄協(xié)議規(guī)定共享存儲(chǔ)器中的每個(gè)數(shù)據(jù)塊都有一個(gè)目錄項(xiàng)，每個(gè)目錄項(xiàng)中有N個(gè)處理機(jī)位和一個(gè)重寫位，其中N為處理機(jī)的臺(tái)數(shù)，目錄項(xiàng)結(jié)構(gòu)如圖6.13所示。 第第6 6章章 多處理機(jī)多處理機(jī)38 下面以三個(gè)處理機(jī)的系統(tǒng)為例，說(shuō)明全映射目錄的三種狀態(tài)以及全映射目錄協(xié)議保持Cache一致性的原理。 （1）處理機(jī)Cache中沒(méi)有包含單元x的數(shù)據(jù)塊副本 全映射目錄的第一種狀態(tài)。此時(shí)，包含單元x的數(shù)據(jù)塊Bd目錄項(xiàng)中的三個(gè)處理機(jī)位均為“0”，表示整個(gè)系統(tǒng)所有Cache中都沒(méi)有數(shù)據(jù)塊Bd的副本；重寫位為未寫(C)狀態(tài)，表示沒(méi)有一臺(tái)處理機(jī)允許寫入該數(shù)據(jù)塊。第第6 6章章 多處理機(jī)多處理機(jī)39（2）處理機(jī)從共享存儲(chǔ)器讀入數(shù)據(jù)塊到Cache 當(dāng)三臺(tái)處理機(jī)都有過(guò)讀x的請(qǐng)求之后，全映射目錄出現(xiàn)第二種狀態(tài)。目錄項(xiàng)中的三個(gè)處理機(jī)位被置“1”，表示這些Cache中已有數(shù)據(jù)塊Bd的拷貝；重寫位仍為未寫狀態(tài)，不允許處理機(jī)寫Cache塊Bd。此時(shí)，三個(gè)Cache中Bd的Cache塊狀態(tài)位均為有效位1，允許寫位0，與Cache目錄的狀態(tài)位一致。第第6 6章章 多處理機(jī)多處理機(jī)40（3）處理機(jī)寫Cache塊 如果處理機(jī)P3向Cache3發(fā)出寫x（或Bd中其它單元）的請(qǐng)求，全映射目錄將從第二種狀態(tài)轉(zhuǎn)換到第三種狀態(tài)，此時(shí)的Cache全映射目錄呈現(xiàn)第三種狀態(tài)。目錄項(xiàng)中Cache1和Cache2的處理機(jī)位被置“0”，表示這些Cache中數(shù)據(jù)塊Bd的拷貝已失效；Cache3的處理機(jī)位為“1”，同時(shí)重寫位為重寫狀態(tài)，表示允許處理機(jī)P3寫Cache塊Bd，且Cache3中的Bd塊已被修改為Bd。第第6 6章章 多處理機(jī)多處理機(jī)412. 有限目錄協(xié)議 有限目錄協(xié)議與全映射目錄協(xié)議十分相似，都有一位重寫位，但有限目錄的目錄項(xiàng)中的指針（處理機(jī)位）實(shí)際上是數(shù)目固定的若干個(gè)處理機(jī)編號(hào)。若共有N臺(tái)處理機(jī)，則每個(gè)處理機(jī)指針為log2N位。有I個(gè)指針域的目錄項(xiàng)最多只能允許該數(shù)據(jù)塊裝入I個(gè)Cache中，有限目錄協(xié)議使用IN個(gè)指針，可以緩解目錄過(guò)大的問(wèn)題。 第第6 6章章 多處理機(jī)多處理機(jī)42 如圖6.15所示，假設(shè)多處理機(jī)系統(tǒng)中共有三臺(tái)處理機(jī)，目錄項(xiàng)中只有兩個(gè)指針域。當(dāng)P1和P2的Cache中都有單元x所在數(shù)據(jù)塊Bd的拷貝時(shí)，該數(shù)據(jù)塊對(duì)應(yīng)的目錄項(xiàng)中的兩個(gè)指針?lè)謩e指向處理機(jī)P1和P2。 第第6 6章章 多處理機(jī)多處理機(jī)433. 鏈?zhǔn)侥夸泤f(xié)議 鏈?zhǔn)侥夸浲ㄟ^(guò)將目錄信息分布到多個(gè)小規(guī)模的本地目錄中來(lái)模擬全映射機(jī)制。其主要思想是通過(guò)維護(hù)一個(gè)目錄指針鏈來(lái)跟蹤共享數(shù)據(jù)塊的拷貝。要想得到某個(gè)數(shù)據(jù)塊在所有Cache中的共享情況，必須搜索整個(gè)Cache目錄鏈。鏈?zhǔn)侥夸浀膬?yōu)點(diǎn)在于既不限制共享數(shù)據(jù)塊的拷貝數(shù)目，又保持了可擴(kuò)展性。鏈?zhǔn)侥夸浻袃煞N實(shí)現(xiàn)方法，單向鏈和雙向鏈。若采用比較簡(jiǎn)單的單向鏈，則目錄項(xiàng)中除一位重寫位之外，只需要一個(gè)指針域。第第6 6章章 多處理機(jī)多處理機(jī)44采用單向鏈的鏈?zhǔn)侥夸浫鐖D6.16所示。 第第6 6章章 多處理機(jī)多處理機(jī)456.3 多處理機(jī)的軟件多處理機(jī)的軟件6.3.1并行算法并行算法算法對(duì)于并行性的開(kāi)發(fā)至關(guān)重要。算法必須適應(yīng)具體的計(jì)算機(jī)結(jié)構(gòu)。對(duì)表達(dá)式E1abxcx2dx3 ，順序算法與并行算法比較如圖6.17所示。將運(yùn)算過(guò)程用樹(shù)形流程圖來(lái)表示的方法。運(yùn)算的級(jí)數(shù)就是樹(shù)的高度，用Tp代表；P為所需處理機(jī)數(shù)目；Sp為加速比，SpTl/Tp；Ep為效率，EpSp/P 第第6 6章章 多處理機(jī)多處理機(jī)46 對(duì)樹(shù)進(jìn)行變換來(lái)降低樹(shù)高，減少運(yùn)算級(jí)數(shù)，即可提高運(yùn)算的并行性。樹(shù)形結(jié)構(gòu)可以用交換律、結(jié)合律、分配律來(lái)變換。 先從算術(shù)表達(dá)式的最直接形式出發(fā)，利用交換律把相同的運(yùn)算集中在一起；再利用結(jié)合律把參加運(yùn)算的操作數(shù)（稱原子）配對(duì)，盡可能并行運(yùn)算，組成樹(shù)高最小的子樹(shù)；最后利用分配律，平衡各分支運(yùn)算的級(jí)數(shù)，把這些子樹(shù)結(jié)合起來(lái)，使總級(jí)數(shù)減至最少。 第第6 6章章 多處理機(jī)多處理機(jī)47 例如：某表達(dá)式E2ab(cdefg)h，需7級(jí)運(yùn)算，如圖6.18(a)所示。利用交換律和結(jié)合律改寫為E2(ah)b(cg)def ，則需5級(jí)運(yùn)算，如圖6.18(b)所示。 第第6 6章章 多處理機(jī)多處理機(jī)48再利用分配律，將上式改寫為E2(ah)(bcbg)bdef則用3個(gè)處理機(jī)，僅需4級(jí)運(yùn)算。如圖6.18(c)所示。 第第6 6章章 多處理機(jī)多處理機(jī)496.3.2 程序并行性分析程序并行性分析除算法以外，任務(wù)間能否并行在很大程度還取決于程序的結(jié)構(gòu)形式。假設(shè)一個(gè)程序包含P1、P2、Pi、Pj、Pn等n個(gè)程序段，其書(shū)寫的順序反映了該程序正常執(zhí)行的順序。為了便于分析，設(shè)Pi和Pj程序段都是一條語(yǔ)句，Pi在Pj之前執(zhí)行，且只討論P(yáng)i和Pj之間的直接數(shù)據(jù)相關(guān)關(guān)系。第第6 6章章 多處理機(jī)多處理機(jī)50程序段之間會(huì)出現(xiàn)類似的3種數(shù)據(jù)相關(guān)。1.如果Pi的左部變量在Pj的右部變量集內(nèi)，且Pj要從Pi取得運(yùn)算結(jié)果來(lái)作為操作數(shù)，則稱Pj“數(shù)據(jù)相關(guān)”于Pi。如Pi A = B + DPj C = A * EPj必須取Pi算得的A值作為操作數(shù)，相當(dāng)于流水中發(fā)生的“先寫后讀”相關(guān)。第第6 6章章 多處理機(jī)多處理機(jī)512.如果Pj的左部變量在Pi的右部變量集內(nèi)，且當(dāng)Pi未取用其變量的值之前，不允許被Pj所改變，則稱Pi“數(shù)據(jù)反相關(guān)”于Pj。如Pi C = A * EPj A = B + D在A的值未被Pi取用之前不能被Pj所改變，相當(dāng)于流水中發(fā)生的“先讀后寫”相關(guān)。3.如果Pi的左部變量也是Pj的左部變量，且Pj存入其算得的值必須在Pi存入之后。則稱Pj“數(shù)據(jù)輸出相關(guān)”于Pi。如Pi A = B + DPj A = C + E Pj存入其算得的A值必須在Pi存入其結(jié)果A之后，相當(dāng)于流水中發(fā)生的“寫寫”相關(guān)。第第6 6章章 多處理機(jī)多處理機(jī)52對(duì)程序并行性的影響表現(xiàn)為下列幾種可能的執(zhí)行次序。1.寫讀串行次序2.讀寫次序3.可并行次序4.必并行次序第第6 6章章 多處理機(jī)多處理機(jī)531. 寫讀串行次序如果程序必須保持前面的語(yǔ)句先寫，后面的語(yǔ)句后讀的次序，則允許上述任意一種數(shù)據(jù)相關(guān)存在。一般情況下，執(zhí)行的次序不可并行，也不可顛倒。這是通常遇到的典型串行程序。但有一種特殊情況，即當(dāng)Pi和Pj服從交換律時(shí)，雖仍需串行執(zhí)行，但允許Pi和Pj的執(zhí)行次序交換，這稱為可交換串行。如Pi A = 2 * APj A = 3 * A為可交換串行，但Pi A = B + 1Pj B = A + 1就不是可交換串行的。第第6 6章章 多處理機(jī)多處理機(jī)542. 讀寫次序如果兩個(gè)程序段之間只包含第2種數(shù)據(jù)相關(guān)，則只須保持前面的語(yǔ)句先讀，后面的語(yǔ)句后寫的次序，便允許它們既可串行執(zhí)行，也可并行執(zhí)行，但不可交換串行。如Pi A = B + DPj B = C + E二者同時(shí)執(zhí)行，能保證Pi先讀B，Pj后寫B(tài)的次序。又如Pi A = 3 * C/BPj B = C * 5Pk C = 7 + E 三者同時(shí)執(zhí)行雖屬可能，但由于處理時(shí)間上Pi費(fèi)時(shí)最長(zhǎng)，Pj次之，Pk最短，如果不采取特別的同步措施，就不能保證必要的先讀后寫次序。第第6 6章章 多處理機(jī)多處理機(jī)553. 可并行次序如果兩程序段之間不存在任何一種數(shù)據(jù)相關(guān)，即無(wú)共同變量，或共同變量?jī)H為右部變量，而不作為左部變量出現(xiàn)，則它們可以無(wú)條件地并行執(zhí)行。當(dāng)然，也可以串行執(zhí)行，而且是可交換串行的。如Pi A = B * CPj D = B + E第第6 6章章 多處理機(jī)多處理機(jī)564. 必并行次序如果兩程序段的輸入變量互為輸出變量，同時(shí)具有“先寫后讀”和“先讀后寫”兩種相關(guān)，以交換數(shù)據(jù)為目的，則二者必須并行執(zhí)行，既不能順序串行，也不能交換串行。如Pi A = BPj B = A兩語(yǔ)句的左右變量互相交換，必須并行執(zhí)行，且需保證讀寫完全同步。第第6 6章章 多處理機(jī)多處理機(jī)57綜上所述：兩個(gè)程序段之間若有先寫后讀的數(shù)據(jù)相關(guān)，不能并行，只在特殊情況下可以交換串行；若有先讀后寫的數(shù)據(jù)反相關(guān)，可以并行執(zhí)行，但必須保證其寫入共享主存時(shí)的先讀后寫次序，不能交換串行；若有寫寫的數(shù)據(jù)輸出相關(guān)，可以并行執(zhí)行 但同樣需保證其寫入的先后次序，不能交換串行；若同時(shí)有先寫后讀和先讀后寫兩種相關(guān)，以交換數(shù)據(jù)為目的時(shí)，則必須并行執(zhí)行，且要求讀寫完全同步，不許順序串行和交換串行；若沒(méi)有任何相關(guān)，或僅有右部源數(shù)據(jù)相同時(shí)，可以并行、順序串行和交換串行。第第6 6章章 多處理機(jī)多處理機(jī)586.3.3并行程序設(shè)計(jì)語(yǔ)言并行程序設(shè)計(jì)語(yǔ)言并行算法需要用并行程序來(lái)實(shí)現(xiàn)，而編寫并行程序所用的程序語(yǔ)言中需要含有能明確表示并發(fā)進(jìn)程的成分，這就要使用并行程序設(shè)計(jì)語(yǔ)言。并行進(jìn)程的特點(diǎn)是多個(gè)進(jìn)程在時(shí)間上重疊地執(zhí)行，而并行程序設(shè)計(jì)語(yǔ)言必須便于具體描述這些并行關(guān)系。 第第6 6章章 多處理機(jī)多處理機(jī)591.描述程序并行性的語(yǔ)句包含并行性的程序在多處理機(jī)上運(yùn)行時(shí)，需要對(duì)并行任務(wù)的派生和匯合進(jìn)行管理。 并行任務(wù)的派生和匯合通常是用軟件手段來(lái)控制的。要在程序中反映出并行任務(wù)的派生和匯合關(guān)系，可以在程序語(yǔ)言中使用FORK 語(yǔ)句來(lái)派生并行任務(wù)，用JOIN語(yǔ)句來(lái)實(shí)現(xiàn)對(duì)多個(gè)并發(fā)任務(wù)的匯合。第第6 6章章 多處理機(jī)多處理機(jī)60語(yǔ)句格式：FORK m，其中m為一個(gè)新進(jìn)程開(kāi)始的標(biāo)號(hào)。功能：執(zhí)行一個(gè) FORK m 語(yǔ)句時(shí)l繼續(xù)在原分配的處理機(jī)上執(zhí)行FORK m 語(yǔ)句的原進(jìn)程；l派生出標(biāo)號(hào)為m開(kāi)始的新進(jìn)程。準(zhǔn)備好啟動(dòng)和繼續(xù)執(zhí)行新進(jìn)程所必需的有關(guān)信息。若是共享主存，則應(yīng)該產(chǎn)生存儲(chǔ)器指針、映像函數(shù)和訪問(wèn)權(quán)等信息。l將空閑處理機(jī)分配給被FORK語(yǔ)句派生的新進(jìn)程，如果所有處理機(jī)都忙，則讓新進(jìn)程排隊(duì)等待。第第6 6章章 多處理機(jī)多處理機(jī)61語(yǔ)句格式：JOIN n ，其中n為已派生出的并發(fā)進(jìn)程個(gè)數(shù)。JOIN與FORK語(yǔ)句相配合，作為每個(gè)并發(fā)進(jìn)程的終端語(yǔ)句。功能：JOIN語(yǔ)句附有一個(gè)計(jì)數(shù)器，其初始值為0。當(dāng)執(zhí)行JOIN語(yǔ)句時(shí)，計(jì)數(shù)器加1，并與n比較。l若計(jì)數(shù)器值等于n，表明此進(jìn)程是執(zhí)行中的第n個(gè)并發(fā)進(jìn)程經(jīng)過(guò)JOIN語(yǔ)句，則允許該進(jìn)程通過(guò)JOIN語(yǔ)句，將計(jì)數(shù)器清0，在其所在的處理機(jī)上繼續(xù)執(zhí)行后續(xù)語(yǔ)句。l若計(jì)數(shù)器值小于n，表明此進(jìn)程不是并發(fā)進(jìn)程中的最后一個(gè)，可讓現(xiàn)在執(zhí)行JOIN語(yǔ)句的這個(gè)進(jìn)程先結(jié)束，并把它占用的處理機(jī)釋放出來(lái)，分配給排隊(duì)等待的其他任務(wù)。若無(wú)等待任務(wù)，則該處理機(jī)空閑。第第6 6章章 多處理機(jī)多處理機(jī)62給定算術(shù)表達(dá)式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如果不加并行控制語(yǔ)句，該程序仍是串行程序，不能發(fā)揮多處理機(jī)作用。圖6.19(a)示出了各語(yǔ)句間的數(shù)據(jù)相關(guān)情況。 第第6 6章章 多處理機(jī)多處理機(jī)63 利用FORK和JOIN語(yǔ)句實(shí)現(xiàn)并行任務(wù)派生和匯合，可將程序改寫為： FORK S2 S1G = A * B （進(jìn)程S1）JOIN 2GOTO S3S2H = C/D （進(jìn)程S2）JOIN 2S3FORK S4I = G * H （進(jìn)程S3）JOIN 2GOTO S5S4J = E + F （進(jìn)程S4）JOIN 2S5Z = I + J （進(jìn)程S5） 第第6 6章章 多處理機(jī)多處理機(jī)64 執(zhí)行這個(gè)程序可用P1和P2兩個(gè)處理機(jī)。假定最初的程序在P1上運(yùn)行，按照FORK語(yǔ)句和JOIN語(yǔ)句對(duì)并行任務(wù)的派生和匯合關(guān)系，程序執(zhí)行過(guò)程如圖6.19(b)所示。第第6 6章章 多處理機(jī)多處理機(jī)65 作為FORKJOIN概念的發(fā)展，E.W.Dijkstra提出一種新的塊結(jié)構(gòu)語(yǔ)言。它把所有可并行執(zhí)行的語(yǔ)句或進(jìn)程S1，S2，Sn用并行語(yǔ)句對(duì)cobegincoend（或parbeginparend）括起來(lái)，如下程序的執(zhí)行過(guò)程如圖所示：beginS0；cobegin S1；S2； Sn；coendSn+1；end第第6 6章章 多處理機(jī)多處理機(jī)66并行語(yǔ)句也可以嵌套。例如：begin S0； cobegin S1； begin S2； cobegin S3；S4；S5；coend S6； end S7； coend S8；end其程序的執(zhí)行過(guò)程如圖6.21所示。第第6 6章章 多處理機(jī)多處理機(jī)672.并行編譯 實(shí)現(xiàn)算術(shù)表達(dá)式的并行處理可以應(yīng)用并行算法編制并行程序，還可以依靠并行編譯程序。有一些編譯算法，可以經(jīng)過(guò)或不經(jīng)過(guò)逆波蘭式，直接從算術(shù)表達(dá)式產(chǎn)生能并行執(zhí)行的目標(biāo)程序。例如，對(duì)下列表達(dá)式：Z = E + A * B * C/D + F利用普通串行編譯算法，產(chǎn)生三元指令組為 1 *AB2 *1C3 /2D4 +3E5 +4F6 =5Z指令之間均相關(guān)，需5級(jí)運(yùn)算。第第6 6章章 多處理機(jī)多處理機(jī)68如采用并行編譯算法可得 1 *AB2 /2D3 *124 +EF5 +346 =5Z 其中，1，2為第1級(jí)；3，4為第2級(jí)；5，6為第3級(jí)。分配給兩個(gè)處理機(jī)，只需3級(jí)運(yùn)算即可實(shí)現(xiàn)。第第6 6章章 多處理機(jī)多處理機(jī)696.3.4 多處理機(jī)的操作系統(tǒng)多處理機(jī)的操作系統(tǒng)1.多處理機(jī)操作系統(tǒng)的功能與特點(diǎn)在多處理機(jī)中有多臺(tái)實(shí)際的處理機(jī)，它可以真正實(shí)現(xiàn)多個(gè)進(jìn)程的并行執(zhí)行。在多處理機(jī)中有多個(gè)進(jìn)程并行執(zhí)行，很可能出現(xiàn)若干個(gè)進(jìn)程同時(shí)要求訪問(wèn)某一共享的資源的情況。在多處理機(jī)中有各處理機(jī)共享的全局性存儲(chǔ)器，還有每個(gè)處理機(jī)自己的局部存儲(chǔ)器。多處理機(jī)（尤其是松耦合多處理機(jī)）表現(xiàn)出任務(wù)、資源和控制上的分布性。 系統(tǒng)的容錯(cuò)性對(duì)多處理機(jī)，特別是分布式系統(tǒng)是非常重要的。 第第6 6章章 多處理機(jī)多處理機(jī)702. 多處理機(jī)操作系統(tǒng)的類型主從型，即集中控制方式；單獨(dú)管理型，即分布控制方式；浮動(dòng)管理型，即對(duì)稱控制方式。第第6 6章章 多處理機(jī)多處理機(jī)716.4 多處理機(jī)的性能多處理機(jī)的性能多處理機(jī)系統(tǒng)是程序并行的基礎(chǔ)，使用多處理機(jī)的主要目的是用多個(gè)處理機(jī)并發(fā)執(zhí)行多個(gè)任務(wù)來(lái)提高解題速度。只有當(dāng)多處理機(jī)系統(tǒng)的并行性能為程序并行帶來(lái)較高的性能時(shí)才能產(chǎn)生效益，否則只會(huì)增加程序的運(yùn)行成本和復(fù)雜性。因此，多處理機(jī)的性能除取決于多處理機(jī)系統(tǒng)硬件和軟件的性能之外，在很大程度上取決于程序的并行度。第第6 6章章 多處理機(jī)多處理機(jī)726.4.1 任務(wù)粒度與系統(tǒng)性能任務(wù)粒度與系統(tǒng)性能 顆粒規(guī)模或粒度是衡量軟件進(jìn)程所含計(jì)算量的尺度。任務(wù)粒度過(guò)小，輔助開(kāi)銷大，系統(tǒng)效率低；粒度過(guò)大，并行度低，性能也不會(huì)很高。 如果用R表示程序用于有效計(jì)算的時(shí)間開(kāi)銷，C表示處理機(jī)間的通信等的輔助時(shí)間開(kāi)銷，則比值R/C就作為衡量任務(wù)粒度大小的依據(jù)。在粗任務(wù)粒度并行情況下，R/C比值較大，計(jì)算所需的處理機(jī)數(shù)量少；在細(xì)任務(wù)粒度并行情況下，R/C比值較小，計(jì)算所需的處理機(jī)數(shù)量多。用R/C比值能直觀地反映系統(tǒng)的性能，只有R/C比值較大時(shí)，開(kāi)發(fā)并行性才能得到好處。第第6 6章章 多處理機(jī)多處理機(jī)736.4.2 多處理機(jī)性能模型多處理機(jī)性能模型現(xiàn)在我們通過(guò)幾種不同的多處理機(jī)模型來(lái)分析R/C的值對(duì)系統(tǒng)性能的影響。 1.基本模型2.隨機(jī)模型3.通信開(kāi)銷為線性函數(shù)的模型4.完全重疊通信的模型5.具有多條通信鏈的模型第第6 6章章 多處理機(jī)多處理機(jī)741.基本模型若某應(yīng)用程序包含M個(gè)任務(wù)，在一個(gè)由N臺(tái)處理機(jī)組成的系統(tǒng)上運(yùn)行。為了簡(jiǎn)單起見(jiàn)，我們先討論在一個(gè)僅有兩臺(tái)處理機(jī)的系統(tǒng)上運(yùn)行的情況，并假設(shè)以下兩個(gè)條件是成立的。l每個(gè)任務(wù)的計(jì)算時(shí)間開(kāi)銷為R，各處理機(jī)的執(zhí)行速度相同；l不在同一臺(tái)處理機(jī)上運(yùn)行的兩個(gè)任務(wù)之間用于通信的額外時(shí)間開(kāi)銷為C，忽略在同一臺(tái)處理機(jī)上運(yùn)行的兩個(gè)任務(wù)之間的通信開(kāi)銷。第第6 6章章 多處理機(jī)多處理機(jī)75 M個(gè)任務(wù)在兩臺(tái)處理機(jī)上有多種分配方法。如果把全部任務(wù)都分配給一臺(tái)處理機(jī)而另一臺(tái)空閑，則通信開(kāi)銷最小，但沒(méi)有并行性。若把K個(gè)任務(wù)分配給一臺(tái)處理機(jī)，把（MK）個(gè)任務(wù)分配給另一臺(tái)處理機(jī)，則系統(tǒng)運(yùn)行包含M個(gè)任務(wù)的應(yīng)用程序所需總的處理時(shí)間為： TRmax(MK，K)C(MK)K (6.1)式中第一項(xiàng)為程序用于計(jì)算的時(shí)間，取兩臺(tái)處理機(jī)執(zhí)行時(shí)間中的大者；第二項(xiàng)為通信產(chǎn)生的額外開(kāi)銷時(shí)間。K稱為任務(wù)分配參數(shù)。 第第6 6章章 多處理機(jī)多處理機(jī)76由(6.1)式可知，總處理時(shí)間是K的函數(shù), 第一項(xiàng)是K的線性函數(shù)，第二項(xiàng)是K的二次函數(shù)。任務(wù)分配應(yīng)使總處理時(shí)間最小，分析任務(wù)分配參數(shù)K對(duì)處理時(shí)間的影響可得：l當(dāng)K0 時(shí)(任務(wù)集中分配給一臺(tái)處理機(jī))，執(zhí)行時(shí)間最長(zhǎng)(為RM)，通信時(shí)間最短(為0)，總的處理時(shí)間為T1RM；l當(dāng)KM/2時(shí)(任務(wù)平均分配給兩臺(tái)處理機(jī)) ，執(zhí)行時(shí)間最短(為RM/2)，通信時(shí)間最長(zhǎng)(為CM2/4)，總的處理時(shí)間為T2RM/2CM2/4。第第6 6章章 多處理機(jī)多處理機(jī)77使總處理時(shí)間最短的K的最佳值的范圍為：0KM/2。當(dāng)0KM/2時(shí)，max(MK，K)MK，總處理時(shí)間為TR(MK)C(MK)K CK2(CMR)KRM (6.2)T與K的關(guān)系曲線為一開(kāi)口向下的拋物線，如圖6.22所示。第第6 6章章 多處理機(jī)多處理機(jī)78由圖6.22可見(jiàn)，當(dāng)K0和KM/2時(shí)的總處理時(shí)間T較小，而誰(shuí)是使總處理時(shí)間最小的最佳K值則與任務(wù)粒度有關(guān)。設(shè)TT1T2，有TRM(RM/2CM2/4) RM/2CM2/4 (6.3) 對(duì)(6.3)式進(jìn)行討論，并得該模型的結(jié)論：l若T0，得R/CM/2，說(shuō)明任務(wù)粒度較細(xì)。此時(shí)T1T2，表示采用集中分配策略(K0)可使總的處理時(shí)間最短，為TRM；l若T0，得R/CM/2，說(shuō)明任務(wù)粒度較粗。此時(shí)T1T2，表示采用平均分配策略(KM/2)可使總的處理時(shí)間最短，為TRM/2CM2/4。第第6 6章章 多處理機(jī)多處理機(jī)79 現(xiàn)在，討論包含M個(gè)任務(wù)的程序，在一個(gè)由N臺(tái)處理機(jī)組成的系統(tǒng)上運(yùn)行的情況。仍假設(shè)各處理機(jī)的速度相同，每個(gè)任務(wù)的執(zhí)行時(shí)間均為R，將Ki個(gè)任務(wù)分配給第i臺(tái)處理機(jī)，則N臺(tái)處理機(jī)執(zhí)行一個(gè)包含M個(gè)任務(wù)的應(yīng)用程序所需的總處理時(shí)間為 (6.4)式中第一項(xiàng)為N臺(tái)處理機(jī)中最大的計(jì)算時(shí)間，第二項(xiàng)為不同處理機(jī)上的任務(wù)兩兩之間通信的額外時(shí)間開(kāi)銷的總和。這里，假設(shè)處理機(jī)的計(jì)算時(shí)間和通信時(shí)間不會(huì)重疊，而且所有的任務(wù)間的通信是串行執(zhí)行的。iiiiiiiiiiiKMKKKKKkKCRMCRMCRT2222max2max2max第第6 6章章 多處理機(jī)多處理機(jī)80與兩臺(tái)處理機(jī)系統(tǒng)的基本模型類似，N臺(tái)處理機(jī)系統(tǒng)的基本模型也有一個(gè)決定采用平均分配還是采用集中分配的臨界值。設(shè)M為N的倍數(shù)，由(6.4)式可得：l當(dāng)K0 時(shí)(采用集中分配策略)，執(zhí)行時(shí)間最長(zhǎng)(為RM)，通信時(shí)間最短(為0)，總的處理時(shí)間為T1RM；l當(dāng)KM/N時(shí)(采用平均分配策略，將M個(gè)任務(wù)盡可能平均分配給N臺(tái)處理機(jī)) ，執(zhí)行時(shí)間最短(為RM/N)，通信時(shí)間最長(zhǎng)(為CM2/2(11/N)，總的處理時(shí)間為TNRM/NCM2/2(11/N) 第第6 6章章 多處理機(jī)多處理機(jī)81 注意，這里的所謂平均，是指如果任務(wù)數(shù)M是處理機(jī)數(shù)N的整數(shù)倍，則每臺(tái)處理機(jī)分得M/N個(gè)任務(wù)，否則讓大多數(shù)處理機(jī)分得個(gè)任務(wù)，一臺(tái)處理機(jī)分配剩余的不足個(gè)任務(wù)，余下的處理機(jī)空閑不分配任務(wù)。這樣可減少不必要的通信開(kāi)銷。例如，有19個(gè)任務(wù)和6臺(tái)處理機(jī)。讓其中4臺(tái)處理機(jī)各分得個(gè)任務(wù)，第5臺(tái)處理機(jī)分得余下的3個(gè)任務(wù)，而第6臺(tái)處理機(jī)空閑，免去了通信開(kāi)銷。第第6 6章章 多處理機(jī)多處理機(jī)82令TT1TN ，有 (6.5)對(duì)(6.5)式進(jìn)行討論，由此得出R/C比值對(duì)最佳任務(wù)分配的影響：l若T0，得R/CM/2，細(xì)粒度任務(wù)對(duì)應(yīng)的R/C比值很小，T1TN表示采用集中分配策略(K0)將任務(wù)集中分配給一臺(tái)處理機(jī)可使總的處理時(shí)間最短，為TRM；l若T0，得R/CM/2，粗粒度任務(wù)對(duì)應(yīng)的R/C比值較大，T1TN表示采用平均分配策略(KM/N)將任務(wù)平均分配給所有處理機(jī)會(huì)使總的處理時(shí)間最短，為TRM/NCM2/2(11/N) NCNRMRMTM1122第第6 6章章 多處理機(jī)多處理機(jī)832. 隨機(jī)模型對(duì)于N臺(tái)處理機(jī)系統(tǒng)的隨機(jī)模型，假設(shè)各處理機(jī)的速度不一定相同，各任務(wù)的執(zhí)行時(shí)間也可能不同。執(zhí)行一個(gè)包含M個(gè)任務(wù)的應(yīng)用程序所需的總處理時(shí)間為 (6.6)其中，Ri表示i臺(tái)處理機(jī)執(zhí)行一個(gè)任務(wù)所需的時(shí)間，其它參數(shù)的含義與N臺(tái)處理機(jī)系統(tǒng)的基本模型相同。iiiiiKKKRMCT2max第第6 6章章 多處理機(jī)多處理機(jī)84 例2.2假設(shè)有兩臺(tái)處理機(jī)，處理機(jī)A的速度是B的兩倍，參考基本性能模型和隨機(jī)模型的分析，請(qǐng)問(wèn)如何分配任務(wù)能達(dá)到最優(yōu)性能?解：由于A處理機(jī)的速度是B處理機(jī)的兩倍，現(xiàn)給B分配K個(gè)任務(wù)，每個(gè)任務(wù)執(zhí)行的時(shí)間為R，則A分配MK個(gè)任務(wù)，每個(gè)任務(wù)執(zhí)行的時(shí)間為R/2，同時(shí)設(shè)各對(duì)任務(wù)之間的通信開(kāi)銷為C。參考基本性能模型和隨機(jī)模型的系統(tǒng)總處理時(shí)間公式，可寫出兩臺(tái)處理機(jī)執(zhí)行M個(gè)任務(wù)的總處理時(shí)間為 (6.7)式中第一項(xiàng)為并行執(zhí)行時(shí)間，若要使其最小，必須讓兩個(gè)處理器的執(zhí)行時(shí)間完全相等，即R/2(MK)RK，可得KM/3。KKMCRKKMRT，2max第第6 6章章 多處理機(jī)多處理機(jī)85分析(6.7)式可得：l當(dāng)K0時(shí)(全部任務(wù)集中分配給速度快的A處理機(jī))，計(jì)算時(shí)間最長(zhǎng)(為RM/2)，通信時(shí)間最短(為0)，總處理時(shí)間為T1RM/2； l當(dāng)KM/3時(shí)(讓兩個(gè)處理機(jī)的執(zhí)行時(shí)間相等)，計(jì)算時(shí)間最短(為RM/3)，通信時(shí)間為2M2C/9，總處理時(shí)間為T2RM/32M2C/9；l當(dāng)KM/2時(shí)(將任務(wù)平均分配給兩個(gè)處理機(jī))，計(jì)算時(shí)間并不是最短(為RM/2)，但通信開(kāi)銷卻是最大(M2C/4)，故其總處理時(shí)間(RM/2M2C/4) 肯定大于T2。第第6 6章章 多處理機(jī)多處理機(jī)86 由此可知，使總處理時(shí)間T最小的K值最佳取值范圍為0KM/3。據(jù)此簡(jiǎn)化(6.7)式得 (6.8)2222RMKRMCCKKMCKMRTK第第6 6章章 多處理機(jī)多處理機(jī)87T與K的關(guān)系曲線為一開(kāi)口向下的拋物線，如圖6.23所示。其中，圖6.23(a) 表示當(dāng)K0時(shí)T取最小值（圖中M/3也可能大于(2MCR)/(4C)，圖中未標(biāo)出），圖6.23(b) 表示當(dāng)KM/3時(shí)T取最小值。第第6 6章章 多處理機(jī)多處理機(jī)88具體K取何值能使總處理時(shí)間最短仍與任務(wù)粒度有關(guān)。設(shè)TT1T2，有 (6.9)分析上式并得以下結(jié)論：l若T0，得R/C4M/3，說(shuō)明任務(wù)粒度較細(xì)。此時(shí)取K0可使總的處理時(shí)間最短，為TRM/2；l若T0，得R/C4M/3，說(shuō)明任務(wù)粒度較粗。此時(shí)取KM/3可使總的處理時(shí)間最短，為TRM/32M2C/9。92322CRMRMTM第第6 6章章 多處理機(jī)多處理機(jī)893. 通信開(kāi)銷為線性函數(shù)的模型在基本模型中，我們假設(shè)每一對(duì)在不同處理機(jī)上的任務(wù)之間都要通信，因此通信開(kāi)銷隨處理機(jī)數(shù)目的增加以二次函數(shù)增加。實(shí)際上一個(gè)任務(wù)要同另一臺(tái)處理機(jī)上的所有任務(wù)通信，且通信內(nèi)容相同，只需向這臺(tái)處理機(jī)發(fā)送一次信息就可以了，當(dāng)信息到達(dá)該處理機(jī)后，在這臺(tái)處理機(jī)上各任務(wù)之間的信息傳遞就不必花費(fèi)通信開(kāi)銷了。 第第6 6章章 多處理機(jī)多處理機(jī)90在通信開(kāi)銷為線性函數(shù)的模型中，就假設(shè)通信開(kāi)銷與處理機(jī)的數(shù)目N成正比，而不是同分配的任務(wù)數(shù)成正比。如果把M個(gè)任務(wù)分配給N臺(tái)處理機(jī)，并假設(shè)M是N的整數(shù)倍，各處理機(jī)的速度相同，每個(gè)任務(wù)的執(zhí)行時(shí)間均為R，則總的處理時(shí)間為TRmax(Ki)CN (6.10)式中的第一項(xiàng)與任務(wù)的分配有關(guān)，第二項(xiàng)與任務(wù)的分配無(wú)關(guān)。如果把M個(gè)任務(wù)平均地分配給N臺(tái)處理機(jī)，那么第一項(xiàng)等于RM/N，使計(jì)算時(shí)間最短?？偺幚頃r(shí)間為T(N)RM/NCN。當(dāng)N增加時(shí)，第二項(xiàng)的增加甚至?xí)^(guò)第一項(xiàng)的減少。所以存在一個(gè)最大的N值，這時(shí)的性能最佳，這個(gè)N值是R/C的函數(shù)。 第第6 6章章 多處理機(jī)多處理機(jī)91把M個(gè)任務(wù)平均地分配給N1臺(tái)處理機(jī)，則總處理時(shí)間為T(N1)RM/(N1)C(N1)對(duì) M個(gè)任務(wù)多分配一臺(tái)處理機(jī)是希望總處理時(shí)間減少，即T(N1)T(N)，由此可得出進(jìn)一步提高并行性的條件為： 或 N (6.11)上式表明，如果分配M個(gè)任務(wù)給N臺(tái)處理機(jī)并行處理，當(dāng)任務(wù)的R/C比值已達(dá)到臨界值N(N1)/M后，總的處理時(shí)間不會(huì)隨N的增加而減少，反而也會(huì)增加。原因是通信開(kāi)銷的增加超過(guò)了提高并行性帶來(lái)的好處。式(6.11)的第二種形式直接給出了可使用處理機(jī)數(shù)量N的上限。CRMNN1CRM第第6 6章章 多處理機(jī)多處理機(jī)92 該模型的結(jié)論是：將任務(wù)平均地分配給各臺(tái)處理機(jī)，且當(dāng)處理機(jī)的數(shù)目 時(shí)，總的處理時(shí)間最短。 在本模型中，通信開(kāi)銷隨著N值的增大線性增加，當(dāng)N超過(guò)臨界值時(shí)，計(jì)算時(shí)間的減少將小于通信開(kāi)銷的增加，這使得系統(tǒng)的整體性能下降。前面的幾種模型告訴我們，在某種情況下，限制并行性反而能獲得高性能，也就是說(shuō)，使用的處理機(jī)數(shù)目并不是越多越好。CRMN 第第6 6章章 多處理機(jī)多處理機(jī)934. 完全重疊通信的模型 完全重疊通信是指任務(wù)間的通信過(guò)程可以完全與任務(wù)的計(jì)算過(guò)程重疊進(jìn)行以使額外開(kāi)銷趨于零。在N臺(tái)處理機(jī)系統(tǒng)的完全重疊通信模型中，執(zhí)行包含M個(gè)任務(wù)的程序所需的總處理時(shí)間為iiiiiiiKMKKKKCRMCRT222maxmax2maxmax，第第6 6章章 多處理機(jī)多處理機(jī)94通信過(guò)程與計(jì)算過(guò)程完全重疊時(shí)，計(jì)算時(shí)間越短，總處理時(shí)間也就越短。當(dāng)任務(wù)平均分配時(shí)，即KM/N并帶入式(6.12)，得最短計(jì)算時(shí)間為 (6.13)通信時(shí)間為 (6.14)對(duì)于完全重疊通信模型，計(jì)算時(shí)間等于通信時(shí)間，由式(6.13)和(6.14)得 (6.15)NRMRTKimaxNCCMNMMi1122222NCNRMM1122第第6 6章章 多處理機(jī)多處理機(jī)95 當(dāng)N值很大時(shí)，1/N可忽略，式(6.15)可簡(jiǎn)化為 (6.16) 式(6.16)表明，包含M個(gè)任務(wù)的程序在N臺(tái)處理機(jī)上并行處理，若任務(wù)間的通信過(guò)程能與計(jì)算過(guò)程重疊進(jìn)行，則只有當(dāng)R/C比值等于或大于MN/2，才能將通信的開(kāi)銷完全屏蔽，從而使總處理時(shí)間最短。式(6.16)的第二種形式直接給出了可使用處理機(jī)數(shù)量N的上限，并顯示處理機(jī)數(shù)量N的選擇與可提供的任務(wù)數(shù)M成反比。MCRNMNCR22或第第6 6章章 多處理機(jī)多處理機(jī)96 若N的值不是很大，則式(6.15)中的1/N不能忽略。如對(duì)N2的兩臺(tái)處理機(jī)完全重疊通信的理想模型，有 (6.17) 簡(jiǎn)化上式，得R/CM/2，滿足此關(guān)系時(shí)總處理時(shí)間最短，為TRM/2。 該模型的結(jié)論是：將任務(wù)平均地分配給各臺(tái)處理機(jī)，當(dāng)處理機(jī)的數(shù)目N較大且等于2R/(CN) 時(shí)，計(jì)算時(shí)間與通信時(shí)間完全重疊，且總的處理時(shí)間最短。21122MCRM第第6 6章章 多處理機(jī)多處理機(jī)975. 具有多條通信鏈的模型如果每臺(tái)處理機(jī)與其他任何一臺(tái)處理機(jī)之間都有專用的通信鏈路，而且鏈路和處理機(jī)都支持雙向通信。由于一臺(tái)處理機(jī)在某一時(shí)刻只能與另一臺(tái)處理機(jī)通信，則在一個(gè)具有N臺(tái)處理機(jī)的系統(tǒng)中，通信過(guò)程的最大并發(fā)度為N。在這種理想情況下，總的通信開(kāi)銷可縮短為原來(lái)通信過(guò)程串行執(zhí)行時(shí)的1/N。在此具有多條通信鏈路支持并行通信的模型中，N臺(tái)處理機(jī)執(zhí)行M個(gè)任務(wù)的總處理時(shí)間為iiiiKKKMNCRT2max第第6 6章章 多處理機(jī)多處理機(jī)98設(shè)M為N的倍數(shù)，由式(6.18)可得l當(dāng)K0時(shí)（采用集中分配策略），執(zhí)行時(shí)間最長(zhǎng)（為RM），通信時(shí)間最短（為0）總的處理時(shí)間為T1RM；l當(dāng)N2時(shí)，由N臺(tái)處理機(jī)系統(tǒng)的基本模型可知，盡可能平均分配任務(wù)可以使總處理時(shí)間達(dá)到最小。故當(dāng)KM/N時(shí)（采用平均分配策略），執(zhí)行時(shí)間最短（為RM/N），通信時(shí)間最長(zhǎng)（CM2/(2N)(11/N)），總處理時(shí)間為NNCNRMMTN1122第第6 6章章 多處理機(jī)多處理機(jī)99 由式(6.19)可看出，當(dāng)N2時(shí)，計(jì)算時(shí)間和通信時(shí)間將隨N的增大而逐漸減少，即N越大，總處理時(shí)間TN越短，提高并行性將縮短程序的運(yùn)行時(shí)間。 為了確定任務(wù)粒度與分配策略和系統(tǒng)性能的關(guān)系， 設(shè)TT1TN，有 (6.20)分析(6.20)式可得以下結(jié)論：l若T0，則R/CM/(2N)，說(shuō)明任務(wù)粒度較細(xì)。此時(shí)取 K0，采用集中分配策略可使總處理時(shí)間最短，為 TRM；l若T0，則R/CM/(2N)，說(shuō)明任務(wù)粒度較粗。此時(shí)取KM/N，采用平均分配策略可使總處理時(shí)間最短，為TRM/NCM2/(2N)(11/N)，并且N的值越大(NM)總處理時(shí)間越短。NNCNRMRMTM1122第第6 6章章 多處理機(jī)多處理機(jī)1006.5 MIMD并行機(jī)結(jié)構(gòu)模型并行機(jī)結(jié)構(gòu)模型6.5.1并行向量處理機(jī)并行向量處理機(jī) 并行向量處理機(jī)的結(jié)構(gòu)如圖6.24所示。它包含功能很強(qiáng)的定制向量處理機(jī)、共享存儲(chǔ)器SM模塊和定制的高速縱橫交叉開(kāi)關(guān)互連網(wǎng)絡(luò)。PVP系統(tǒng)由少數(shù)幾臺(tái)巨型向量處理機(jī)采用共享存儲(chǔ)器方式互連而成，每個(gè)存儲(chǔ)模塊都能提供高速數(shù)據(jù)訪問(wèn)。這類機(jī)器通常不使用Cache，而是使用大量向量寄存器以及指令緩存。第第6 6章章 多處理機(jī)多處理機(jī)1016.5.2對(duì)稱多處理機(jī)對(duì)稱多處理機(jī) 對(duì)稱多處理機(jī)的結(jié)構(gòu)如圖6.25所示。它由帶有片內(nèi)和片外Cache的處理機(jī)經(jīng)總線或交叉開(kāi)關(guān)網(wǎng)絡(luò)與共享存儲(chǔ)器連接而成。該系統(tǒng)是具有對(duì)稱性特點(diǎn)的緊密耦合系統(tǒng)，每個(gè)處理機(jī)的能力都一樣，并且可以平等地訪問(wèn)任何共享存儲(chǔ)器模塊、I/O設(shè)備和操作系統(tǒng)服務(wù)，同時(shí)可以開(kāi)發(fā)較高的并行性。所有存儲(chǔ)單元按單一物理地址空間編址。 第第6 6章章 多處理機(jī)多處理機(jī)1026.5.3大規(guī)模并行處理機(jī)大規(guī)模并行處理機(jī) 大規(guī)模并行處理機(jī)的結(jié)構(gòu)如圖6.26所示。MPP并行機(jī)采用了大量的商品化微處理器芯片作為單結(jié)點(diǎn)，每個(gè)處理結(jié)點(diǎn)都帶有獨(dú)立編址的本地存儲(chǔ)器以及網(wǎng)絡(luò)接口電路(NIC) ，結(jié)點(diǎn)內(nèi)部通過(guò)存儲(chǔ)器總線(MB)相連，結(jié)點(diǎn)之間則由NIC通過(guò)高性能定制網(wǎng)絡(luò)實(shí)現(xiàn)互連。第第6 6章章 多處理機(jī)多處理機(jī)103分布共享存儲(chǔ)器多處理機(jī)的結(jié)構(gòu)如圖6.27所示。它與MPP在結(jié)構(gòu)上的區(qū)別是每個(gè)結(jié)點(diǎn)中增加了一個(gè)用于支持分布Cache一致性的Cache目錄DIR。所謂分布共享存儲(chǔ)器也稱為共享虛擬存儲(chǔ)器。它是將在物理上分散的各臺(tái)處理機(jī)所擁有的本地存儲(chǔ)器在邏輯上加以統(tǒng)一編址，形成一個(gè)統(tǒng)一的虛擬地址空間來(lái)支持存儲(chǔ)器的共享，以實(shí)現(xiàn)每臺(tái)處理機(jī)可以訪問(wèn)共享虛擬存儲(chǔ)器的任意一個(gè)地址。6.5.4分布共享存儲(chǔ)器多處理機(jī)分布共享存儲(chǔ)器多處理機(jī)第第6 6章章 多處理機(jī)多處理機(jī)1046.5.5機(jī)群系統(tǒng)機(jī)群系統(tǒng)機(jī)群系統(tǒng)是指利用高速網(wǎng)絡(luò)將一組計(jì)算機(jī)結(jié)點(diǎn)按某種結(jié)構(gòu)連接起來(lái)，并在并行程序設(shè)計(jì)以及可視化人機(jī)交互集成開(kāi)發(fā)環(huán)境支持下，統(tǒng)一調(diào)度、協(xié)調(diào)處理，實(shí)現(xiàn)高效并行處理的計(jì)算機(jī)系統(tǒng)。機(jī)群系統(tǒng)的結(jié)構(gòu)如圖6.28所示。第第6 6章章 多處理機(jī)多處理機(jī)105五種MIMD并行機(jī)模型的特性 PVPSMPMPPDSMCOW同構(gòu)性MIMDMIMDMIMDMIMDMIMD同步性異步或松同步異步或松同步異步或松同步異步或松同步異步或松同步通信機(jī)制共享變量共享變量消息傳遞共享變量消息傳遞地址空間單地址空間單地址空間多地址空間單地址空間多地址空間處理器類型專用定制商用商用商用商用互連網(wǎng)絡(luò)定制的縱橫交叉開(kāi)關(guān)總線或交叉開(kāi)關(guān)定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)商品化網(wǎng)絡(luò)（以太網(wǎng)、ATM）系統(tǒng)存儲(chǔ)器集中式共享集中式共享分布式非共享分布式共享分布式非共享代表機(jī)器Cray C-90、Fujistu VPP500、銀河2號(hào)IBM R50、SUN Ultra En-terprise 1000曙光1號(hào)Cray T3E、Inter ASCI Op-tion Red、曙光-1000Stanford DASH、Cray T3DSGI/Cray Origin 2000Berkeley NOW、Alpha Farm、Digital Trucluster模型特性