并行處理機和多處理機.ppt

《并行處理機和多處理機.ppt》由會員分享，可在線閱讀，更多相關(guān)《并行處理機和多處理機.ppt（52頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第八章 并行處理機和多處理機,并行處理機又叫SIMD計算機。它是單一控制部件控制下的多個處理單元構(gòu)成的陣列，所以又稱為陣列處理機。 多處理機是由多臺獨立的處理機組成的系統(tǒng)。 并行處理機結(jié)構(gòu)和實例 多處理機結(jié)構(gòu)和實例,并行處理計算機模型 并行處理機定義：多個PU按照一定方式互連，在同一個CU控制下，對各自的數(shù)據(jù)完成同一條指令規(guī)定的操作。從CU看，指令是串行執(zhí)行的，從PU看，數(shù)據(jù)是并行處理的。并行處理機也稱為陣列處理機。按照佛林分類法，它屬于SIMD計算機。 并行處理機的應(yīng)用領(lǐng)域：主要用于高速向量或矩陣運算中。,8.1 并行處理機結(jié)構(gòu)和實例,下圖是H.J.Siegel提出的SIMD計算機的操作模型

2、,并行處理機的操作模型可用五元組來表示：M(N，C，I，M，R), 其中： N為PE個數(shù)。如IlliacIV有64個PE。 C為由控制部件CU直接執(zhí)行的指令集，包括標(biāo)量指令和程序控制指令。I為所有PE并行執(zhí)行的指令集，包括算術(shù)運算、邏輯運算、數(shù)據(jù)尋徑、屏蔽以及其它由每個活動的PE對它的數(shù)據(jù)所執(zhí)行的局部操作。M為屏蔽操作集，每種屏蔽將PE劃分為允許操作和禁止操作兩個子集。 R是數(shù)據(jù)尋徑集，說明互連網(wǎng)絡(luò)中PE間通信所需要的各種設(shè)置模式。,并行處理機的基本結(jié)構(gòu) 兩種SIMD計算機的基本結(jié)構(gòu)： 分布存儲器并行處理機 共享存儲器并行處理機 一臺并行處理機由五個部分組成：多個處理單元PE多個存

3、儲器模塊M一個控制器CU一個互連網(wǎng)絡(luò)ICN一臺輸入輸出處理機IOP,目前的大部分并行處理機是基于分布式存儲器模型的系統(tǒng)。 比較容易構(gòu)成MPP（Massively Parallel Processor）,幾十萬個PE。 必須依靠并行算法來提高PE的利用率。因此，應(yīng)用領(lǐng)域很有限。 CU是控制部件，執(zhí)行標(biāo)量指令，并把向量指令廣播到各個PE中。在CU中通常有一個較大容量的存儲器。 IOP是輸入輸出處理機，或稱為主機。在IOP上安裝操作系統(tǒng)，它除了負(fù)擔(dān)輸入輸出工作外，還負(fù)責(zé)程序的編輯、編譯和調(diào)試等工作。 數(shù)據(jù)在局部存儲器中的分布是一個很關(guān)鍵的問題。 標(biāo)量指令與向量指令可以并發(fā)執(zhí)行。,1、分布存儲器結(jié)構(gòu),

4、共享的多體并行存儲器 SM 通過互連網(wǎng)絡(luò)與各處理單元PE相連。 存儲模塊的數(shù)目等于或略大于處理單元的數(shù)目。 同時在存儲模塊之間合理分配數(shù)據(jù)，通過靈活、高速的互連網(wǎng)絡(luò)，使存儲器與處理單元之間的數(shù)據(jù)傳送在大多數(shù)向量運算中都能以存儲器的最高頻率進(jìn)行，而最少受存儲沖突的影響。 共享存儲器模型的處理單元數(shù)目一般不多，幾個至幾十個。 Burroughs Scientific Processor (BSP)采用了這種結(jié)構(gòu)。16個PE通過一個1617的對準(zhǔn)互連網(wǎng)絡(luò)訪問17個共享存儲器模塊。 存儲器模塊數(shù)與PE數(shù)互質(zhì)可以實現(xiàn)無沖突并行訪問存儲器。,2. 共享存儲器并行處理機,,PE0,互連網(wǎng)絡(luò),,,CU,,PE

5、1,,PEn-1,IOP,,,,,,SM0,,,,SM1,,SMk-1,,,,,并行處理機的主要特點如下： 速度快，特別適于高速數(shù)值計算。 SIMD依靠的是資源重復(fù)，而不是時間重疊。它依靠增加PE個數(shù)，與流水線處理機主要依靠縮短時鐘周期相比，其提高速度的潛力要大得多。 依賴于互連網(wǎng)絡(luò)和并行算法?；ミB網(wǎng)絡(luò)決定了PE之間的連接模式，也決定了并行處理機能夠適應(yīng)的算法。 需要有一臺高性能的標(biāo)量處理機。如果一臺機器的向量處理速度極高，但標(biāo)量處理速度只是每秒一百萬次，那么對于標(biāo)量運算占10的題目來說，總的有效速度就不過是每秒一千萬次。 SIMD基本上是一臺向量處理專用計算機。盡管它有一個功能很強的控制部件

6、實際上起作標(biāo)量處理機的作用，但仍然必須和一臺高性能單處理機配合工作，使后者擔(dān)負(fù)系統(tǒng)的全部管理功能。,并行處理機的特點,IlliacIV 是最先采用SIMD結(jié)構(gòu)的并行機 隨后一個方向是用位片PE制造的并行機，如Goodyear MPP、AMT/DAP 610和TMC/CM-2。CM-5是以SIMD模式運行的同步MIMD計算機。另一方向是用字寬運算PE的中粒度SIMD計算機。 并行處理機的兩個發(fā)展方向： 保留陣列結(jié)構(gòu)，但每個處理單元的規(guī)模減小，如一個bit。去掉陣列結(jié)構(gòu)和分布存儲器。 Burroughs公司的BSP是典型代表。 GF-11是由IBM Watson實驗室研制、作科學(xué)模擬研究用的。Ma

7、sPar MP1是中粒度并行處理機的典型代表。 下面介紹并行處理機的兩種典型代表： 采用陣列結(jié)構(gòu)分布存儲器的IlliacIV并行處理機去掉陣列結(jié)構(gòu)和分布存儲器BSP并行處理機。,并行處理機實例,1963年，美國西屋電器公司提出“Slotnick，The SOLOMON Computer，Simultaneous Operation linked Ordinal Modular Network”。 1966年美國國防遠(yuǎn)景研究規(guī)劃局ARPR與伊利諾依大學(xué)簽定合同。原計劃：256個PE，每個PE每240ns處理一個64位的浮點數(shù)，每個局部存儲器PEM為2K?64位，總的運算速度為1GFLOPS。 美

8、國Burroughs公司和伊利諾依大學(xué)于1972年共同設(shè)計和生產(chǎn)，1975年實際投入運行。用了4倍的經(jīng)費，只達(dá)到1/20的速度。只實現(xiàn)了8?864個PE，只達(dá)到50MFLOPS。 IlliacIV系統(tǒng)的影響非常大。它是并行處理機的典型代表，也是分布存儲器并行處理機的典型代表。 IlliacIV系統(tǒng)由三大部分組成。IlliacIV處理機陣列，陣列控制器，一臺標(biāo)準(zhǔn)的Burroughs B6700計算機。,1 IlliacIV 陣列處理機,1、IlliacIV處理陣列 IlliacIV處理陣列由8864個PU組成。每個PU由處理部件PE和它的局部存儲器PEM組成。 每一個PUi只和它的東、西、南、北

9、四個近鄰直接連接。PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64 南北方向上同一列的PU連成一個環(huán)，東西方向上構(gòu)成一個閉合螺線。 采用閉合螺線最短距離不超過7步。而普通網(wǎng)格最短距離不超過8步。 例如：從PU0到PU36的距離：采用普通網(wǎng)格必須8步：PU0 PU1 PU2 PU3 PU4 PU12 PU20 PU28 PU36或 PU0 PU8 PU16 PU24 PU32 PU33 PU34 PU35 PU36或 （等于8步的很多，大于8步的更多）如果采用閉合螺旋線，只需要7步：PU0 PU63 PU62 PU61 PU60 PU52 P

10、U44 PU36,普通網(wǎng)格必須8步：PU0 PU1 PU2 PU3 PU4 PU12 PU20 PU28 PU36或 PU0 PU8 PU16 PU24 PU32 PU33 PU34 PU35 PU36或 閉合螺旋線只要7步：PU0 PU63 PU62 PU61 PU60 PU52 PU44 PU36或 PU0 PU63 PU55 PU47 PU39 PU38 PU37 PU36或 ,2、陣列控制器 陣列控制器CU實際上是一臺小型控制計算機。對陣列處理單元實行控制和完成標(biāo)量操作。標(biāo)量操作與各PE的數(shù)組操作可以重疊執(zhí)行。 控制器的功能有以下五個方面：(1) 對指令進(jìn)行譯碼，并執(zhí)行標(biāo)量指令；(2)

11、 向各處理單元發(fā)出執(zhí)行數(shù)組操作指令所需的控制信號；(3) 產(chǎn)生和向所有處理單元廣播公共的地址；,(4) 產(chǎn)生和向所有處理單元廣播公共的數(shù)據(jù)；(5) 接收和處理PE、I/O操作以及B6700產(chǎn)生的陷阱中斷信號。 2、輸入輸出系統(tǒng) IlliacIV的輸入輸出系統(tǒng)由磁盤文件系統(tǒng)DFS、I/O分系統(tǒng)和一臺B6700處理機組成。 I/O分系統(tǒng)又由輸入輸出開關(guān)IOS、控制描述字控制器CDC和輸入輸出緩沖存儲器BIOM三個部分組成。,試在含一個PE的SISD機和在含m個PE的且連接成一線性環(huán)的SIMD機上計算下列求內(nèi)積的表達(dá)式。 假定完成每次ADD操作需2個單元時間，完成每次MULTIPLY操作需4個單位時

12、間，沿雙向環(huán)在相鄰PE間移數(shù)需1個單位時間。 （1）SISD計算機上計算s需多少時間？ （2）SIMD計算機上計算s需多少時間？ （3）用SIMD機計算s相對于用SISD機計算的加速比是多少？,習(xí)題8.6,（1）在SISD計算機中計算s需要串行計算n次乘法和n-1次加法。共需要時間： 算法如下： S=A1*B1 For i=2 to n Do S=S+Ai*Bi Enddo （2）在SIMD計算機上計算采用如下的算法：（假設(shè)mn）首先，把向量中的n對元素盡量平均地分配到m個處理器中，每個處理器最多分配n/m+1對，最少分配n/m對，最多經(jīng)過4（n/m+1）+2n/m 時間，所有n個處理

13、器上都得到了一個局部和，對這m個處理器,解答,構(gòu)成的線性環(huán)做累加運算。若采用兩路7線性累加的方法共用做加法m/2次,數(shù)據(jù)傳遞m/2次，共用時間4（n/m+1）+2n/m+3m/2 = 6n/m+ 3m/2+4。 若用遞歸累加的方法，假設(shè)m 是2的p次冪。做p次并行的加法，移位1+2+4+ + m/2 = m-1 次。用時2p+（m-1）。總共用時為 4（n/m+1）+2n/m+2log m +（m-1） = 6n/m+ m+2log m +3 進(jìn)一步分析：當(dāng)2logm 16時 并行累加比兩路線性累加更優(yōu)。 反之，當(dāng)m < 16 時，兩路線性累加更快。其根本原因就是并行累加算法節(jié)省了加法時間，

14、但是花費更多的數(shù)據(jù)傳送時間。,算法描述如下: Par： For j=1 to m Do S(j)=A1j*B1j For 2 to n/m Do S(j)=S(j)+Aij*Bij Enddo S(j)=S(j)+S(j+1) S(j)=S(j)+S(j+2) S(j)=S(j)+S(j+4) S(j)=S(j)+S(j+n/m) Enddo,（3）加速比 當(dāng)采用兩路線性累加的方法時加速比為： 若m = n，做乘法的時間變?yōu)?，則加速比簡化為 當(dāng)采用遞歸并行累加時加速比為： 當(dāng)m = n 時，做乘法的時間變?yōu)?，則加速比簡化為,分析其原因，可以看出，線性互連網(wǎng)絡(luò)的傳輸開銷在這里是制約加速比增長

15、的最大障礙，無論采用何種并行算法，一個數(shù)據(jù)從線性環(huán)形網(wǎng)絡(luò)中的一個節(jié)點傳遞到最遠(yuǎn)的節(jié)點的最短時間為m/2，這個時間是無法改進(jìn)的，并且隨著處理節(jié)點的增多成為最主要的時間開銷。相對而言，加法和乘法隨著處理單元的增多，所占的時間比例越來越小。,8.2多處理機結(jié)構(gòu)和實例,兩個或兩個以上處理機(包括PU和CU)，通過高速互連網(wǎng)絡(luò)連接起來，在統(tǒng)一的操作系統(tǒng)管理下，實現(xiàn)指令以上級（任務(wù)級、作業(yè)級）并行。 按照Flynn分類法，多處理機系統(tǒng)屬于MIMD計算機。 多處理機系統(tǒng)由多個獨立的處理機組成，每個處理機都能夠獨立執(zhí)行自己的程序。,多處理機結(jié)構(gòu)由若干臺獨立的計算機組成，每臺計算機能夠獨立執(zhí)行自己的程序。Fly

16、nn稱這種結(jié)構(gòu)為多指令流多數(shù)據(jù)流（MIMD）結(jié)構(gòu)。多處理機系統(tǒng)中的處理機之間按某種形式互連，從而實現(xiàn)程序之間的數(shù)據(jù)交換和同步。 多處理機系統(tǒng)中每臺處理機都有寄存器、運算器、邏輯部件、訪問存儲器和I/O的通道。 還有一種多處理機系統(tǒng)中每臺處理機有自己的存儲器和I/O設(shè)備。,多處理機結(jié)構(gòu),互連網(wǎng)絡(luò),處理機1,處理機2,處理機N,,,,,存儲器,存儲器,存儲器,,,,,I/O,,I/O,,具有通過互連網(wǎng)絡(luò)共享存儲器和I/O的多處理機系統(tǒng),每個處理機都擁有自己的存儲器和I/O的多處理機系統(tǒng),1、結(jié)構(gòu)靈活性 并行處理機：專用，PE數(shù)很多（幾千個），固定有限的通信多處理機： 通用，幾十個，高速靈活的通信

17、2、程序并行性 并行處理機的并行性存在于指令內(nèi)部，識別比較容易。多處理機的并行性存在于指令外部，在多個任務(wù)之間，識別難度較大。 一個簡單的例子：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,多處理機系統(tǒng)的特點,3、并行任務(wù)派生并行處理機把同種操作集中在一起，由指令直接啟動各PE同時工作。 多處理機用專門的指令來表示并發(fā)關(guān)系，一個任務(wù)開始執(zhí)行時能夠派生出與它并行執(zhí)行的另一些任務(wù)，如果任務(wù)數(shù)多于處理機數(shù)，多余的任務(wù)進(jìn)入排隊器等待。 4、進(jìn)程同步并行處理機僅一個C

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

19、閑狀態(tài)(4) 由于一臺或多臺處理機執(zhí)行無用的工作(5) 系統(tǒng)控制和操作調(diào)度所需開銷 研究多處理機的目的：提前5年得到速度高10倍的機器。 或用1/10的價格獲得一臺高性能的機器。如果設(shè)計得好，在某些適合進(jìn)行并行處理得應(yīng)用領(lǐng)域，可以達(dá)到：提前10年得到速度高100倍的機器 或用1/100的價格獲得一臺高性能的機器。,多處理機性能模型,并行性在很大程度上依賴于R/C比值， 其中：R代表程序執(zhí)行時間，C代表通信開銷。 通常：R/C比值小，并行性低。R/C比值大，并行性高如果把作業(yè)分解成較大的塊，就能得到較大的R/C值，但是所得到的并行性比最大可能的并行性要小得多。 R/C比值是衡量任務(wù)粒度(Gran

20、ularity)大小的尺度在粗粒度（Coarsegrain）并行情況下，R/C比值比較大，通信開銷小在細(xì)粒度（Finegrain）并行情況下，R/C比值比較小，通信開銷大 細(xì)粒度并行性需要的處理機多，粗粒度并行性需要的處理機少。 細(xì)粒度并行性的基本原理是把一個程序盡可能地分解成能并行執(zhí)行的小任務(wù)。在極端情況下，一個小任務(wù)只完成一個操作。,1.基本模型,在兩臺處理機情況 每個任務(wù)的執(zhí)行時間為R個單位時間 兩個任務(wù)不在同一臺處理機上時，通信開銷為C個單位時間 K個任務(wù)給一臺處理機 M-K個任務(wù)給另一臺處理機 總處理時間=Rmax(M-K，K)+C(M-K)K 結(jié)論：當(dāng)R/CM/2時，把任務(wù)平均分給

21、兩臺處理機能使總處理時間最小。,2.N臺處理機系統(tǒng)的基本模型,將Ki個任務(wù)分配給第i臺處理機。推廣前面的式子：,分析任務(wù)均分給N臺處理機和任務(wù)集中在一臺處理機的總處理時間差，有： 如果R/C比臨界值M/2大，將任務(wù)平均分配給盡可能多的處理機進(jìn)行處理，能獲得最短處理時間。如果R/C比臨界值M/2小，即使有很多臺處理機可供使用，也不可能比用一臺處理機處理全部任務(wù)快。,并行系統(tǒng)的加速比是一個計算問題在一臺處理機上的運行時間與在并行系統(tǒng)上的運行時間的比值，可近似如下：,多處理機的Cache一致性（自己看）,多處理機系統(tǒng)主要有四大類： (1) 多向量處理機系統(tǒng)：如CRAY YMP-90, NEC SX-

22、3和FUJITSU VP-2000 (2) SMP (Symmetry MultiProcessors)對稱多處理機; SMP (Shared Memory MulptiProcessors)共享存儲多處理機 如SGI Challenge，Sun SparcCenter 2000 (3) MPP (massively parallel processing)大規(guī)模并行處理機如Intel Paragon, CM-5, Cray T3D (4) Cluster 機群系統(tǒng)（NOW或COM）,多處理機實例,科學(xué)計算中的重大課題要求提供3T性能：(1) 1 Teraflops計算能力(2) 1 Tera

23、byte主存儲器(3) 1 Terabyte/s 輸入輸出頻帶寬度目前，速度還慢1000倍左右，存儲容量和I/O帶寬差距更大。 科學(xué)計算中的重大課題：全球氣候預(yù)報, 基因工程 ,飛行動力學(xué) ,海洋環(huán)流, 流體動力學(xué), 超導(dǎo)建模, 半導(dǎo)體建模, 量子染色動力學(xué), 視覺 采用的關(guān)鍵技術(shù)：VLSI, 可擴展技術(shù), 共享虛擬存儲技術(shù),大規(guī)模并行處理機(MPP),虛擬共享存儲器(Shared Virtual Memory)也稱為共享分布存儲器(Distributed Shared Memory)；物理上分布存儲器，邏輯上共享存儲器。 虛擬共享存儲器的優(yōu)點：編程容易, 系統(tǒng)結(jié)構(gòu)靈活可擴充性好, 有較好的軟

24、件移植性 與消息傳遞方式相比，程序運行效率高，主要原因： (1) 數(shù)據(jù)塊緩存在本地 (內(nèi)存或Cache中), 可以多次使用(2) 通信時間分散，提高了并行性(3) 擴大存儲空間，減少換頁操作 虛擬共享存儲器實現(xiàn)途徑：(1) 硬件實現(xiàn), 利用Cache技術(shù)。需要增加專用硬件(2) 操作系統(tǒng)和庫實現(xiàn)，通過虛擬存儲機制取得共享和一致性。在松耦合的分布存儲多處理機上，不需要增加任何硬件(3) 編譯實現(xiàn)，自動將共享訪問轉(zhuǎn)換成同步和一致原語。大多數(shù)系統(tǒng)采用途徑(1)和(2)，或這兩種途徑結(jié)合實現(xiàn),SMP稱為共享存儲多處理機 (Shared Memory mulptiProcessors),也稱為對稱多處理

25、機 (Symmetry MultiProcessors) 有三種模型： (1) UMA多處理機均勻存儲器存取模型 (Uniform Memory Access)存儲器被所有處理機均勻共享所有處理機對所有存儲單元具有相同的存取時間 每臺處理機有局部Cache 外圍設(shè)備可以共享 (2) NUMA多處理機非均勻存儲器存取 (Nonuniform Memory Access)模型存儲器訪問時間隨存儲單元的位置不同而變化。共享存儲器在物理上是分布在所有處理機中的本地存儲器。所有局部存儲器地址空間的集合就組成了全局地址空間。,對稱多處理機 (SMP),處理機訪問本地存儲器比較快，訪問屬于另一臺處理機的遠(yuǎn)程

26、存儲器則比較慢，因為通過互連網(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ù)分配和傳輸。,1、機群系統(tǒng)的組成 機群系統(tǒng)是利用高速網(wǎng)絡(luò)將一組高性能工作站或高檔PC機連接起來，在并行程序設(shè)計以及可視化人機交互集

27、成開發(fā)環(huán)境支持下，統(tǒng)一調(diào)度，協(xié)調(diào)處理，實現(xiàn)高效并行處理的系統(tǒng)。 Cluster、NOW、COW 從結(jié)構(gòu)和結(jié)點間的通信方式來看，屬于分布存儲系統(tǒng)。 機群系統(tǒng)中的主機和網(wǎng)絡(luò)可以是同構(gòu)的，也可以是異構(gòu)的。 微處理機技術(shù)、網(wǎng)絡(luò)技術(shù)和并行編程環(huán)境的發(fā)展使得機群系統(tǒng)這一新的并行處理系統(tǒng)形式正成為當(dāng)前研究的熱點。(1)微處理器的性能不斷提高。(2)網(wǎng)絡(luò)技術(shù)的進(jìn)步使得松散耦合系統(tǒng)的通信瓶頸逐步得到緩解。,機群系統(tǒng) (Cluster),(3)并行編程環(huán)境的開發(fā)使得新編并行程序或改寫串行程序更為容易。 2、機群系統(tǒng)的特點 (1)系統(tǒng)開發(fā)周期短。 (2)用戶投資風(fēng)險小。 (3)系統(tǒng)價格低。 (4)節(jié)約系統(tǒng)資源。 U

28、C Berkeley計算機系100多臺工作站的使用情況調(diào)查表明，一般單機系統(tǒng)的使用率不到10%，而機群系統(tǒng)中的資源利用率可達(dá)到80%左右。 (5)系統(tǒng)擴展性好。 (6)用戶編程方便。,3、機群系統(tǒng)的關(guān)鍵技術(shù) (1)高效的通信系統(tǒng)在用戶空間實現(xiàn)通信協(xié)議精簡通信協(xié)議Active Message通信機制 (2) 并行程序設(shè)計環(huán)境PVM(Parallel Virtual Machine)開始于1989年夏天,美國橡樹嶺國家實驗室(ORNL)；是一套并行計算工具軟件，支持多用戶及多任務(wù)運行；支持多種結(jié)構(gòu)的計算機，工作站、并行機以及向量機等；支持C、C++和Fortran語言；自由軟件，使用非常廣泛；編程

29、模型可以是SPMD或MPMD；具有容錯功能，當(dāng)發(fā)現(xiàn)一個結(jié)點出故障時，自動將之刪除MPI(Message Passing Interface)在1992年11月至1994年元月產(chǎn)生。,能用于大多數(shù)并行計算機、計算機機群和異構(gòu)網(wǎng)絡(luò)環(huán)境，支持C和Fortran兩種語言,編程模型采用SPMD,Express：美國Parasoft公司推出；能在不同的硬件環(huán)境上運行；支持C和Fortran兩種程序設(shè)計語言。Linda：美國Yale大學(xué)與科學(xué)計算協(xié)會共同研制；通過函數(shù)擴充現(xiàn)并行程序的設(shè)計；支持C-Linda、Fortran-Linda等 (3) 并行程序設(shè)計語言在多處理機系統(tǒng)中，必須用并行程序設(shè)計語言編寫程

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

31、不同。因此，準(zhǔn)確的負(fù)載定義應(yīng)是負(fù)載量與結(jié)點處理能力的比值負(fù)載平衡技術(shù)的核心就是調(diào)度算法，即將各個任務(wù)比較均衡地分布到不同的處理結(jié)點上并行計算，從而使各結(jié)點的利用率達(dá)到最大。 負(fù)載平衡技術(shù)分為靜態(tài)和動態(tài)兩大類：靜態(tài)方法是在編譯時針對用戶程序的各種信息（任務(wù)的計算量和通信關(guān)系等）及并行系統(tǒng)本身的狀況（網(wǎng)絡(luò)結(jié)構(gòu)、各結(jié)點計算能力等）對用戶程序中的并行任務(wù)作出靜態(tài)分配決策。,動態(tài)方法是在程序運行過程中實現(xiàn)負(fù)載平衡的。它通過分析并行系統(tǒng)的實時負(fù)載信息，動態(tài)地將任務(wù)在各處理機之間進(jìn)行分配和調(diào)整，以消除系統(tǒng)中負(fù)載分布的不均勻性。動態(tài)負(fù)載平衡的算法簡單，實時控制，但增加了系統(tǒng)的額外開銷。 (5)并行程序調(diào)試技術(shù)用并行程序設(shè)計語言編寫程序，比用串行程序設(shè)計語言更容易出錯，因此，在多處理機系統(tǒng)中，用并行程序設(shè)計語言編寫程序更加依賴于并行調(diào)試工具。并行程序調(diào)試的主要困難：并行程序的執(zhí)行過程不能重現(xiàn)。 (6)可靠性技術(shù)在多處理機上運行的程序通常比較大，程序執(zhí)行時間很長（幾十個小時或幾十天）。如果在程序執(zhí)行過程中出現(xiàn)偶然故障（如電源掉電、磁盤滿、某一臺處理機故障等），則整個運算過程要從頭開始。定時設(shè)置檢查點，保存現(xiàn)場信息。當(dāng)出現(xiàn)故障時，只要回復(fù)到上一個檢查點，不必從頭開始執(zhí)行。,