《并行處理機(jī)和多處理機(jī).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行處理機(jī)和多處理機(jī).ppt（52頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

9、四個(gè)近鄰直接連接。PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64 南北方向上同一列的PU連成一個(gè)環(huán)，東西方向上構(gòu)成一個(gè)閉合螺線。 采用閉合螺線最短距離不超過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實(shí)際上是一臺(tái)小型控制計(jì)算機(jī)。對(duì)陣列處理單元實(shí)行控制和完成標(biāo)量操作。標(biāo)量操作與各PE的數(shù)組操作可以重疊執(zhí)行。 控制器的功能有以下五個(gè)方面：(1) 對(duì)指令進(jìn)行譯碼，并執(zhí)行標(biāo)量指令；(2)

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

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

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

14、但是花費(fèi)更多的數(shù)據(jù)傳送時(shí)間。,算法描述如下: 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)采用兩路線性累加的方法時(shí)加速比為： 若m = n，做乘法的時(shí)間變?yōu)?，則加速比簡(jiǎn)化為 當(dāng)采用遞歸并行累加時(shí)加速比為： 當(dāng)m = n 時(shí)，做乘法的時(shí)間變?yōu)?，則加速比簡(jiǎn)化為,分析其原因，可以看出，線性互連網(wǎng)絡(luò)的傳輸開銷在這里是制約加速比增長(zhǎng)

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

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

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

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

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

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

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

22、3和FUJITSU VP-2000 (2) SMP (Symmetry MultiProcessors)對(duì)稱多處理機(jī); SMP (Shared Memory MulptiProcessors)共享存儲(chǔ)多處理機(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）,多處理機(jī)實(shí)例,科學(xué)計(jì)算中的重大課題要求提供3T性能：(1) 1 Teraflops計(jì)算能力(2) 1 Tera

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

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

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

26、存儲(chǔ)器則比較慢，因?yàn)橥ㄟ^互連網(wǎng)絡(luò)會(huì)產(chǎn)生附加的時(shí)間延遲。 (3) COMA多處理機(jī) 只有Cache的存儲(chǔ)器結(jié)構(gòu) (Cache-Only Memory Architecture) 模型；COMA是一種只用Cache的多處理機(jī)系統(tǒng) 實(shí)際上，COMA模型是NUMA模型的一種特例，后者分布存儲(chǔ)器換成了Cache 在每個(gè)處理機(jī)結(jié)點(diǎn)上沒有主存儲(chǔ)器，全部Cache組成了全局虛擬地址空間 遠(yuǎn)程Cache訪問通過分布Cache目錄進(jìn)行 共享存儲(chǔ)系統(tǒng)擁有統(tǒng)一的尋址空間，程序員不必參與數(shù)據(jù)分配和傳輸。,1、機(jī)群系統(tǒng)的組成 機(jī)群系統(tǒng)是利用高速網(wǎng)絡(luò)將一組高性能工作站或高檔PC機(jī)連接起來，在并行程序設(shè)計(jì)以及可視化人機(jī)交互集

27、成開發(fā)環(huán)境支持下，統(tǒng)一調(diào)度，協(xié)調(diào)處理，實(shí)現(xiàn)高效并行處理的系統(tǒng)。 Cluster、NOW、COW 從結(jié)構(gòu)和結(jié)點(diǎn)間的通信方式來看，屬于分布存儲(chǔ)系統(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)步使得松散耦合系統(tǒng)的通信瓶頸逐步得到緩解。,機(jī)群系統(tǒng) (Cluster),(3)并行編程環(huán)境的開發(fā)使得新編并行程序或改寫串行程序更為容易。 2、機(jī)群系統(tǒng)的特點(diǎn) (1)系統(tǒng)開發(fā)周期短。 (2)用戶投資風(fēng)險(xiǎn)小。 (3)系統(tǒng)價(jià)格低。 (4)節(jié)約系統(tǒng)資源。 U

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

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

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

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