番茄花園-第九章多處理機.ppt

第九章 多處理機,多處理機系統(tǒng)由若干臺獨立的處理機組成，每臺處理機能夠獨立執(zhí)行自己的程序，處理機之間按某種形式互連，在統(tǒng)一的操作系統(tǒng)調(diào)度下，從而實現(xiàn)程序之間的數(shù)據(jù)交換和同步。Flynn稱這種結(jié)構(gòu)為多指令流多數(shù)據(jù)流（MIMD）結(jié)構(gòu)。,并行性(parallelism)：指同一時刻或同一時間間隔內(nèi)完成兩種或兩種以上性質(zhì)相同或不同的工作。只要在時間上相互重疊，均存在并行性。 并行性分：同時性、并發(fā)性。 并行性等級（執(zhí)行的角度，從低到高）： 1）指令內(nèi)部并行性，即指令內(nèi)部的微操作之間的并行。 2）指令間并行，即并行執(zhí)行兩條或多條指令。 3）任務(wù)級或過程級并行，即并行執(zhí)行兩個或多個過程或任務(wù)（程序段） 4）作業(yè)或程序級并行，即在多個作業(yè)或程序間的并行。 陣列處理機（SIMD）實現(xiàn)的是指令內(nèi)部并行性（多數(shù)據(jù)流執(zhí)行同一指令）。 多處理機系統(tǒng)（MIMD）實現(xiàn)指令以上級（任務(wù)級、作業(yè)級）并行。,并行性概念,多處理機系統(tǒng)的基本結(jié)構(gòu),互連網(wǎng)絡(luò),處理機1,處理機2,處理機N,存儲器,存儲器,存儲器,I/O,I/O,互連網(wǎng)絡(luò),處理機1,處理機2,處理機N,存儲器,存儲器,存儲器,I/O,I/O,I/O,兩種多處理機系統(tǒng)基本結(jié)構(gòu),2）分布式存儲器多處理機結(jié)構(gòu) （每臺處理器有自己的處理器和I/O設(shè)備，處理器之間通過互連網(wǎng)絡(luò)實現(xiàn)點對點信息交換）,1）共享存儲器多處理機結(jié)構(gòu) （存儲器和I/O設(shè)備是獨立的子系統(tǒng)，通過互連網(wǎng)絡(luò)為所有處理器共享，任何兩臺處理器可以通過共享存儲器單元實現(xiàn)通信）,兩種多處理機系統(tǒng)基本結(jié)構(gòu)： 1）共享存儲器使多處理機擁有同一的尋址空間，一方面便于處理機之間的信息交換，另一方面使程序員無需在程序中顯式地控制數(shù)據(jù)的分布和傳輸，因而易于編程。 2）分布式存儲器可以采用虛擬共享存儲器技術(shù)。虛擬共享存儲器（Virtual Shared Memory）對分布在各處理機的局部存儲器在邏輯上統(tǒng)一編址，形成一個為所有處理機共享的虛擬地址空間（ Virtual Address Space）。虛擬共享存儲器技術(shù)方便了程序員編程，但是，處理機之間信息交換的物理實現(xiàn)仍然是通過點對點的通信。,多處理機系統(tǒng)的基本結(jié)構(gòu),MIMD結(jié)構(gòu)特點（與SIMD比較）： 1）MIMD結(jié)構(gòu)有多個控制器，至少有多個指令部件，對各個PE實現(xiàn)單獨控制，而又相互協(xié)調(diào)配合。 2）MIMD結(jié)構(gòu)的外圍設(shè)備要能夠被多個PE分別調(diào)用，因而要通過互連網(wǎng)絡(luò)轉(zhuǎn)接。 3）MIMD互連網(wǎng)絡(luò)必須滿足各個PE隨機訪問主存儲器的要求，必須有存儲映射部件，滿足存儲空間動態(tài)分配和處理機共享數(shù)據(jù)的需要。,共享存儲器=共享存儲器+虛擬共享存儲器 共享存儲多處理機 (Shared Memory mulptiProcessors)，也稱為對稱多處理機SMP (Symmetry MultiProcessors) 有三種模型： 1) UMA多處理機 均勻存儲器存取模型 (Uniform Memory Access) 存儲器被所有處理機均勻共享 所有處理機對所有存儲單元具有相同的存取時間 每臺處理機有局部Cache 外圍設(shè)備可以共享 2) NUMA多處理機 非均勻存儲器存取 (Nonuniform Memory Access)模型 存儲器訪問時間隨存儲單元的位置不同而變化。 共享存儲器在物理上是分布在所有處理機中的本地存儲器。所有局部存儲器地址空間的集合就組成了全局地址空間。 處理機訪問本地存儲器比較快，訪問屬于另一臺處理機的遠(yuǎn)程存儲器則比較慢，因為通過互連網(wǎng)絡(luò)會產(chǎn)生附加的時間延遲。,共享存儲多處理機,3) COMA多處理機 只有Cache的存儲器結(jié)構(gòu) (Cache-Only Memory Architecture) 模型， COMA是一種只用Cache的多處理機系統(tǒng)，實際上，COMA模型是NUMA模型的一種特例。后者分布存儲器換成了Cache。 在每個處理機結(jié)點上沒有主存儲器，全部Cache組成了全局虛擬地址空間。 遠(yuǎn)程Cache訪問通過分布Cache目錄進(jìn)行。 共享存儲系統(tǒng)擁有統(tǒng)一的尋址空間，程序員不必參與數(shù)據(jù)分配和傳輸。,多處理機系統(tǒng)的特點,1）結(jié)構(gòu)靈活性 SIMD從解決專用問題發(fā)展而來，其結(jié)構(gòu)針對數(shù)組向量處理算法而設(shè)計，特點是：處理單元很多，但只需設(shè)置有限和固定的互連通路，即可滿足并行性很高的算法需要，是以解決大型數(shù)組計算問題為主的計算機。用庫克分類標(biāo)準(zhǔn)，屬于數(shù)組單執(zhí)行（SEA）一類。 MIMD有較強的通用性，即使對數(shù)組運算，也可以同時對多個數(shù)組進(jìn)行不同的處理，稱為數(shù)組多執(zhí)行（MEA）；它可以同時對多個標(biāo)量數(shù)據(jù)進(jìn)行處理，稱為標(biāo)量多執(zhí)行（MES）。要求能適應(yīng)更多樣的算法，更靈活的結(jié)構(gòu)，實現(xiàn)各種復(fù)雜的互連模式，同時解決共享資源沖突問題，因此，MIMD中處理單元數(shù)量不多。 SIMD：專用，PE數(shù)很多（幾千個），固定有限的通信 MIMD： 通用，PE幾十個，高速靈活的通信 2）程序并行性 SIMD實現(xiàn)操作級的并行，其并行性存在于指令內(nèi)部，由于結(jié)構(gòu)固定，加上系統(tǒng)專用，因此并行性易于實現(xiàn)。 MIMD不限于解決數(shù)組向量問題，其并行性存在于指令外部，表現(xiàn)在多個任務(wù)之間，加上通用性要求，從而使程序并行性的識別難度較大，需要利用多種途徑，如算法、程序語言、編譯、操作系統(tǒng)直至指令、硬件，盡量挖掘各種潛在的并行性，而且程序并行化的主要任務(wù)不應(yīng)放在程序員肩上。,3）并行任務(wù)派生 SIMD把同種操作集中在一起，由指令直接啟動各PE同時工作。 MIMD用專門的指令來表示并發(fā)關(guān)系，一個任務(wù)開始執(zhí)行時能夠派生出與它并行執(zhí)行的另一些任務(wù)，如果任務(wù)數(shù)多于處理機數(shù)，多余的任務(wù)進(jìn)入排隊器等待。 4）進(jìn)程同步 SIMD僅一個CU，自然是同步的 MIMD執(zhí)行不同的指令，工作進(jìn)度不會也不必保持相同，先做完的要停下來等待。有數(shù)據(jù)相關(guān)和控制相關(guān)也要停下來等待，要采取特殊的同步措施來保持程序所要求的正確順序。,一個簡單的例子：Y = A+B*C*D/E+F 用兩個處理機： CPU1： CPU2： B*C， D/E， A+F， B*C*D/E， A+B*C*D/E+F,5）資源分配和進(jìn)程調(diào)度 SIMD的PE數(shù)目固定，受同一控制器控制，程序員采用屏蔽手段改變實際參加操作的PE數(shù)目。 MIMD執(zhí)行并發(fā)任務(wù)，需用處理機的數(shù)目不固定，各個處理機進(jìn)入或退出任務(wù)的時刻不相同，所需共享資源的品種、數(shù)量又隨時變化。因此，如何進(jìn)行資源分配和進(jìn)程調(diào)度對整個系統(tǒng)的效率有直接的影響。,多處理機的Cache一致性問題,問題由來 由于一般的MIMD中處理機除了擁有共享存儲器外，還有自己的Cache，因此，MIMD的一般模型可描述如下（假設(shè)兩個處理機）：,P1,P2,總線,共享 存儲器,處理機,高速緩沖 存儲器,數(shù)據(jù)分布在P1的Cache1 、P2的Cache2和共享存儲器中。多處理機的Cache的不一致包括Cache1與Cache2之間的數(shù)據(jù)不一致以及Cache1、 Cache2與共享存儲器之間的數(shù)據(jù)不一致。 問題是有哪些因素會引起上述數(shù)據(jù)不一致？,1）共享可寫數(shù)據(jù)引起的不一致 假設(shè)有兩個處理機P1、P2，它們私有的Cache分別為C1、C2， C1、C2中保存共享存儲器某個數(shù)據(jù)X的拷貝，其初始狀態(tài)如下圖所示。 假設(shè)P1改寫C1，使X變?yōu)閄，如果P1采用“寫通過WT(Write Through)”策略，那么，主存對應(yīng)的數(shù)據(jù)也改為X，但是C2中的對應(yīng)數(shù)據(jù)仍然為X，這時如果P2讀C2，那么讀取的數(shù)據(jù)將是X，而非X，即與主存對應(yīng)數(shù)據(jù)不一致；如果采用“寫回WB(Write Back)”策略，即P1更新C1后主存數(shù)據(jù)不立即更新，而是當(dāng)該數(shù)據(jù)從C1調(diào)出時才更新主存數(shù)據(jù)，那么，主存數(shù)據(jù)仍然是X，這就導(dǎo)致了C1中的數(shù)據(jù)與主存數(shù)據(jù)不一致。,多處理機的Cache一致性問題,P1,P2,X,X,X,共享 存儲器,處理機,高速緩沖 存儲器,初始狀態(tài),P1,P2,X,X,X,寫通過,P1,P2,X,X,X,總線,寫回,2）進(jìn)程遷移引起的不一致 假設(shè)P1的C1保存共享數(shù)據(jù)X的拷貝，而P2的C2沒有該共享數(shù)據(jù)。若P1的進(jìn)程對C1中的X進(jìn)行了修改，使其變?yōu)閄，且采用“寫回”策略，內(nèi)存中的數(shù)據(jù)仍然是X。由于某種原因，該進(jìn)程從P1遷移到P2上運行，修改的X仍在P1的C1中，P2上的進(jìn)程從主存讀取數(shù)據(jù)X到C2，即遷移了的進(jìn)程讀取的數(shù)據(jù)是“過時”了的X，而非遷移前修改過的X。 若C1、C2都有共享數(shù)據(jù)X的拷貝，P2進(jìn)程修改了C2中X，使其變?yōu)閄，且采用“寫通過”策略，使主存中的X也修改為X。由于某種原因，該進(jìn)程從P2遷移到P1上運行，此時，C1中仍然是X，而不是修改過的X。,P1,P2,X,X,X,共享 存儲器,處理機,調(diào)整緩沖 存儲器,遷移之前,P1,P2,X,X,X,寫通過,P1,P2,X,X,X,總線,寫回,3）I/O傳輸引起的不一致 若C1、C2都有共享數(shù)據(jù)X的拷貝，當(dāng)I/O處理機將一個新的數(shù)據(jù)X輸入內(nèi)存時，導(dǎo)致了主存與Cache之間的數(shù)據(jù)不一致。 若C1、C2都有共享數(shù)據(jù)X的拷貝，當(dāng)P1運行過程中修改了X的值，使其變?yōu)閄，P1采用“寫回”策略，那么，主存的X與C1中的X不一致。這時，若I/O處理機要求輸出，輸出的將是主存的X，而非修改后的X。,P1,P2,X,X,存儲器,處理機,高速緩沖 存儲器,P1,P2,X,X,（寫通過）,P1,P2,X,X,總線,（寫回）,X,I/O,存儲器,X,X,（輸入）,存儲器,X,X,（輸出）,多處理機的Cache不一致性解決辦法,1）監(jiān)聽協(xié)議(Snoopy Protocol)：適用基于總線互連結(jié)構(gòu)的系統(tǒng)。 2）基于目錄的協(xié)議：適用非總線互連結(jié)構(gòu)的系統(tǒng)。 監(jiān)聽協(xié)議 通過總線監(jiān)聽機制實現(xiàn)高速緩沖和共享存儲器之間的數(shù)據(jù)一致性。 策略： Cache與主存之間：“寫通過WT”和“寫回WB” Cache與Cache之間：“寫無效WI(Write Invalidate)”和“寫更新WU(Write Update)” 1）“寫通過WT”：改寫Cache時同時改寫主存數(shù)據(jù)。 2）“寫回WB”：改寫Cache時不立即改寫主存數(shù)據(jù)，而是等Cache數(shù)據(jù)調(diào)出時才改寫主存數(shù)據(jù)。 3）“寫無效WI”：本地Cache數(shù)據(jù)改寫時，使遠(yuǎn)程數(shù)據(jù)塊拷貝無效。 4）“寫更新WU”：本地Cache數(shù)據(jù)改寫時，通過總線把改寫的數(shù)據(jù)塊廣播到含有該數(shù)據(jù)塊拷貝的所有其它Cache。 上述4中策略可組合起來使用，即： “寫通過WT”+“寫無效WI”、“寫通過WT”+“寫更新WU” “寫回WB”+“寫無效WI”、 “寫回WB”+“寫更新WU”,P1,P2,X,X,共享 存儲器,處理機,高速緩沖 存儲器,更新之前,P1,P2,X,I,寫無效,P1,P2,X,X,總線,寫更新,由于寫更新策略在本地Cache修改時要通過總線將修改過的數(shù)據(jù)塊內(nèi)容廣播給所有含有該數(shù)據(jù)塊拷貝的其它Cache，增加了總線的負(fù)擔(dān)，所以，一般系統(tǒng)中，很少使用寫更新策略，而是采用寫無效策略。基于此，以下只討論寫無效策略的監(jiān)聽協(xié)議。,1.采用寫通過策略的Cache 1）數(shù)據(jù)塊狀態(tài)：有效和無效。有效表示數(shù)據(jù)塊內(nèi)容正確，無效表示數(shù)據(jù)塊內(nèi)容已“過時”或不在本地Cache中。需要注意的是：有效和無效分別表示本地處理機對應(yīng)數(shù)據(jù)塊狀態(tài)，而非整個Cache狀態(tài)。 2）狀態(tài)圖,有效,無效,R1,W1,Wr,Rr,Wr,R1,W1,Rr,說明（假設(shè)本地處理機P1，對應(yīng)的Cache為C1；其它處理機Pr，對應(yīng)的Cache為Cr ）： R1本地讀(P1讀C1),W1本地寫;RrPr讀Cr,WrPr寫Cr。,遠(yuǎn)程讀，引起本地寫回操作,2.采用寫回策略的Cache 1）數(shù)據(jù)塊狀態(tài)：讀寫、只讀和無效。只讀狀態(tài)表示整個系統(tǒng)中不止一個數(shù)據(jù)塊拷貝是正確的；讀寫狀態(tài)表示數(shù)據(jù)塊至少被修改過一次，存儲器中相應(yīng)數(shù)據(jù)塊還沒有被修改，即在整個系統(tǒng)中只有一個數(shù)據(jù)塊拷貝是正確的。 2）狀態(tài)圖,讀寫,無效,W1,Rr,R1,Rr,R1,W1,只讀,Rr,Wr,W1,Wr,Wr,R1,3.寫一次(Writeonce)協(xié)議 結(jié)合寫通過和寫回的優(yōu)點，為減少總線流量，Cache第一次寫采用寫通過策略，爾后的寫采用寫回策略，此時，整個系統(tǒng)只有一份正確的拷貝。 1）數(shù)據(jù)塊狀態(tài)：有效、無效、保留、重寫。為了區(qū)分是否第一次寫，將讀寫狀態(tài)分成“保留”和“重寫”兩種狀態(tài)。其中，“保留”狀態(tài)表示數(shù)據(jù)從存儲器讀入Cache后只修改過一次，這時，Cache中的拷貝與存儲器中的拷貝一致，而且是正確的； “重寫”狀態(tài)表示數(shù)據(jù)塊不止一次被修改過，此時，存儲器中的數(shù)據(jù)塊不正確?！坝行А睜顟B(tài)表示從存儲器讀入數(shù)據(jù)塊，Cache中的數(shù)據(jù)與存儲器中的一致，相當(dāng)于寫回的“只讀”狀態(tài)。 2）狀態(tài)圖,無效,重寫,R1,Wr,R1,Rr,Rr,Wr,有效,Rr,W1,Wr,W1,R1,保留,W1,Rr,R1,W1,Wr,中心思想： 1）使用Cache目錄 2）記錄有關(guān)數(shù)據(jù)塊拷貝駐留Cache位置和狀態(tài)信息 3）無效命令只發(fā)給保存有關(guān)數(shù)據(jù)塊拷貝Cache 基于目錄的協(xié)議分類(目錄如何維護和目錄存放位置)： 1）全映射(full-map)目錄 2）有限(limited)目錄 3）鏈?zhǔn)?chained)目錄 1.全映射目錄協(xié)議 數(shù)據(jù)結(jié)構(gòu) 1）共享存儲器中目錄項 2）Cache狀態(tài)位,基于目錄的協(xié)議,C,-,-,-,-,數(shù)據(jù),X,共享存儲器,有效位,允許寫,數(shù)據(jù),X,Cache,重寫位 (數(shù)據(jù)是否已重寫) 1:已重寫 0:末重寫,處理機位 (每一位對應(yīng)一臺處理機) 1:處理機有數(shù)據(jù)塊拷貝 0:處理機無數(shù)據(jù)塊拷貝,注：Cache的一致性協(xié)議必須保證目錄狀態(tài)位與Cache數(shù)據(jù)塊狀態(tài)位一致。,P1,P2,PN,全映射目錄協(xié)議保持Cache一致性原理,C,-,-,-,數(shù)據(jù),X,共享存儲器,C,1,1,1,數(shù)據(jù),X,共享存儲器,C,-,-,1,數(shù)據(jù),X,共享存儲器,C1,C2,C3,P1,P2,P3,C1,C2,C3,P1,P2,P3,C1,C2,C3,P1,P2,P3,Read X,Read X,Read X,Write X,從第二種狀態(tài)到第三種狀態(tài)（P3要寫單元X時）： 1)C3發(fā)現(xiàn)包含X單元的塊有效，但不允許寫。 2)C3向包含X單元的存儲器模塊發(fā)寫請求，并暫停P3的工作。 3)該存儲器模塊發(fā)無效請求至C1、C2。 4)C1、C2接到無效請求后，將對應(yīng)塊置無效狀態(tài)，并發(fā)回答信號給存儲器模塊。 5)存儲器模塊接到C1、C2的回答信號后，置重寫位為“1”，清除指向C1、C2的指針，發(fā)允許信號給C3。 6)C3接到允許寫信號，更新Cache狀態(tài)，激活P3。,全映射目錄特點： 1）不具有可擴展性。 2）效率高，但開銷與處理器數(shù)目的平方成正比（因為目錄項數(shù)與處理器數(shù)目成正比，項的大小也與處理器數(shù)目成正比）。,2.有限目錄,C,數(shù)據(jù),X,共享存儲器,C,數(shù)據(jù),X,共享存儲器,C1,C2,C3,P1,P2,P3,C1,C2,C3,P1,P2,P3,Read X,注：當(dāng)目錄項指針域均建立指針后，再有一處理機需要裝入該數(shù)據(jù)，則目錄項需要實施指針替換，指針替換過程稱為驅(qū)逐。驅(qū)逐算法與Cache替換算法相似。,有限目錄特點： 1）目錄指針域數(shù)目固定，但指針域并不與處理機一一對應(yīng)，任何一個指針域可以為任何需要裝如入該數(shù)據(jù)塊的處理機建立指針，因此，具有可擴展性。 3.鏈?zhǔn)侥夸?鏈?zhǔn)侥夸浱攸c是既不限制共享數(shù)據(jù)塊拷貝數(shù)目，又保持可擴展性。 實現(xiàn)方法：通過建立目錄指針鏈跟蹤共享數(shù)據(jù)拷貝。 1）單向鏈法 2）雙向鏈法,C,數(shù)據(jù),X,共享存儲器,C1,C2,C3,P1,P2,P3,Read X,CT,X,C,數(shù)據(jù),X,共享存儲器,C1,C2,C3,P1,P2,P3,CT,X,X,假設(shè)C1沒有單元X的共享拷貝，這時處理機P1要讀單元X，則： 1）存儲器送一份拷貝給C1，同時附加一個鏈結(jié)束指針（CT），存儲器保持一個指向C1的指針。 爾后，當(dāng)P2要讀單元X時， 2）存儲器送一個拷貝給C2，同時送給C2一個指向C1的指針，存儲器保持一個指向C2的指針。,鏈?zhǔn)侥夸涰椖縿h除問題（假設(shè)刪Ci目錄）： 1）沿鏈發(fā)消息，使得Ci+1的指針指向Ci-1 ，把Ci從鏈中去掉。 2）使Ci及鏈中位于其后的所有Cache中的單元X無效。 鏈?zhǔn)侥夸浱攸c： 1）可擴展性。,多處理機性能指標(biāo)： 1）程序并行度 一個程序在各時間范圍內(nèi)執(zhí)行程序的處理機數(shù)目稱為程序的并行度（DOP）。 DOP是在假設(shè)可對該程序提供無限數(shù)量的處理機和其它所需資源條件下確定的，因此，DOP表示程序本身并行化程度，由程序相關(guān)性決定。 DOP是一個離散時間函數(shù)，DOP的時間函數(shù)曲線DOP(t)稱為程序并行性分布圖。平均并行性A表示程序單位時間平均可使用的處理機數(shù)目，其表達(dá)式如下：,A=,1 t2-t1,DOP(t)dt,t2 t1,若程序在時間段ti使用ji臺處理機，那么：,A=(ti.ji)/(ti),m i=1,m i=1,2）調(diào)和均值加速比 加速比是衡量并行系統(tǒng)優(yōu)劣的一個重要指標(biāo)，等于一個程序在一臺處理機上運行時間與在并行系統(tǒng)上運行時間的比值。包括多個加速比，調(diào)和均值加速比是其中一種。 在多處理機