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

1、第9章 多處理機(jī),9.1 多處理機(jī)結(jié)構(gòu)9.2 多處理機(jī)性能模型9.3 多處理機(jī)的Cache一致性9.4 大規(guī)模并行處理機(jī)9.5 對稱多處理機(jī)9.6 機(jī)群系統(tǒng),多處理機(jī)定義：兩個或兩個以上處理機(jī)(包括PU和CU)，通過高速互連網(wǎng)絡(luò)連接起來，在統(tǒng)一的操作系統(tǒng)管理下，實現(xiàn)指令以上級（任務(wù)級、作業(yè)級）并行。按照Flynn分類法，多處理機(jī)系統(tǒng)屬于MIMD計算機(jī)研究多處理機(jī)的目的：提前10年得到性能高100倍的高性能計算機(jī)系統(tǒng)。,

2、9.1.1 多處理機(jī)分類9.1.2 松散偶合多處理機(jī)9.1.3 緊密偶合多處理機(jī)9.1.4 多處理機(jī)系統(tǒng)的特點(diǎn),9.1 多處理機(jī)結(jié)構(gòu),9.1.1 多處理機(jī)分類,多處理機(jī)系統(tǒng)由多個獨(dú)立的處理機(jī)組成，每個處理機(jī)都能夠獨(dú)立執(zhí)行自己的程序。按照處理機(jī)之間的連接程度：緊密偶合和松散偶合多處理機(jī)按照是否共享主存儲器：共享存儲器和分布存儲器多處理機(jī)按照處理機(jī)類型：同構(gòu)型和異構(gòu)型多處理機(jī)按照處理機(jī)的個數(shù)：大規(guī)模并行處理機(jī)MPP和對稱

3、多處理機(jī)SMP,按照PE與IOP之間互連方式：對稱型：每個IOP能夠連接到所有PE上非對稱型：每個IOP只與一個PE連接。冗余對稱型：一個PE與多個IOP連接。按照存儲器的訪問方式：均均存儲器，UMA模型非均均存儲器，NUMA模型只有Cache，COMA模型另外，多向量處理機(jī)，機(jī)群系統(tǒng)等也稱為多處理機(jī)系統(tǒng)。,處理機(jī)之間的連接頻帶比較低處理機(jī)之間互為外圍設(shè)備進(jìn)行連接。通過并行口或串行口把多臺計算機(jī)連接起來

4、。多臺計算機(jī)之間的連接需要有多個接口。通過Ethernet網(wǎng)絡(luò)接口連接多臺計算機(jī)。速度達(dá)10Mb、100Mb、1Gb，Mynet已經(jīng)達(dá)到1.28Gb和2.56Gb。當(dāng)通信速度要求更高時，可以通過一個通道和仲裁開關(guān)CAS (Channel and Arbiter Switch)直接載存儲器總線之間建立連接。,9.1.2 松散偶合多處理機(jī),處理機(jī)之間共享主存儲器，通過高速總線或高速開關(guān)連接。每個CPU能夠訪問任意一個存儲器模

5、塊通過映象部件把全局邏輯地址變換成局部物理地址通過互連網(wǎng)絡(luò)尋找合適的路徑，并分解訪問存儲器的沖突多個輸入輸出處理機(jī)IOP也連接在互連網(wǎng)絡(luò)上，輸入輸出設(shè)備與CPU共享主存儲器。處理機(jī)個數(shù)不能太多，一般幾個到幾十個。,9.1.3 緊密偶合多處理機(jī),緊密偶合方式要求有很高通信頻帶?？梢圆捎萌缦麓胧?1)采用高速互連網(wǎng)絡(luò)(2)增加存儲模塊個數(shù)，一般n?m，取1～2倍之間。(3)每個存儲模塊再分成多個小模塊，并采用流

6、水線方式工作。(4)每個CPU都有自己的局部存儲器LM。(5)每個CPU設(shè)置一個Cache。,1. 結(jié)構(gòu)靈活陣列處理機(jī)：專用，PE數(shù)多，固定有限通信多處理機(jī)： 通用，PE數(shù)少，高速靈活通信2. 程序并行性陣列處理機(jī)的并行性存在于指令內(nèi)部，識別比較容易。多處理機(jī)的并行性存在于指令外部，在多個任務(wù)之間，識別難度較大。一個簡單的例子：Y = A+B*C*D/E+F，用兩個處理機(jī)計算：CPU1：B*C， A+F

7、， A+B*C*D/E+FCPU2：D/E， B*C*D/E，,9.1.4 多處理機(jī)系統(tǒng)的特點(diǎn),3. 并行任務(wù)派生陣列處理機(jī)把同種操作集中，由指令直接啟動各PE同時工作。多處理機(jī)用專門的指令來表示并發(fā)關(guān)系，一個任務(wù)執(zhí)行時能夠派生出與它并行的另一些任務(wù)如果沒有空閑處理機(jī)，任務(wù)進(jìn)入排隊器等待4. 進(jìn)程同步陣列處理機(jī)僅一個CU，自然是同步的。多處理機(jī)中，各處理機(jī)執(zhí)行不同的指令，工作進(jìn)度不會也不必保持相同。先做完的要停下等待。有

8、數(shù)據(jù)相關(guān)和控制相關(guān)也要停下等待。,要采取同步措施來保持程序要求的正確順序5. 資源分配和進(jìn)程調(diào)度陣列處理機(jī)的PE是固定的，用屏蔽來改變實際參加操作的PE數(shù)目。多處理機(jī)執(zhí)行并發(fā)任務(wù)，需用處理機(jī)的數(shù)目不固定，各處理機(jī)進(jìn)出任務(wù)的時刻不相同，所需共享資源的品種、數(shù)量隨時變化。資源分配和進(jìn)程調(diào)度問題，對整個系統(tǒng)的效率有很大的影響。,引起峰值性能下降的原因：(1)由于處理機(jī)之間通信而產(chǎn)生的延遲。(2)一臺處理機(jī)與其它處理機(jī)同步所需的開銷

9、。(3)當(dāng)沒有足夠多任務(wù)時，一臺或多臺處理機(jī)處于空閑狀態(tài)。(4)由于一臺或多臺處理機(jī)執(zhí)行無用的工作。(5)系統(tǒng)控制和操作調(diào)度所需的開銷。,9.2 多處理機(jī)性能模型,研究多處理機(jī)的目的： 單處理機(jī)的速度提高很快，為什么還要研究多處理機(jī)？提前5年得到速度高10倍的機(jī)器。 或用1/10的價格獲得一臺高性能的機(jī)器。在某些適合進(jìn)行并行處理得應(yīng)用領(lǐng)域，可以達(dá)到：提前10年得到速度高100倍的機(jī)器。 或用1

10、/100的價格獲得一臺高性能的機(jī)器。,并行性在很大程度上依賴于R/C比值其中：R: 程序執(zhí)行時間，C: 通信開銷R/C小，并行度低。R/C大，并行性高。把作業(yè)分解成較大的塊，能得到較大的R/C，但所得到的并行性小R/C是衡量任務(wù)粒度(Granularity)的尺度粗粒度(Coarsegrain)并行：R/C大，通信開銷小 細(xì)粒度(Finegrain)并行：R/C小，通信開銷大細(xì)粒度并行性是程序盡可能地分解成小任

11、務(wù)，在極端情況下，一個小任務(wù)只完成一個操作,目標(biāo)：由M個任務(wù)組成的程序，在N臺處理機(jī)組成的系統(tǒng)上運(yùn)行，求最短執(zhí)行時間？基本模型僅考慮由兩臺處理機(jī)組成的系統(tǒng)。 總處理時間＝Rmax(M－K，K)＋C(M－K)K 其中：R：每個任務(wù)的執(zhí)行時間， C：通信開銷， K：任務(wù)分配參數(shù)。當(dāng)通信時間很小時，把M個任務(wù)平均分給兩臺處理機(jī)當(dāng)通信時間很大時，把M個任務(wù)分配給一臺處理

12、機(jī),9.2.1 基本模型,通信時間： C(M-K)K是一個開口向下的二次函數(shù)， 任務(wù)執(zhí)行時間是兩根相交的直線。 當(dāng)通信時間比較大時，總時間的最小值發(fā)生在端點(diǎn)， 當(dāng)通信時間比較小時，總時間的最小值發(fā)生在中點(diǎn)。結(jié)論： (1)總時間的最小值只可能出現(xiàn)在中點(diǎn)或兩個端點(diǎn)， (2)如果總時間的最小值發(fā)生在中點(diǎn)，必須滿足： M R ＞ R M/2 + C M/2 M/

13、2 R/C ＞ M/2總時間最短的結(jié)論：當(dāng)R/C＜M/2時，把所有任務(wù)分配給同一臺處理機(jī)，K＝0；當(dāng)R/C＞M/2時，把任務(wù)平均分配給兩臺處理機(jī)，K＝M/2。,要解決的問題：把M個任務(wù)分配給N臺處理機(jī)，求總處理時間的最小值。實際的最小值發(fā)生在極端分配情況下， 或者將所有的任務(wù)集中在一臺處理機(jī)上， 或者將任務(wù)平均分配給所有處理機(jī)。先討論平均分配方法：,9.2.2 N臺處理機(jī)系統(tǒng)的基本模

14、型,平均分配方法：例1：４個任務(wù)平均分給３臺處理機(jī)： 例2： 11個任務(wù)平均分給５臺處理機(jī)：,M個任務(wù)分配給N臺處理機(jī)的最佳分配方法： 臺處理機(jī)，每臺 個任務(wù)如果M/N≠0，則：另外有1臺處理機(jī)分得剩下的 個任務(wù)；剩下的

15、 臺處理機(jī)不分配任何任務(wù)。例如：101個任務(wù)平均分給50臺處理機(jī)：　　　　 有33臺處理機(jī)，每臺分給3個任務(wù)； 另有１臺處理機(jī)分給２個任務(wù)； 剩下的16臺處理機(jī)不分配任務(wù)。,假設(shè)Ki個任務(wù)分給了第ｉ臺處理機(jī)：第一項求出N臺處理機(jī)中最大執(zhí)行時間；第二項計算出Ki與（M－Ki）任務(wù)之間兩兩通信的開銷時間，它是關(guān)于Ki的二次函數(shù)。Ki最多有3個取值：

16、 、 和0當(dāng) M 是 N 的倍數(shù)時，當(dāng)R/C＞M/2時采用平均分配方法， 當(dāng)R/C＜M/2時采用集中分配方法。,多處理機(jī)系統(tǒng)的加速比：一個計算問題在一臺處理機(jī)上運(yùn)行時間與在多處理機(jī)系統(tǒng)上運(yùn)行時間的比值 當(dāng)M是N的倍數(shù)時，有：如果M和N較小，R/C較大，即分母中的第一項遠(yuǎn)大于第二項，則加速比與處理機(jī)臺數(shù)N成正比。當(dāng)處理機(jī)臺數(shù)N很大，加速比≈

17、 ，趨近于一個常數(shù)。這時如果再增加處理機(jī)，性能的提高很小。,總結(jié)上面幾個模型，可以得出如下結(jié)論：(1)多處理機(jī)系統(tǒng)結(jié)構(gòu)所需的額外開銷，包括調(diào)度，對共享資源的競爭，同步，處理機(jī)之間通信等。(2)當(dāng)處理機(jī)臺數(shù)增加時，額外開銷時間也增加。有時，額外開銷的增加可能比處理機(jī)數(shù)目的線性增加更快。(3)R/C比值越大，越有利于計算過程。如果采用粗粒度，能夠獲得較大的R/C比值；但是并行程度將大為降低。(4)為了使價格和性能都比

18、較合理，處理機(jī)數(shù)目存在一個極大值，這個值主要依賴于機(jī)器的系統(tǒng)結(jié)構(gòu)、基本技術(shù)（尤其是通信技術(shù)）和具體的應(yīng)用問題。,在并行處理機(jī)和多處理機(jī)系統(tǒng)中，采用局部Cache會引起Cache與共享存儲器之間的一致性問題。存儲系統(tǒng)行為的兩個不同方面What: 讀操作得到的是什么值When: 什么時候才能將已寫入的值返回給讀操作出現(xiàn)不一致性問題的原因有三個：共享可寫的數(shù)據(jù)、進(jìn)程遷移、I/O傳輸,9.3 多處理機(jī)的Cache一致性,1.寫共享

19、數(shù)據(jù)引起的不一致性使用多個局部Cache時，可能發(fā)生Cache不一致性問題：當(dāng)P1把X的值寫為X’之后，如果P1采用寫通過方式，內(nèi)存中的內(nèi)容也變?yōu)閄’，但是P2處理機(jī)Cache中的內(nèi)容還是X。 如果P1采用寫回策法，內(nèi)存中的內(nèi)容還是X，當(dāng)P2處理機(jī)要讀X時，讀到的是X而不是X’。,9.3.1 問題由來,2.進(jìn)程遷移引起的數(shù)據(jù)不一致性P1和P2中都有共享數(shù)據(jù)X的拷貝，P2修改了X，并采用寫通過方式，所以內(nèi)存中的X修改成了X’

20、。如果該進(jìn)程遷移到P1上，P1的Cache中仍然是X。P1中有共享數(shù)據(jù)X的拷貝，而P2中沒有該共享數(shù)據(jù)，P1進(jìn)程對X進(jìn)行了修改，如果該進(jìn)程遷移到了P2上，P2運(yùn)行時從內(nèi)存中讀到是X。,3.I/O造成數(shù)據(jù)不一致性如果P1和P2在各自的局部Cache中都有X的拷貝，當(dāng)I/O將一個新數(shù)據(jù)X’寫入存儲器時就導(dǎo)致存儲器和Cache的數(shù)據(jù)不一致。如果兩個局部Cache中都有X的拷貝，并采用寫回方式，當(dāng)P1把X修改成X’之后；輸出部件讀X，存儲

21、器把X傳給輸出部件一種解決I/O操作引起數(shù)據(jù)不一致性的方法是把I/O處理機(jī)分別連接到各自的局部Cache上。,有兩類解決Cache不一致性問題的協(xié)議：在總線互連的多處理機(jī)系統(tǒng)中，通常采用監(jiān)聽協(xié)議。在其他多處理機(jī)系統(tǒng)中，通常采用基于目錄協(xié)議。,9.3.2 監(jiān)聽協(xié)議,1.兩種監(jiān)聽協(xié)議使用監(jiān)聽協(xié)議，有兩種方法：方法一：寫無效（Write Invalidate）策略，在本地Cache的數(shù)據(jù)塊修改時使遠(yuǎn)程數(shù)據(jù)塊都無效。方法二：

22、寫更新（Write Update）策略，在本地Cache數(shù)據(jù)塊修改時通過總線把新的數(shù)據(jù)塊廣播給含該塊的所有其他Cache采用寫無效或?qū)懜虏呗耘cCache采用寫回方式（Write Back）還是寫通過方式（Write Through）無關(guān)。如果Cache采用的寫通過方式，在使遠(yuǎn)程數(shù)據(jù)塊無效或更新其他Cache的同時，還要同時修改共享存儲器中的內(nèi)容。,,Cache一致性協(xié)議 在多個處理器中用來維護(hù)一致性的協(xié)議。關(guān)鍵：跟蹤記

23、錄共享數(shù)據(jù)塊的狀態(tài) 兩類協(xié)議（采用不同的共享數(shù)據(jù)狀態(tài)跟蹤技術(shù)）目錄法（directory） 物理存儲器中共享數(shù)據(jù)塊的狀態(tài)及相關(guān)信息均被保存在一個稱為目錄的地方。監(jiān)聽法（snooping）每個Cache除了包含物理存儲器中塊的數(shù)據(jù)副本之外，也保存著各個塊的共享狀態(tài)信息。,Cache通常連在共享存儲器的總線上，各個Cache控制器通過監(jiān)聽總線來判斷它們是否有總線上請求的數(shù)據(jù)塊。 兩種更新協(xié)議（維持一致性要求）寫作

24、廢協(xié)議 在處理器對某個數(shù)據(jù)項進(jìn)行寫入之前，保證它擁有對該數(shù)據(jù)項的唯一的訪問權(quán)。(作廢其他副本),,例 在寫回Cache、監(jiān)聽總線的情況下，寫作廢協(xié)議的實現(xiàn),,寫更新協(xié)議 當(dāng)一個處理器對某數(shù)據(jù)項進(jìn)行寫入時，通過廣播使其他Cache中所有對應(yīng)于該數(shù)據(jù)項的副本進(jìn)行更新。 例 在寫回Cache、監(jiān)聽總線的情況下，寫更新協(xié)議的實現(xiàn)。,,寫更新和寫作廢協(xié)議性能上的差別主要來自：在對同一個

25、數(shù)據(jù)進(jìn)行多次寫操作而中間無讀操作的情況下，寫更新協(xié)議需進(jìn)行多次寫廣播操作，而寫作廢協(xié)議只需一次作廢操作。在對同一Cache塊的多個字進(jìn)行寫操作的情況下，寫更新協(xié)議對于每一個寫操作都要進(jìn)行一次廣播，而寫作廢協(xié)議僅在對該塊的第一次寫時進(jìn)行作廢操作即可。寫作廢是針對Cache塊進(jìn)行操作，而寫更新則是針對字（或字節(jié)）進(jìn)行?？紤]從一個處理器A進(jìn)行寫操作后到另一個處理器B能讀到該寫入數(shù)據(jù)之間的延遲時間。 寫更新協(xié)議的延遲時間較小。,

26、小規(guī)模多處理機(jī)中實現(xiàn)寫作廢協(xié)議的關(guān)鍵利用總線進(jìn)行作廢操作：把要作廢的地址放到總線上 （一個放，多個讀） 寫操作的順序性：由總線實現(xiàn) （獲取總線控制權(quán)的順序性）寫直達(dá)Cache：因為所有寫的數(shù)據(jù)同時被寫回主存，所以從主存中總可以取到最新的數(shù)據(jù)值。對于寫回Cache，得

27、到數(shù)據(jù)的最新值會困難一些，因為最新值可能在某個Cache中，也可能在主存中。,監(jiān)聽協(xié)議及其實現(xiàn),在寫回法Cache條件下的實現(xiàn)技術(shù)Cache的標(biāo)識（tag）用于實現(xiàn)監(jiān)聽。作廢一個塊只需將其有效位（valid）置為無效。給每個Cache塊加一個特殊的狀態(tài)位。狀態(tài)：共享（shared）—— 至少一個副本，clean專有 （exclusive）—— 唯一副本，dirty Cache塊的擁有者：擁有唯一的Cache塊副本的處理器。

28、,在每個結(jié)點(diǎn)內(nèi)嵌入一個Cache狀態(tài)控制器。 控制器根據(jù)來自處理器或總線的請求，改變所選擇的數(shù)據(jù)塊的狀態(tài)。因為每次總線操作均要檢查Cache的地址標(biāo)識，這可能會影響CPU對Cache的訪問?？赏ㄟ^下列兩種技術(shù)之一來減少影響 ：復(fù)制標(biāo)志位采用多級包容Cache （許多系統(tǒng)采用）,在非總線結(jié)構(gòu)的多處理機(jī)系統(tǒng)中，采用基于目錄的Cache一致性協(xié)議。。 1.Cache目錄結(jié)構(gòu)目錄：一種專用的數(shù)據(jù)結(jié)構(gòu)，用于記錄可以進(jìn)

29、入Cache的每個數(shù)據(jù)塊的狀態(tài)、哪些處理器有該塊的副本以及是否修改過等信息。Cache目錄中存放的內(nèi)容是大量的指針，用以指明塊拷貝的地址，每個目錄項還有一個重寫位，指明是否有一個Cache允許寫入數(shù)據(jù)。,9.3.3 基于目錄的協(xié)議,根據(jù)Cache目錄的存放形式，有集中式和分布式兩種。根據(jù)目錄的結(jié)構(gòu)，目錄協(xié)議分成三類：全映射(Full-Map)目錄：存放全局存儲器每個塊的有關(guān)數(shù)據(jù)。有限(Limited)目錄：

30、每個目錄項的指針數(shù)固定。鏈?zhǔn)?Chained)目錄：把目錄分布到所有Cache中。,目錄的使用規(guī)則： 當(dāng)一個CPU對Cache進(jìn)行寫操作時，要根據(jù)Cache目錄中的內(nèi)容將所有其他存有相同內(nèi)容的所有Cache拷貝無效，并置重寫位。 在CPU對Cache進(jìn)行讀操作時，如果讀命中，則直接讀Cache即可。 如果重寫位為“0”，則從主存或其他Cache中讀入該塊，并修改目錄。,2.全映射目錄目錄項中有N個處理

31、機(jī)位和一個重寫位。處理機(jī)位表示相應(yīng)處理機(jī)對應(yīng)的Cache塊的狀態(tài)。只有一個處理機(jī)的重寫位為“1”，則該處理機(jī)可以對該塊進(jìn)行寫操作。Cache的每個數(shù)據(jù)塊有兩個狀態(tài)位。一位表示數(shù)據(jù)塊是否有效，另一位表示有效塊是否允許寫。,從第二種狀態(tài)(b)轉(zhuǎn)移至第三種狀態(tài)(c)的過程如下：(1)Cache3發(fā)現(xiàn)包含X單元的塊有效，但不允許寫(2)Cache3向包含X單元的存儲器模塊發(fā)寫請求，并暫停P3工作(3)該存儲器模塊發(fā)無效請求

32、至Cache1和Cache2(4)Cache1和Cache2接到無效請求后，將對應(yīng)塊置為無效態(tài)，并發(fā)回答信號給存儲器模塊。(5)存儲器模塊接到Cache1和Cache2的回答信號后，置重寫位為“1”，清除指向Cache1和Cache2的指針，發(fā)允許寫信號到Cache3。(6)Cache3接到允許寫信號，更新Cache狀態(tài)，激活P3。優(yōu)點(diǎn)：全映射目錄協(xié)議的效率比較高。缺點(diǎn)：開銷與處理機(jī)數(shù)目的平方成正比，

33、 不具有擴(kuò)展性。,3.有限目錄當(dāng)處理機(jī)數(shù)目為N時，限制目錄大小為O(N log2 N)。目錄指針需要對N進(jìn)行二進(jìn)制編碼，每個指針占log2 N位，目錄所占的總存儲空間與（Nlog2 N）成正比。當(dāng)Cache1和Cache2中都有X的拷貝時，若P3請求訪問X，則必須在在Cache1和Cache2中選擇一個使之無效，這種替換過程稱為驅(qū)逐。有限目錄的驅(qū)逐需要一種驅(qū)逐策略，驅(qū)逐策略的好壞對系統(tǒng)的性能具有很大的影響。驅(qū)逐策略

34、與Cache替換策略在很多方面是相同的。,4. 鏈?zhǔn)侥夸?通過維護(hù)一個目錄指針鏈來跟蹤共享數(shù)據(jù)拷貝。當(dāng)P1讀X時，存儲器送X到Cache1,同時寫Cache1的一個鏈結(jié)束指針CT，在存儲器中也保存一個指向Cache1的指針。當(dāng)P2讀X時，存儲器送X給Cache2, 同時給Cache2一個指向Cache1的指針,存儲器則保存一個指向Cache2的指針。當(dāng)某一處理機(jī)需要寫X時,它必須沿整個目錄鏈發(fā)送一個數(shù)據(jù)無效信息。在收到所

35、有處理機(jī)的回答信號之后，存儲器才給該處理機(jī)寫允許權(quán)。,當(dāng)Cache中的數(shù)據(jù)塊需要替換時，要把該Cache從目錄鏈中刪除。有如下解決辦法： (1)把Cachei+1的指針指向Cachei-1。在Cachei中存放新數(shù)據(jù)塊。 (2)使Cachei及在鏈中位于其后的所有Cache中的單元X無效。 (3)使用雙向鏈。在替換時不再需要遍歷整個鏈。但指針增加了一倍，一致性協(xié)議也更加復(fù)雜。,優(yōu)點(diǎn)：不限制共享數(shù)據(jù)塊的拷貝數(shù)目，又保持了

36、可擴(kuò)展性。指針的長度以處理機(jī)數(shù)目的對數(shù)關(guān)系增長，Cache的每個數(shù)據(jù)塊的指針數(shù)目與處理機(jī)數(shù)目無關(guān)。缺點(diǎn)：鏈?zhǔn)侥夸浀膹?fù)雜程度超過了前兩種目錄。,9.4 大規(guī)模并行處理機(jī),多處理機(jī)系統(tǒng)主要有四大類：(1)多向量處理機(jī)系統(tǒng)：如CRAY YMP-90，NEC SX-3和FUJITSU VP-2000(2)SMP(Symmetry MultiProcessors)對稱多處理機(jī) SMP(Shared Memory mulptiPro

37、cessors)共享存儲多處理機(jī) 如SGI Challenge、Sun SparcCenter 2000(3)MPP(massively parallel processing)大規(guī)模并行處理機(jī) 如Intel Paragon，CM-5，Cray T3D(4)Cluster 機(jī)群系統(tǒng)（NOW或COM）,1. 科學(xué)計算中的重大課題要求提供3T性能：(1) 1Teraflops計算能力(2) 1Terabyte主存儲器(

38、3) 1Terabyte/s 輸入輸出頻帶寬度科學(xué)計算中的重大課題：全球氣候預(yù)報, 基因工程 ,飛行動力學(xué) ,海洋環(huán)流, 流體動力學(xué), 超導(dǎo)建模, 半導(dǎo)體建模, 量子染色動力學(xué), 視覺，證券指數(shù)計算，電力安全評估，建筑工程抗震性評估 ，核能開發(fā)利用，汽車碰撞 等領(lǐng)域。,2. 采用的關(guān)鍵技術(shù)：VLSI, 可擴(kuò)展技術(shù), 共享虛擬存儲技術(shù)虛擬共享存儲器(Shared Virtual Memory)也稱為共享分布存儲器(Distri

39、buted Shared Memory)；物理上分布存儲器，邏輯上共享的存儲器。虛擬共享存儲器的優(yōu)點(diǎn)：編程容易, 系統(tǒng)結(jié)構(gòu)靈活可擴(kuò)充性好, 有較好的軟件移植性與消息傳遞方式相比，程序運(yùn)行效率高，主要原因：,(1)數(shù)據(jù)塊緩存在本地, 可以多次使用(2)通信時間分散，提高了并行性(3)擴(kuò)大存儲空間，減少換頁操作虛擬共享存儲器實現(xiàn)途徑：(1)硬件實現(xiàn), 利用Cache,需要增加專用硬件(2)操作系統(tǒng)和庫實現(xiàn)，通過虛擬存儲機(jī)制

40、取得共享和一致性。在松耦合的分布存儲多處理機(jī)上，不需要增加任何硬件(3)編譯實現(xiàn)，自動將共享訪問轉(zhuǎn)換成同步和一致原語。大多數(shù)系統(tǒng)采用途徑(1)和(2)，或這兩種途徑結(jié)合實現(xiàn),3. 同步MIMD機(jī)器SIMD與MIMD的優(yōu)點(diǎn)結(jié)合在一起。CM-5同時支持SIMD與MIMD兩種并行計算方式。數(shù)據(jù)并行可以采用SIMD、多SIMD或同步MIMD模式。32到16384個處理器結(jié)點(diǎn)，每個結(jié)點(diǎn)有一個SPARC處理機(jī)，32MB存儲器，64位浮點(diǎn)和

41、整數(shù)操作，128Mflops向量處理部件,三個網(wǎng)絡(luò)：數(shù)據(jù)網(wǎng)絡(luò)提供點(diǎn)對點(diǎn)通信?？刂凭W(wǎng)絡(luò)提供廣播、同步、掃描和系統(tǒng)管理功能。診斷網(wǎng)絡(luò)從后臺訪問所有系統(tǒng)硬件，測試系統(tǒng)完整性，檢測和隔離錯誤。數(shù)據(jù)網(wǎng)絡(luò)和控制網(wǎng)絡(luò)有很好的可擴(kuò)展性?？梢詣澐殖梢粋€或多個分區(qū)供用戶使用每個分區(qū)一臺控制處理機(jī)，一組處理結(jié)點(diǎn)，數(shù)據(jù)和控制網(wǎng)絡(luò)的專用部分。,4. CM-5網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)網(wǎng)絡(luò)采用胖樹型網(wǎng)，數(shù)據(jù)處理結(jié)點(diǎn)、控制處理機(jī)和I/O通道都位于胖

42、樹的葉子上。利用胖樹的層次結(jié)構(gòu)特性，可以劃分一棵子樹給一個用戶。采用4元胖樹實現(xiàn)，每個內(nèi)部開關(guān)結(jié)點(diǎn)由n個尋徑器芯片組成。每個尋徑器與4個子芯片和2或4個父芯片相連?？梢苑峙洳煌淖訕涮幚聿煌淖鳂I(yè)，子樹的大小可以任意。每臺處理機(jī)與數(shù)據(jù)網(wǎng)絡(luò)有兩條連接通路。,5. 控制處理機(jī)控制處理機(jī)由CPU、存儲器、本地磁盤、網(wǎng)絡(luò)接口、以太網(wǎng)組成。它相當(dāng)于一臺標(biāo)準(zhǔn)工作站。網(wǎng)絡(luò)接口通過控制網(wǎng)絡(luò)和數(shù)據(jù)網(wǎng)絡(luò)使處理機(jī)與系統(tǒng)的其它部分相連。控制處理

43、機(jī)專門執(zhí)行管理功能，不需要高性能的運(yùn)算部件。每臺控制處理機(jī)都能夠運(yùn)行操作系統(tǒng)，負(fù)責(zé)并行處理資源的管理。一部分控制處理機(jī)管理用戶區(qū)的計算資源，其它管理I/O資源。,6.處理結(jié)點(diǎn)通過控制網(wǎng)絡(luò)和數(shù)據(jù)網(wǎng)絡(luò)將結(jié)點(diǎn)與系統(tǒng)的其它部分相連。每個向量部件有一個流水ALU和64個64位的寄存器。每條向量指令可傳送給一個向量部件、或一對向量部件、或同時廣播給所有4個向量部件。標(biāo)量處理機(jī)負(fù)責(zé)地址轉(zhuǎn)換和循環(huán)控制，向量處理部件的操作與標(biāo)量處理部件并行執(zhí)行

44、。16384個處理結(jié)點(diǎn)的總峰值速度為：214×27＝221 Mflops=2Tflops,9.5 對稱多處理機(jī),對稱多處理機(jī) (Symmetry MultiProcessors) 共享存儲多處理機(jī) (Shared Memory mulptiProcessors)，有三種模型：1. UMA多處理機(jī)均勻存儲器存取模型 (Uniform Memory Access), 存儲器被所有處理機(jī)均勻共享所有處理機(jī)對所有存儲單元

45、具有相同的存取時間, 每臺處理機(jī)有局部Cache外圍設(shè)備可以共享,2. NUMA多處理機(jī)非均勻存儲器存取 (Nonuniform Memory Access)模型存儲器訪問時間隨存儲單元的位置不同而變化。共享存儲器在物理上是分布在所有處理機(jī)中的本地存儲器。所有局部存儲器地址空間的集合就組成了全局地址空間。處理機(jī)訪問本地存儲器比較快，訪問屬于另一臺處理機(jī)的遠(yuǎn)程存儲器則比較慢，因為通過互連網(wǎng)絡(luò)會產(chǎn)生附加的時間延遲。,只有Cache

46、的存儲器結(jié)構(gòu) (Cache-Only Memory Architecture) 模型；COMA是一種只用Cache的多處理機(jī)系統(tǒng)實際上，COMA模型是NUMA模型的一種特例，后者分布存儲器換成了Cache在每個處理機(jī)結(jié)點(diǎn)上沒有主存儲器，全部Cache組成了全局虛擬地址空間遠(yuǎn)程Cache訪問通過分布Cache目錄進(jìn)行共享存儲系統(tǒng)擁有統(tǒng)一的尋址空間，程序員不必參與數(shù)據(jù)分配和傳輸。,3. COMA多處理機(jī),1996年SGI公司的Or

47、igin 2000服務(wù)器，首先采用S2MP并行體系結(jié)構(gòu)S2MP實際上是NUMA多處理機(jī)系統(tǒng)，采用分布存儲器，并通過cache對系統(tǒng)的共享和局部數(shù)據(jù)都進(jìn)行緩存。從用戶編程角度看，S2MP是一種共享存儲的多處理機(jī)系統(tǒng)。S2MP的主要特點(diǎn)：(1)編程容易，使用方便。(2)可擴(kuò)展性好，增加處理器數(shù)目容易。(3)通信開銷小，可開發(fā)程序的細(xì)粒度并行性,4. S2MP結(jié)構(gòu),S2MP的關(guān)鍵技術(shù)：(1)高速無阻塞互連網(wǎng)絡(luò)，增加多處理機(jī)

48、系統(tǒng)的通信帶寬。(2)分布式存儲器，隨處理器數(shù)目的增加自動增加存儲器帶寬。(3)引入cache，降低訪存時延。(4)所有存儲器統(tǒng)一編址，提供單一的大容量地址空間。(5)每個處理器結(jié)點(diǎn)上有一個目錄存儲器，維護(hù)cache一致性。,雙核處理技術(shù)的介紹,什么是雙核處理器?　　簡而言之，雙核處理器即是基于單個半導(dǎo)體的一個處理器上擁有兩個一樣功能的處理器核心。換句話說，將兩個物理處理器核心整合入一個核中。,雙核的優(yōu)點(diǎn),提高處理器性

49、能　　因為處理器實際性能是處理器在每個時鐘周期內(nèi)所能處理指令數(shù)的總量，因此增加一個內(nèi)核，處理器每個時鐘周期內(nèi)可執(zhí)行的單元數(shù)將增加一倍。但只有充分利用兩個內(nèi)核中的所有可執(zhí)行單元，才能使系統(tǒng)達(dá)到最大性能。增強(qiáng)處理器功能　　雙處理器架構(gòu)的引入和微軟Longhorn操作系統(tǒng)將在很大程度上促進(jìn)虛擬技術(shù)的發(fā)展。虛擬化技術(shù)可以讓一臺物理計算機(jī)虛擬出若干個虛擬的系統(tǒng)，這些虛擬系統(tǒng)能使用同樣的PC資源獨(dú)立工作。換句話說，這些技術(shù)允許用戶在他們的PC

50、上使用超過一個操作系統(tǒng)，以便每個操作系統(tǒng)解決特定的運(yùn)算任務(wù)。,,雙核的由來　如果將處理器的運(yùn)行頻率比做高速公路的最高限速，前端總線則是這條道路容納的車道數(shù)，在兩者都不能再進(jìn)一步時，還有什么辦法可以解決交通堵塞呢？修建一條同樣的道路顯然就可以解決問題了，這與雙核的工作方式本質(zhì)上是一樣的道理。事實上，在服務(wù)器領(lǐng)域，多路處理器系統(tǒng)已經(jīng)不是新鮮事了；隨著工藝的進(jìn)步，將雙路系統(tǒng)集成到處理器內(nèi)部也是可以實現(xiàn)的。,雙核處理器的發(fā)展,高端的RISC處

51、理器中　早在上個世紀(jì)末，HP和IBM就已經(jīng)提出雙核處理器的可行性設(shè)計，并成功推出了擁有雙內(nèi)核的HP PA8800和IBM Power4處理器。 Sun也在2003年10月微處理器論壇中，發(fā)表雙核心UltraSPARCⅣ處理器 x86平臺 　AMD和Intel在2004年公布了各自的雙核計劃，AMD率先在服務(wù)器和工作站領(lǐng)域引入雙核架構(gòu)，而Intel則是率先在臺式機(jī)領(lǐng)域引入雙核技術(shù)！,具體雙核處理結(jié)構(gòu)的介紹,AMD和Intel不同的

52、體系結(jié)構(gòu),ＡＭＤ——”雙核” 兩個處理器核心直接連接到同一個內(nèi)核上，核心之間以芯片速度通信 Intel——”雙芯” 采用多個核心共享前端總線的方式，把兩個獨(dú)立的內(nèi)核封裝在一起 。,對Intel和AMD雙核處理器技術(shù)分析及比較,AMD的雙核是把兩顆內(nèi)核Core(s)集成在一塊晶片硅上，而Intel的雙核其實是用電路將兩個獨(dú)立的Packet(s)縫合在一起。Intel的雙核架構(gòu)會遇到多個內(nèi)核爭用總線資源的瓶頸問題。AMD直連

53、架構(gòu)(也就是通過超傳輸技術(shù)讓CPU內(nèi)核直接跟外部I/O相連，不通過前端總線)和集成內(nèi)存控制器技術(shù)，使得每個內(nèi)核都自己的高速緩存可資遣用，都有自己的專用車道直通I/O，沒有資源爭搶的問題，實現(xiàn)雙核和多核更容易。,,,從上面看起來，Intel的雙核心處理器在技術(shù)規(guī)格上落后于AMD雙核心處理器 在價格上，Intel雙核心處理器的價格遠(yuǎn)遠(yuǎn)低于AMD雙核心處理器的價格，因此極具市場競爭力！,1. 機(jī)群系統(tǒng)的組成機(jī)群系統(tǒng)是利用高速網(wǎng)絡(luò)將一組高性

54、能工作站或高檔PC機(jī)連接起來，在并行程序設(shè)計以及可視化人機(jī)交互集成開發(fā)環(huán)境支持下，統(tǒng)一調(diào)度，協(xié)調(diào)處理，實現(xiàn)高效并行處理的計算機(jī)系統(tǒng)。Cluster、NOW、COW從結(jié)構(gòu)和結(jié)點(diǎn)間的通信方式來看，屬于分布存儲系統(tǒng)。,9.6 機(jī)群系統(tǒng),機(jī)群系統(tǒng)中的主機(jī)和網(wǎng)絡(luò)可以是同構(gòu)的，也可以是異構(gòu)的。微處理機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)和并行編程環(huán)境的發(fā)展使得機(jī)群系統(tǒng)這一新的并行處理系統(tǒng)形式正成為當(dāng)前研究的熱點(diǎn)。(1)微處理器的性能不斷提高。(2)網(wǎng)絡(luò)技術(shù)的進(jìn)

55、步使得松散耦合系統(tǒng)的通信瓶頸逐步得到緩解。(3)并行編程環(huán)境的開發(fā)使得新編并行程序或改寫串行程序更為容易。,2. 機(jī)群系統(tǒng)的特點(diǎn) (1)系統(tǒng)開發(fā)周期短 (2)用戶投資風(fēng)險小 (3)系統(tǒng)價格低 (4)節(jié)約系統(tǒng)資源 UC Berkeley計算機(jī)系100多臺工作站的使用情況調(diào)查表明，一般單機(jī)系統(tǒng)的使用率不到10%，而機(jī)群系統(tǒng)中的資源利用率可達(dá)到80%左右。 (5)系統(tǒng)擴(kuò)展性好

56、 (6)用戶編程方便,3. 機(jī)群系統(tǒng)的關(guān)鍵技術(shù)(1)高效的通信系統(tǒng)在用戶空間實現(xiàn)通信協(xié)議精簡通信協(xié)議Active Message通信機(jī)制(2)并行程序設(shè)計環(huán)境PVM(Parallel Virtual Machine)開始于1989年夏天,美國橡樹嶺國家實驗室(ORNL)；是一套并行計算工具軟件，支持多用戶及多任務(wù)運(yùn)行；支持多種結(jié)構(gòu)的計算機(jī)，工作站、并行機(jī)以及向量機(jī)等；,傳統(tǒng)通信協(xié)議 (TCP/IP),,,,10M Ethe

57、rnet,100M Ethernet,Myrinet,硬件開銷,軟件開銷,通信開銷分析,軟件開銷成為影響通信系統(tǒng)性能的瓶頸,支持C、C++和Fortran語言；自由軟件，使用非常廣泛；編程模型可以是SPMD或MPMD；具有容錯功能，當(dāng)發(fā)現(xiàn)一個結(jié)點(diǎn)出故障時，自動將之刪除MPI(Message Passing Interface)在1992年11月至1994年元月產(chǎn)生。 能用于大多數(shù)并行計算機(jī)、計算機(jī)機(jī)群和異構(gòu)網(wǎng)絡(luò)環(huán)境，支持C和F

58、ortran兩種語言,編程模型采用SPMDExpress美國Parasoft公司推出；能在不同的硬件環(huán)境上運(yùn)行；支持C和Fortran兩種程序設(shè)計語言。,Linda美國Yale大學(xué)與科學(xué)計算協(xié)會共同研制；通過函數(shù)擴(kuò)充現(xiàn)并行程序的設(shè)計；支持C-Linda、Fortran-Linda等(3)并行程序設(shè)計語言在多處理機(jī)系統(tǒng)中，必須用并行程序設(shè)計語言編寫程序?；蛘甙岩呀?jīng)用串行語言編寫的程序轉(zhuǎn)換成并行語言程序之后，才能在多處理機(jī)系統(tǒng)上

59、運(yùn)行。,把傳統(tǒng)串行語言程序轉(zhuǎn)換成并行語言程序的過程稱為并行編譯。有兩種并行編譯方式：全自動并行編譯與半自動并行編譯：全自動并行編譯是方向，但實現(xiàn)起來很困難。半自動并行編譯又稱為交互式并行編譯。程序員通過多次與機(jī)器對話，找到串行程序中可以并行執(zhí)行的部分。并行編譯器生成代碼的形式有多種： 并行高級語言程序、并行中間語言程序、并行目標(biāo)語言程序,(4) 負(fù)載平衡技術(shù)一個大任務(wù)可分解為多個子任務(wù)，把多個子任務(wù)分配到各個處理結(jié)點(diǎn)上并行

60、執(zhí)行的技術(shù)稱為負(fù)載平衡技術(shù)對于由異構(gòu)處理結(jié)點(diǎn)構(gòu)成的并行系統(tǒng)，相同的負(fù)載在各結(jié)點(diǎn)上的運(yùn)行時間可能不同。因此，準(zhǔn)確的負(fù)載定義應(yīng)是負(fù)載量與結(jié)點(diǎn)處理能力的比值負(fù)載平衡技術(shù)的核心就是調(diào)度算法，即將各個任務(wù)比較均衡地分布到不同的處理結(jié)點(diǎn)上并行計算，從而使各結(jié)點(diǎn)的利用率達(dá)到最大。,負(fù)載平衡技術(shù)分為靜態(tài)和動態(tài)兩大類：靜態(tài)方法是在編譯時針對用戶程序的各種信息(任務(wù)的計算量和通信關(guān)系等)及并行系統(tǒng)本身的狀況(網(wǎng)絡(luò)結(jié)構(gòu)、各結(jié)點(diǎn)計算能力等)對用戶程序中的

61、并行任務(wù)作出靜態(tài)分配決策。動態(tài)方法是在程序運(yùn)行過程中實現(xiàn)負(fù)載平衡的。它通過分析并行系統(tǒng)的實時負(fù)載信息，動態(tài)地將任務(wù)在各處理機(jī)之間進(jìn)行分配和調(diào)整，以消除系統(tǒng)中負(fù)載分布的不均勻性。動態(tài)負(fù)載平衡的算法簡單，實時控制，但增加了系統(tǒng)的額外開銷。,(5)并行程序調(diào)試技術(shù)用并行程序設(shè)計語言編寫程序，比用串行程序設(shè)計語言更容易出錯，因此，在多處理機(jī)系統(tǒng)中，用并行程序設(shè)計語言編寫程序更加依賴于并行調(diào)試工具。并行程序調(diào)試的主要困難： 并行程序

62、的執(zhí)行過程不能重現(xiàn)。,(6)可靠性技術(shù)在多處理機(jī)上運(yùn)行的程序通常比較大，程序執(zhí)行時間很長（幾十個小時或幾十天）。如果在程序執(zhí)行過程中出現(xiàn)偶然故障（如電源掉電、磁盤滿、某一臺處理機(jī)故障等），則整個運(yùn)算過程要從頭開始。定時設(shè)置檢查點(diǎn)，保存現(xiàn)場信息。當(dāng)出現(xiàn)故障時，只要回復(fù)到上一個檢查點(diǎn)，不必從頭開始執(zhí)行。,曙光5000A,曙光5000A的第一套超大型系統(tǒng)將于08年11月份落戶“上海超級計算中心”，該系統(tǒng)的計算節(jié)點(diǎn)機(jī)采用四路四核AMD Ba

63、rcelona (主頻2.0GHz)處理器，每個節(jié)點(diǎn)64GB內(nèi)存，胖節(jié)點(diǎn)機(jī)采用八路四核AMD Barcelona(主頻 2.0GHz)處理器，每個節(jié)點(diǎn)128GB內(nèi)存，整個系統(tǒng)由1650個節(jié)點(diǎn)組成龐大機(jī)群，共有6000顆CPU與100T海量內(nèi)存，其理論浮點(diǎn)峰值為每秒230萬億次，采用20GB，延遲小于1.3us的Infiniband高速網(wǎng)絡(luò)進(jìn)行互聯(lián)，采用了WCCS + SuSe Linux 雙操作系統(tǒng)。,從曙光針對5000A的宣傳中，我們

64、經(jīng)常會看到一個比較陌生的詞匯——HPP (Hyper Parallel ProCESsing)體系架構(gòu)。其實目前高性能計算機(jī)主流體系系統(tǒng)并沒有HPP這個提法，而是有MPP，有MSP等等，曙光把5000體系結(jié)構(gòu)叫HPP，主要它在體系結(jié)構(gòu)上結(jié)合了機(jī)群體系結(jié)構(gòu)和MPP體系結(jié)構(gòu)兩類結(jié)構(gòu)的優(yōu)點(diǎn)。它主流的結(jié)構(gòu)是機(jī)群，結(jié)點(diǎn)機(jī)是四路四核的，所以在機(jī)群應(yīng)用角度來說既能夠用很大的機(jī)群，同時還能覆蓋一大塊基于UMA架構(gòu)的，兩個結(jié)合起來起一個名字叫HPP。,本